[Lemon-user] Graphs need first and next?

[Kovács Péter]

Hi Ben,

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

This question is merely a trade off between the different operations of 
your graph structure. Your idea provides faster iteraion for Arcs and 
faster access to the source node of an arc, but the Edge iteration and 
the conversions between Arc and Edge objects are slower (and the edge 
maps are twice as large). E.g. the EdgeIt iteration could be implemented 
like that:
   min(a, opposite[a])  for all a in 0..3*N-1
compared to:
   e  for all e in 0..3*N/2-1
using continuous edge ids.

Actually, you can choose the design which fits your requirements more.

> 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

Peter