Port graph adaptors & Co.

[Alpar Juttner]

These files are affected:

• lemon/ugraph_adaptor.h
• lemon/bpugraph_adaptor.h
• lemon/graph_adaptor.h
• lemon/edge_set.h
• lemon/sub_graph.h

• lemon/bits/edge_set_extender.h
• lemon/bits/graph_adaptor_extender.h

• test/graph_adaptor_test.cc
• test/edge_set_test.cc

• doc/graph-adaptors.dox

[Balazs Dezso]

The [e67acd83a9ca] patch contains preliminary support for graph adaptors. The documentation of the classes are not cleaned. The patch based on the [b6732e0d38c5] patch, which can be found as the attachment of ticket #129.

[Balazs Dezso]

Porting arc and edge sets in [591e8758d98b].

[Alpar Juttner]

Replying to deba:

The [e67acd83a9ca] patch contains preliminary support for graph adaptors. The documentation of the classes are not cleaned. The patch based on the [b6732e0d38c5] patch, which can be found as the attachment of ticket #129.

I had a short look at [b6732e0d38c5]. The followings should certainly be fixed.

• The graph adaptors are not in the module hierarchy
• The auxiliary classed should not appear in the doxygen doc.
• The names of the adaptors should be revised. Names like UndirDigraphAdaptor are not acceptable.

Also, it may be that less is more here (i.e. a smaller but perspicacious set of tools might be better).

For sake of history keeping, the clean-up changes should be applied on the top of [b6732e0d38c5].

[Balazs Dezso]

Replying to alpar:

• The names of the adaptors should be revised. Names like UndirDigraphAdaptor are not acceptable.

Could you suggest proper names? I think the you think unacceptable the names of UndirDigraphAdaptor and the DirGraphAdaptor.

Also, it may be that less is more here (i.e. a smaller but perspicacious set of tools might be better).

Could you clarify it?

[Balazs Dezso]

Improvements on adaptors

[Balazs Dezso]

The [7a4a426a037e] patch contains some improvements on graph adaptors.

Some topics must be clarified connected to the graph adaptors:

• naming (one possibility)
  • RevDigraphAdaptor? => Reverser
  • SubDigraphAdaptor? => DigraphFilter?
  • SubGraphAdaptor? => GraphFilter?
  • NodeSubGraphAdaptor? => NodeFilter? (specialized)
  • NodeSubDigraphAdaptor? => NodeFilter? (specialized)
  • EdgeFilterGraphAdaptor? => EdgeFilter?
  • ArcSubDigraphAdaptor? =>ArcFilter?
  • UndirDigraphAdaptor? => Undirector
  • SplitDigraphAdaptor? => NodeSplitter?
  • DirGraphAdaptor? => Director
• the style of documentation
  • are the example codes necessary?
• I don't think, that some of the adaptors have to be removed. But what is your opinion?

[Alpar Juttner]

Replying to deba:

Some other choices:

• RevDigraphAdaptor? => Reverser

• ReverseGraph

• SubDigraphAdaptor? => DigraphFilter?

• SubDigraph

• SubGraphAdaptor? => GraphFilter?

• SubGraph

• NodeSubGraphAdaptor? => NodeFilter? (specialized)
• NodeSubDigraphAdaptor? => NodeFilter? (specialized)
• EdgeFilterGraphAdaptor? => EdgeFilter?
• ArcSubDigraphAdaptor? =>ArcFilter?

• FilterNodes, FilterEdges, FilterArcs

• UndirDigraphAdaptor? => Undirector
• DirGraphAdaptor? => Director

• What about Orienter<ListGraph> or just Orient<ListGraph>

• SplitDigraphAdaptor? => NodeSplitter?

• SplitNodes<ListGraph>

