COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 9 years ago

#68 closed task (done)

Port static graph implementation

Reported by: Alpar Juttner Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.2 release
Component: core Version:
Keywords: Cc:
Revision id:

Description

Namely the file

  • lemon/static_graph.h

Attachments (12)

68-1-cf360f758f25.patch (8.1 KB) - added by Peter Kovacs 10 years ago.
68-2-f4b5c2d5449d.patch (5.4 KB) - added by Peter Kovacs 10 years ago.
68-3-6cab2ab9d8e7.patch (2.9 KB) - added by Peter Kovacs 10 years ago.
68-4-a3de05c56e7e.patch (3.0 KB) - added by Peter Kovacs 10 years ago.
68-5-6959186d3612.patch (3.3 KB) - added by Peter Kovacs 10 years ago.
68-6-2d82f9560e1a.patch (4.7 KB) - added by Peter Kovacs 10 years ago.
68-7-4cad1981d18d.patch (697 bytes) - added by Peter Kovacs 10 years ago.
68-8-afad5d01ef8e.patch (1.9 KB) - added by Peter Kovacs 10 years ago.
68-5-new-eff1caf6d32e.patch (3.3 KB) - added by Peter Kovacs 10 years ago.
68-6-new-5764dd9b6e18.patch (5.2 KB) - added by Peter Kovacs 10 years ago.
68-7-new-05b444bfc02b.patch (697 bytes) - added by Peter Kovacs 10 years ago.
68-311-static-a143f19f465b.patch (6.0 KB) - added by Peter Kovacs 10 years ago.

Download all attachments as: .zip

Change History (26)

comment:1 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:2 Changed 11 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Balazs Dezso

comment:3 Changed 10 years ago by Alpar Juttner

Milestone: LEMON 1.1 release

comment:4 Changed 10 years ago by Peter Kovacs

Milestone: LEMON 1.2 release
Owner: changed from Balazs Dezso to Peter Kovacs
Status: newassigned

Changed 10 years ago by Peter Kovacs

Attachment: 68-1-cf360f758f25.patch added

Changed 10 years ago by Peter Kovacs

Attachment: 68-2-f4b5c2d5449d.patch added

Changed 10 years ago by Peter Kovacs

Attachment: 68-3-6cab2ab9d8e7.patch added

Changed 10 years ago by Peter Kovacs

Attachment: 68-4-a3de05c56e7e.patch added

Changed 10 years ago by Peter Kovacs

Attachment: 68-5-6959186d3612.patch added

Changed 10 years ago by Peter Kovacs

Attachment: 68-6-2d82f9560e1a.patch added

Changed 10 years ago by Peter Kovacs

Attachment: 68-7-4cad1981d18d.patch added

Changed 10 years ago by Peter Kovacs

Attachment: 68-8-afad5d01ef8e.patch added

comment:5 Changed 10 years ago by Peter Kovacs

