[Lemon-user] EdgeLookup for SmartGraph

[Alpár Jüttner]

On Tue, 2009-05-26 at 11:02 -0400, Goldberg, Noam wrote:
> I do not know how the basic data structures are implemented in LEMON; I
>  am sure the developers had a good reason at the time they designed it
>  that way.

It's all about running time and memory efficiency.
Node/arc iterations (and the map access) are by far the most frequent
operations in the common graph algorithms, while we very rarely need to
look up an arc between two vertices. (In fact, you cannot find a single
example for this operation in the algorithms implemented in LEMON.)

Therefore LEMON is aggressively optimized for iterations, map access and
small memory footprint (which in turn have a strong effect on the
running time, due to the caching performance). Other graph libraries
basically use the same approach.

> However, if I were to implement a graph object I would probably do it
>  using adjacency list structure that could easily give you access to
>  arcs in O(d) time.
>
> In STL language that I like to use a graph is represented as a
> vector< set <node Id >    >
>  or possibly 2 such structures one for fast access to outgoing arcs and one for incoming arcs.
> ArcLookup is O(log d) using this simple structure without having to
> write much code and as a simple method of
> the (di-)graph object (without adding any static objects).


It would be possible to do it, but remember "there is no free lunch".
The price of this would be 
      * much slower build-up and modification of graphs.
      * plus the much bigger memory footprint of the graphs (which may
        also slow down some algorithms).

That's why ArcLookUp is implemented as a separate tool. It would be a
bit simpler-to-use if it were a built in feature of the graphs, but it
is still quite comfortable. Anyway, as far I know, the other graph libs
do not provide this feature at all, neither built in the graph nor as a
separate tool.

Best regards,
Alpar