[Lemon-user] Graphs need first and next?

[Kovács Péter]

Hi,

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

Yes, iterator classes are mainly for convenience.

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

We also thought of this design once, but we kept the current design from 
LEMON 0.x series. However, note that such template iterator (and map) 
classes could be added to LEMON as alternative tools without any 
conflict. Actually, I have already implemented such classes as part of a 
proposal in ticket #252, see:
http://lemon.cs.elte.hu/trac/lemon/attachment/ticket/252/252-b483e15fab8e.patch

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

Or you could use this condition:
gr.oppositeArc(a) == b

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

I don't see how could you apply a similar idea for an undirected 
3-regular graph even without the requirement of the Arc->Edge 
converison. I cannot think of an appropriate numeric transformation 
between the ranges 0..3*N/2-1 and 0..N-1 that could yield a certain end 
node of an edge. Not that continous numbering for the incident edges of 
each node is not possible.

As far as I see, you have to leave this design. Another idea is to use 
the range 0..3*N-1 for the arcs in such a way that the corresponding 
edge id for an arc id a is a/2 and the id of the oppsite arc is a^1. 
Then you could store only the target node of each arc a and use 
target[a^1] for the source. The two end nodes of an edge e is 
target[2*e] and target[2*e+1]. Apart from that, you should store the 
outgoing arc list for each node. Up to this point, this idea could be 
used for any undirected graph (ListGraph and SmartGraph also applies 
this solution). For 3-regular graphs, the outgoing arc list could be 
efficiently stored in an int array/vector out of size 3*N so that:
   - outgoing arcs of u: out[u], out[u+1], out[u+2]
   - incomming arcs of u: out[u]^1, out[u+1]^1, out[u+2]^1
   - incident edges of u: out[u]/2, out[u+1]/2, out[u+2]/2

Best regards,
Peter