Port static graph implementation

[Alpar Juttner]

Namely the file

• lemon/static_graph.h

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

[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?

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

[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:

• [eff1caf6d32e] Extend the interface of StaticDigraph (#68)
  A rebased version of [6959186d3612].
• [5764dd9b6e18] Add a new build() function to StaticDigraph (#68)
  It is similar to [2d82f9560e1a] with the exception that it uses a range of iterators as an input instad of an STL contanier.
• [05b444bfc02b] Add tags to provide smaller iterator classes (#68, #252)
  A rebased version of [4cad1981d18d] for merging with #252.

[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?

[Peter Kovacs]

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

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

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

[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?

[Peter Kovacs]

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.