COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 10 years ago

Last modified 10 years ago

#67 closed task (fixed)

Port graph adaptors & Co.

Reported by: Alpar Juttner Owned by: Balazs Dezso
Priority: critical Milestone: LEMON 1.1 release
Component: core Version:
Keywords: Cc:
Revision id:

Description (last modified by 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

Attachments (14)

e67acd83a9ca.patch (171.4 KB) - added by Balazs Dezso 11 years ago.
591e8758d98b.patch (63.7 KB) - added by Balazs Dezso 11 years ago.
7a4a426a037e.patch (38.4 KB) - added by Balazs Dezso 11 years ago.
Improvements on adaptors
cb86ce95522f.patch.gz (38.3 KB) - added by Balazs Dezso 10 years ago.
Improvements on adaptors II
adaptors.bundle (31.1 KB) - added by Balazs Dezso 10 years ago.
Bundle for adaptors
68fe66e2b34a.patch (64.1 KB) - added by Balazs Dezso 10 years ago.
ArcSet? and EdgeSet? port
adaptor-d369e885d196--b510afb08391.bundle (14.0 KB) - added by Peter Kovacs 10 years ago.
Bundle file containing 8 changesets
adaptor-d369e885d196--fbd6e04acf44.bundle (9.9 KB) - added by Peter Kovacs 10 years ago.
adaptor-rename-aea2dc0518ce.patch (17.7 KB) - added by Peter Kovacs 10 years ago.
adaptor-checked-param-c246659c8b19.patch (44.3 KB) - added by Peter Kovacs 10 years ago.
adap1-test-a2fd8b8d0b30.patch (48.2 KB) - added by Peter Kovacs 10 years ago.
adap2-rename-residual-acfb0f24d178.patch (4.1 KB) - added by Peter Kovacs 10 years ago.
adap3-rename-test-2b5496c62ccd.patch (1.8 KB) - added by Peter Kovacs 10 years ago.
adap4-migration-4f1431aeef42.patch (1.8 KB) - added by Peter Kovacs 10 years ago.

Download all attachments as: .zip

Change History (48)

comment:1 Changed 11 years ago by Alpar Juttner

Description: modified (diff)

comment:2 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:3 Changed 11 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Balazs Dezso

Changed 11 years ago by Balazs Dezso

Attachment: e67acd83a9ca.patch added

comment:4 Changed 11 years ago by 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.

comment:5 Changed 11 years ago by Balazs Dezso

Porting arc and edge sets in [591e8758d98b].

Changed 11 years ago by Balazs Dezso

Attachment: 591e8758d98b.patch added

comment:6 Changed 11 years ago by Alpar Juttner

Priority: majorcritical

comment:7 in reply to:  4 ; Changed 11 years ago by 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].

comment:8 in reply to:  7 Changed 11 years ago by 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?

Changed 11 years ago by Balazs Dezso

Attachment: 7a4a426a037e.patch added

Improvements on adaptors

comment:9 Changed 11 years ago by Balazs Dezso

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

Some topics must be clarified connected to the graph adaptors:

comment:10 in reply to:  9 ; Changed 11 years ago by Alpar Juttner

Replying to deba:

Some other choices:

  • ReverseGraph
  • SubDigraph
  • SubGraph
  • FilterNodes, FilterEdges, FilterArcs
  • What about Orienter<ListGraph> or just Orient<ListGraph>
  • 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?

comment:11 in reply to:  10 ; Changed 11 years ago by Balazs Dezso

Replying to alpar:

Replying to deba:

Some other choices:

  • ReverseGraph

ReverseGraph? or ReverseDigraph??

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

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

  • SplitNodes<ListGraph>

SplitNodes?<Digraph>

comment:12 Changed 11 years ago by Balazs Dezso

Status: newassigned

Changed 10 years ago by Balazs Dezso

Attachment: cb86ce95522f.patch.gz added

Improvements on adaptors II

comment:13 in reply to:  11 Changed 10 years ago by Balazs Dezso

Replying to deba:

Replying to alpar:

Replying to deba:

Some other choices:

  • ReverseGraph

ReverseGraph? or ReverseDigraph??

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

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

  • 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.

Changed 10 years ago by Balazs Dezso

Attachment: adaptors.bundle added

Bundle for adaptors

comment:14 Changed 10 years ago by 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.

comment:15 in reply to:  14 Changed 10 years ago by 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).

comment:16 Changed 10 years ago by 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.

Changed 10 years ago by Balazs Dezso

Attachment: 68fe66e2b34a.patch added

ArcSet? and EdgeSet? port

comment:17 Changed 10 years ago by 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.

comment:18 in reply to:  17 ; Changed 10 years ago by 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.

Changed 10 years ago by Peter Kovacs

Bundle file containing 8 changesets

comment:19 in reply to:  16 ; Changed 10 years ago by 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.

comment:20 Changed 10 years ago by 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?

comment:21 Changed 10 years ago by 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.

comment:22 in reply to:  19 Changed 10 years ago by 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:

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

comment:23 in reply to:  21 ; Changed 10 years ago by 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.

comment:24 in reply to:  23 ; Changed 10 years ago by 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?

comment:25 in reply to:  24 ; Changed 10 years ago by 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?

comment:26 in reply to:  25 Changed 10 years ago by 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]; }

comment:27 in reply to:  25 Changed 10 years ago by 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.)

Changed 10 years ago by Peter Kovacs

Changed 10 years ago by Peter Kovacs

comment:28 Changed 10 years ago by 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.

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).

Changed 10 years ago by Peter Kovacs

comment:29 Changed 10 years ago by Peter Kovacs

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

comment:30 in reply to:  29 ; Changed 10 years ago by 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.

Changed 10 years ago by Peter Kovacs

Changed 10 years ago by Peter Kovacs

Changed 10 years ago by Peter Kovacs

Changed 10 years ago by Peter Kovacs

comment:31 Changed 10 years ago by 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.

comment:32 in reply to:  31 Changed 10 years ago by Alpar Juttner

Replying to kpeter:

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

They all went to the main branch.

comment:33 in reply to:  30 Changed 10 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

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.

comment:34 in reply to:  18 Changed 10 years ago by 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.

Note: See TracTickets for help on using tickets.