We might also want to consider putting this stuff into a namespace (e.g. lemon::adaptors

• the style of documentation
  • are the example codes necessary?

I don't think so. The examples are nice, but they are very long considering how much they help people wanting to use these tools for a different purpose.

The right place for these examples are the tutorial.

• I don't think, that some of the adaptors have to be removed. But what is your opinion?

[Balazs Dezso]

Replying to alpar:

Replying to deba:

Some other choices:

• RevDigraphAdaptor? => Reverser

• ReverseGraph

ReverseGraph? or ReverseDigraph??

• What about Orienter<ListGraph> or just Orient<ListGraph>

I think, the Orient<ListGraph?> is a good name.

• SplitDigraphAdaptor? => NodeSplitter?

• SplitNodes<ListGraph>

SplitNodes?<Digraph>

[Balazs Dezso]

Improvements on adaptors II

[Balazs Dezso]

Replying to deba:

Replying to alpar:

Replying to deba:

Some other choices:

• RevDigraphAdaptor? => Reverser

• ReverseGraph

ReverseGraph? or ReverseDigraph??

• What about Orienter<ListGraph> or just Orient<ListGraph>

I think, the Orient<ListGraph?> is a good name.

• SplitDigraphAdaptor? => NodeSplitter?

• SplitNodes<ListGraph>

SplitNodes?<Digraph>

[cb86ce95522f] contains patch for renaming and doc cleaning. The graph adaptors are moved to the same file, because the FilterNodes? dependency.

[Balazs Dezso]

Bundle for adaptors

[Balazs Dezso]

I remade the patches top on the current trunk in the adaptors.bundle. Since the base of the original patches several refactorings are made on the trunk, therefore the merge would be quite hard with the original patches. The new version makes the following additional refactorings, moves the map assignments to private and uses assertions in the variant instead of exceptions.

[Alpar Juttner]

Replying to deba:

I remade the patches top on the current trunk in the adaptors.bundle. Since the base of the original patches several refactorings are made on the trunk, therefore the merge would be quite hard with the original patches. The new version makes the following additional refactorings, moves the map assignments to private and uses assertions in the variant instead of exceptions.

I basically like the new names here (at least much prefer it to the previous ones).

[Alpar Juttner]

The changesets are in the main. (with changes commit logs, see [0c5dd7ceda03], [4b6112235fad] and [76287c8caa26]).

I think, this stuff still deserves a thorough review.

[Balazs Dezso]

ArcSet? and EdgeSet? port

[Balazs Dezso]

I made refreshed patch [68fe66e2b34a], which contains the EdgeSet? and ArcSet? port. What is your opinion about porting the SVN subgraph. I do not think, that it is a very useful class, so I think it can be abandoned.

[Alpar Juttner]

Replying to deba:

What is your opinion about porting the SVN subgraph. I do not think, that it is a very useful class, so I think it can be abandoned.

I think it _is_ an important tool, though it is certainly not of high priority to port it. Still, at least ticket should be created about its port.

[Peter Kovacs]

Bundle file containing 8 changesets

[Peter Kovacs]

Replying to alpar:

I think, this stuff still deserves a thorough review.

I made this thorough review, but it was a huge amount of work.

adaptor-d369e885d196--b510afb08391.bundle​ contains the following 8 changesets for the adaptors:

• [d369e885d196] Fix the usage of tags in adaptors.h (#67)
• [3c0d39b6388c] Avoid warning in adaptors.h (#67)
• [9d9990909fc8] Add missing const keywords (+ remove misleading ones) (#67)
• [91fcb8ed4cdc] Various bug fixes and code improvements in adaptors.h (#67)
  • Fix !UndirectorBase::nodeNum().
  • Fix !UndirectorBase::findEdge().
  • Fix !OrienterBase::addArc().
  • Fix !OrienterBase::findArc().
  • Improve !SplitNodesBase::findArc().
  • Add missing notifier() function in UndirectorBase.
  • Add missing typedefs for maps (conform to the ReferenceMap concept).
  • Add some useful typedefs for graph adaptors.
• [67623f503603] Rename unHide() to unhide() in the subgraph adaptors (#67)
• [c3ac2a321641] Add creator functions for Residual and Residual::ResidualCapacity (#67)
• [24421f952079] Various doc improvements for graph adaptors (#67)
  • Add notes about modifying the adapted graphs through adaptors if it is possible.
  • Add nodes about the possible conversions between the Node, Arc and Edge types of the adapted graphs and the adaptors.
  • Hide the default values for template parameters (describe them in the doc instead).
  • More precise docs for template parameters.
  • More precise docs for member functions.
  • Add docs for important public typedefs.
  • Unify the docs of the adaptors.
  • Add \relates commands for the creator functions.
• [b510afb08391] Greatly extend and improve graph_adaptor_test.cc (#67)
  • Add concept checks for the alterable, extendable, erasable and clearable adaptors.
  • Add test cases for modifying the underlying graphs through adaptors whenever it is possible.
  • Check the conversions between Node, Arc and Edge types.
  • Add more test cases for the adaptor-specific functions and maps: hide(), unhide(), hidden(), forward(), backward(), CombinedArcMap, CombinedNodeMap, ResidualCapacity etc.
  • Use checkGraphIncEdgeArcLists() to simplify the test caes for undirected graphs.
  • Add test cases that use static graph structure (GridGraph) with Several adaptors combined. (This is in comment yet, since it depends on bugfix #195.)
  • Add comments for the test cases.

[Peter Kovacs]

In [b510afb08391] the lines between 1397--1465 are commented since these part depends on the bug fix #195. As soon as both changesets are merged to the main branch, these lines should be used in the test file.

Apart from that there are other similar commented lines, namely 808-809 and 836-837, but I do not know what could be done in order to support them. (Combined maps conform to the ReferenceMap concept if the value type is int, but they do not if the value type is bool.) Balazs, do you have any idea for that? Or somebody else?

[Peter Kovacs]

Other questions:

• Currently we use the names adaptors.h and graph_adaptor_test.cc. I suggest similar names: graph_adaptors.h and graph_adaptors_test.cc or adaptors.h and adaptors_test.cc. What do you like?
• What about renaming unhide() to show() (or maybe add show() as an alternative for unhide()) in sub(di)graph adaptors?
• What about renaming Residual to ResidualDigraph (since there are residual arcs, capacities etc.)?

The renamings applied so far should be involved in the migration script and the guide, too.

[Alpar Juttner]

Replying to kpeter:

adaptor-d369e885d196--b510afb08391.bundle​ contains the following 8 changesets for the adaptors:

I like all these changes except this only one:

• [67623f503603] Rename unHide() to unhide() in the subgraph adaptors (#67)

Let's find a better name first, then rename to it directly.

[Alpar Juttner]

Replying to kpeter:

Other questions:

• Currently we use the names adaptors.h and graph_adaptor_test.cc. I suggest similar names: graph_adaptors.h and graph_adaptors_test.cc or adaptors.h and adaptors_test.cc. What do you like?

I don't think it is worth changing. It would be a bit better, but not significantly.

• What about renaming unhide() to show() (or maybe add show() as an alternative for unhide()) in sub(di)graph adaptors?

Another suggestions:

void enable(Node);
void disable(Node);
void status(Node, bool); //set the status
bool status(Node); // query the status

• What about renaming Residual to ResidualDigraph (since there are residual arcs, capacities etc.)?

Let's change it.

The renamings applied so far should be involved in the migration script and the guide, too.

Agreed.

[Peter Kovacs]

Replying to alpar:

• What about renaming unhide() to show() (or maybe add show() as an alternative for unhide()) in sub(di)graph adaptors?

Another suggestions: void enable(Node); void disable(Node); void status(Node, bool); set the status bool status(Node); query the status

I don't like using status(), since we always have the opportunity to read and write the map itself like status() could be used. So I prefer show(), hide() or enable(), disable(). Which one do you like?

[Alpar Juttner]

I don't like using status(), since we always have the opportunity to read and write the map itself like status() could be used.

Why on earth do we need anything to set/query these values, then?

So I prefer show(), hide() or enable(), disable(). Which one do you like?

[Peter Kovacs]

Replying to alpar:

I don't like using status(), since we always have the opportunity to read and write the map itself like status() could be used.

Why on earth do we need anything to set/query these values, then?

It is a good question. Maybe it is nicer. :)

These functions just read/write the filter maps. E.g.

    void hide(const Node& n) const { _node_filter->set(n, false); }
    void unHide(const Node& n) const { _node_filter->set(n, true); }
    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }

[Alpar Juttner]

So I prefer show(), hide() or enable(), disable(). Which one do you like?

I slightly prefer enable()/disable(). But if we want convenience functions for setting why don't we want convenience query function like this?

bool status(Node);

Once we have this query function, why not follow the usual LEMON convention and define a symmetric set function as follows?

void status(Node, bool);

In fact, I'm not against having both enable()/disable() and status(). (cf. my comment on the MIP interface, where I proposed just the opposite.)

[Peter Kovacs]

I added two new attachments.

The bundle contains the same changes (with the same logs) as the former bundle file, except for the renamings and the last changeset that modifies the test file.

• [d369e885d196] Fix the usage of tags in adaptors.h (#67)
• [3c0d39b6388c] Avoid warning in adaptors.h (#67)
• [9d9990909fc8] Add missing const keywords (+ remove misleading ones) (#67)
• [91fcb8ed4cdc] Various bug fixes and code improvements in adaptors.h (#67)
• [14bb8812b8af] Add creator functions for Residual and Residual::ResidualCapacity (#67)
• [fbd6e04acf44] Various doc improvements for graph adaptors (#67)

The [aea2dc0518ce] patch replaces hide(), unHide(), hidden() functions with status(Item), status(Item, bool), enable(Item), disable(Item) functions in all the five subgraph adaptors.

I would like to make the new variant of the testfile changeset once the above changesets are merged into the main branch (to be able to use the correct names and bugfix #195).

[Peter Kovacs]

[c246659c8b19] removes the "non-checked" variants of the subgraph adaptors and renames a lot of template parameters to make the doc nicer.

[Alpar Juttner]

I've merged all of the lemon/adaptors.h related changes to the main branch.

However, the changeset porting the EdgeSet and ArcSet (i.e. [68fe66e2b34a]) is still pending for review.

[Peter Kovacs]

I attached four new pathces, which could be applied in this order:

• [a2fd8b8d0b30] Greatly extend the test file for adaptors (the same as my previous changeset except for some renamings).
• [acfb0f24d178] Rename Residual to ResidualDigraph.
• [2b5496c62ccd] Rename graph_adaptor_test.cc to adaptors_test.cc.
• [4f1431aeef42] Extend the migration script to handle the renamings of adaptors.

[Alpar Juttner]

Replying to kpeter:

I attached four new pathces, which could be applied in this order:

They all went to the main branch.

[Alpar Juttner]

Replying to alpar:

However, the changeset porting the EdgeSet and ArcSet (i.e. [68fe66e2b34a]) is still pending for review.

It also went to the main branch, so I think I can close the ticket.

[Alpar Juttner]

Replying to alpar:

Replying to deba:

What is your opinion about porting the SVN subgraph. I do not think, that it is a very useful class, so I think it can be abandoned.

I think it _is_ an important tool, though it is certainly not of high priority to port it. Still, at least ticket should be created about its port.

See #200 for a follow-up.