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

[Alpar Juttner]

Dear Matthias,


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

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?

Regards,
Alpar