[Lemon-user] Graphs need first and next?

[Ben Strasser]

Hello,

thanks for explaining this. If I have to implement them then I do not 
really understand why the iterators are needed at all. Do they provide 
anything except syntax sugar? If not then why make them part of every 
graph interface? An alternative would have been a template 
NodeIt<MyGraphType>. As a sideeffect generic code needs a lot less 
typenames.

Another thing that caused me a lot of problems is the fact that Arcs are 
implicitly convertible to Edges. Given a simple undirected graph and two 
arcs a and b I can decide using

G::Edge(a) == G::Edge(b) && a != b

whether the two arcs are opposite. Using the data layout I originally 
wanted to implement it is however unfortunately not possible to decide 
this without having access to the graph object.

I wanted to write an optimized graph to store 3 regular graphs. The 
nodes are represented using ints in the range 0..node_count-1 and and 
arcs using ints in the range 0..3*node_count-1. Let a be an arc id then 
id/3 is the source node id and id%3 is the index of the outgoing arc. 
This means that a node v has the outgoing arcs 3*v, 3*v+1 and 3*v+2. 
This allows one to efficiently implement maps and leads to very compact 
handles. Unfortunately it only works for directed graphs because of the 
restriction mentioned above.

Best regards,
Ben