[Lemon-devel] Design decision for graph concept: firstInc/nextInc vs. IncEdgeIt

[Matthias Walter]

Dear Alpar,

On 11/18/2013 10:07 AM, Alpar Juttner wrote:
>> I recently tried to create a graph adaptor class but had the following
>> problem: When iterating over the edges incident to a node, I am not able
>> to find the next edge *only* based on the previous edge (and its
>> direction flag), hence I am unable to implement the nextInc() method
>> properly. On the other hand an IncEdgeIt iterator is easy to implement
>> since the latter might store additional information which helps to find
>> the next edge quickly. But now I saw that in order to use this adapted
>> graph for another adaptor (like FilterNodes) I need the firstInc/nextInc
>> methods to be implemented although these are not explicitly listed in
>> the Graph concept documentation.
>>
>> Is it a particular design decision that e.g. SubGraphBase uses the
>> firstInc/nextInc interface instead of iterators?
>>
>> Or is nextInc() typically more efficient than having a comparable iterator?
> 
> One can imagine three different kinds of Edge object/iterator
> 
>      1. One that is able to uniquely identify an edge.
>      2. One that is able to identify and edge and also the graph object
>         can calculate the next ones.
>      3. One that can do the iteration in itself.
> 
> Type 3 is the most convenient for iterating over the edges, because you
> can use the usual ++ operator. However it is most often needs an extra
> data field (a reference to the graph), and also there are several
> different Type 3 objects (e.g ArcIt, InArcIt, OutArcIt) corresponding to
> a singe Type 1 (Arc).

I understand the design decisions and just want to point out what comes
to my mind: A 4th variant would be to have 3 but with the restriction
that iteration needs the graph reference in addition, so one wouldn't
need to carry the latter around. The first/next interface would be
Graph::next(EdgeIt&) but it wouldn't allow for operator usage.

> In LEMON, we consider Type 2 = Type 1, that is we assume that the graph
> will be able to calculate the (different kind of) next edges from the
> Edge class (using different next*() member functions). It covers most of
> the use cases and has the huge advantage that the verbose interface of
> the Type 3 iterators can be implemented automatically with the *Extender
> classes. It also allows *EdgeIt->Edge conversion, which has efficiency
> implication when you have to store many iterators (think of BFS).
> 
> So, LEMON doesn't support the extra structures when "calculating the
> next" needs more info then just "identifying one". To be honest, I
> cannot even see a neat concept that would handle this case while keeping
> the above advantages of current concept.
> 
> Isn't it possible to put the necessary extra info directly into the Edge
> class in your case?

In fact I think the answer is NO - but this somehow indicates that maybe
a graph adaptor is not the right choice since it's too complicated. My
goal was to write one that allows node set contractions on a graph by
storing necessary auxiliary information used to work on the contracted
graph more efficiently. The problem appeared since for some edge sets
(e.g., the set of incident edges of a contracted node) I need to
traverse the recursive family of contractions in which this node is
involved and obtain some edges from each of these contractions. But
clearly, a single edge doesn't know at which point in this traversal we are.

So thank you very much for the detailed information!

Best regards,

Matthias