[Lemon-user] Graphs need first and next?

[Ben Strasser]

Hello,
>> 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. 
Is there a rational for this decision? Is it for backward compatibility?
>> 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
>   
The point is that the expression I wrote does not involve the graph 
object. Every undirected graph must have implemented Arc in a way that 
are_opposite(a, b) can be decided *without* looking at the graph object. 
This hinders every design where Arc stores the information "the n-th 
outgoing edge of node v". IMHO this is quite a restriction.

At the moment I work around the problem by letting Arc store 2 arc ids 
:  the forward and the backward arc. The edges are identified using the 
corresponding arc with the smaller id. The edge ids are not continuous. 
This is however no problem as I do not really need edge maps.

My design only needs a single int array of size 0..3*N-1. It basically 
stores the opposite arc for every arc.

outgoing arcs of u: 3*u, 3*u+1, 3*u+2
source of arc a: a/3
incoming arcs: opposite[3*u], opposite[3*u+1], opposite[3*u+2]
target of arc a: opposite[a]/3
arc a to edge: min(a, opposite[a])
direct edge e in true sense: e
direct edge e in false sense: opposite[e]

Given an outgoing arc a I can find the all the outgoing arcs of the same 
source node using:
3*(a/3), 3*(a/3)+1, 3*(a/3)+2

Using your design I need:
u = target[a^1]
out[u], out[u+1], out[u+2] // one memory access because of cache locality

That's none vs 2 memory accesses.

Because of my current Arc implementation, my code needs an unnecessary 
access to fetch all those opposite arcs. I will probably replace the 
backward arc using a pointer to the opposite array and hope the 
optimizer takes care of the situations where this costs something.

Best regards,
Ben