I attached 8 patches for StaticDigraph, some of which really needs revision.

  • [cf360f758f25] Port StaticDigraph from SVN -r3524.
  • [f4b5c2d5449d] Small improvements + add tests for StaticDigraph. These improvements are the followings:
    • The built or not built status of the structure is designated by a bool flag instead of setting node_num to -1, to keep nodeNum() correct for the empty structure, as well.
    • Some functions have to be repeated from DigraphExtender to support the tests correctly.
  • [6cab2ab9d8e7] Add documentation for StaticDigraph.
  • [a3de05c56e7e] Remove the outgoing arc list from StaticDigraph to save one int value for each arc. The list was used only by the basic iteration interface, i.e. the nextOut(Arc&) function, but it can be implemented easily and efficiently without the outgoing arc list, as well. This modification makes the basic interface (namely nextOut(Arc&)) about 15 percent slower, but this interface is hardly used. However it reduces the number of stored integers from 2n+4m to 2n+3m, and it makes the build() function slightly faster.
  • [6959186d3612] Extend the interface of StaticDigraph with index(), arc() and node() functions similarly to other static graph structures. They are especially needed together with the next changeset.
  • [2d82f9560e1a] Add a new build() function to StaticDigraph. This function builds the digraph from an arc list that contains pairs of integer indices from the range [0..n-1]. It is useful in the cases when you would like to build a StaticDigraph from scratch, i.e. you do not want to build another digraph that could be copied using the other build() function. Node and arc references are not important in this case, since the nodes and arcs can be indexed using the functions introduced in the former changeset. I think, this changeset greatly improves the usability of StaticDigraph.
  • [4cad1981d18d] Add tags to provide smaller iterator classes (#68, #252). This changeset should be merged with the one in #252.
  • [afad5d01ef8e] Simplify StaticDigraph::OutArcIt implementation. It works with arc IDs instead of arcs and there are no function calls in operator++(). Using gcc with -O2 and -O3, it makes the iterator only 1-2 percent faster. Thus this modification is questionable.

For benchmark results see #309.

comment:6 Changed 10 years ago by Peter Kovacs

Could anyone tell me why it is important to sort the outgoing arcs of a node with respect to their target nodes during building a StaticDigraph? It makes the build() function about 15 percent slower, but is there any significant advantage? Could it make such algorithms faster that uses node maps and reads data for the target nodes of outgoing arcs?

comment:7 in reply to:  5 Changed 10 years ago by Peter Kovacs

Replying to kpeter:

  • [afad5d01ef8e] Simplify StaticDigraph::OutArcIt implementation. It works with arc IDs instead of arcs and there are no function calls in operator++(). Using gcc with -O2 and -O3, it makes the iterator only 1-2 percent faster. Thus this modification is questionable.

I would like to withdraw this changeset, since the original interface is similar to the base iterator interface, thus it is better if someone would like to use StaticDigraph with the "low-level syntax".

Consider to apply only the first seven changesets.

Changed 10 years ago by Peter Kovacs

Attachment: 68-5-new-eff1caf6d32e.patch added

Changed 10 years ago by Peter Kovacs

Attachment: 68-6-new-5764dd9b6e18.patch added

Changed 10 years ago by Peter Kovacs

Attachment: 68-7-new-05b444bfc02b.patch added

comment:8 Changed 10 years ago by Peter Kovacs

I reworked the patches. The first three (namely [cf360f758f25], [f4b5c2d5449d], [6cab2ab9d8e7]) remained unchanged. The one that removes out-arc lists ([a3de05c56e7e]) turned out to be really questionable, since all adaptors use the base iterator interface (and some other core tools, as well). So I rebased the later changesets on the top of [6cab2ab9d8e7].

The new changesets:

comment:9 Changed 10 years ago by Peter Kovacs

Other forms of the proposed build() function could be imagined. E.g. we could introduce build(n,m,begin) as an alternative to build(n,begin,end). (And the latter one could simply call the other one as build(n, std::distance(begin, end), begin)).

Apart from that I would like to make sort() in the old build() function optional. What do you think about it? Which one should be the default option?

Changed 10 years ago by Peter Kovacs

comment:10 Changed 10 years ago by Peter Kovacs

[a143f19f465b] makes some graph member functions static. It modifies StaticDigraph as well as other graph types.

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

Replying to kpeter:

[a143f19f465b] makes some graph member functions static. It modifies StaticDigraph as well as other graph types.

I can't see how these changes are related to #311.

comment:12 in reply to:  11 Changed 10 years ago by Peter Kovacs

Replying to alpar:

I can't see how these changes are related to #311.

It contains various Improvements for graphs and this ticket is clearly animprovement for graphs. :) In fact, the relation is historical. I wanted to attach this patch to #311 (when it was still open), but it seemed better to apply these changes to StaticDigraph as well, thus I decided to attach it here.

I added a note to #311 about this patch, so the realtion is clear now. :)

comment:13 Changed 9 years ago by Peter Kovacs

All the relevant changesets went to the main branch.

Only one question left here:

I would like to make sort() in the old build() function optional. What do you think about it? Which one should be the default option?

comment:14 in reply to:  13 Changed 9 years ago by Peter Kovacs

Resolution: done
Status: assignedclosed

Replying to kpeter:

Only one question left here:

I would like to make sort() in the old build() function optional. What do you think about it? Which one should be the default option?

I made a follow-up ticket about this question, see #329.

Thus this ticket can be closed.

Note: See TracTickets for help on using tickets.