[Lemon-user] EdgeLookup for SmartGraph

[Goldberg, Noam]

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.

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

For all other purposes LEMON seems to be a great source of graph algorithms and utilities (such as reading and writing to files etc) but some basic graph operations seem to be a little awkward.

Am I missing something?  (is your design this way because you provide faster arc insertion and deletion than O(d) within the (di)graph objects)

I think that it would be nice to have some general guideline description (e.g., a couple of paragraphs on the main web page or documentation) of both the interface design "philosophy" behind LEMON and the run time complexity of basic operations.

Best regards,
Noam

________________________________________
From: Alpár Jüttner [alpar at cs.elte.hu]
Sent: Saturday, May 23, 2009 1:24 PM
To: Goldberg, Noam
Cc: lemon-user at lemon.cs.elte.hu
Subject: Re: [Lemon-user] EdgeLookup for SmartGraph

On Fri, 2009-05-22 at 19:21 -0400, Goldberg, Noam wrote:
> There is an object called ArcLookUp which is seems to be really used to
>  implement the one simple procedure of finding an Arc of a directed
>  graph by its endpoints.

In fact, it is a bit more than that. It finds an Arc between two nodes
(u,v) in O(log d) steps (d is the number of outgoing arcs of u), which
can be much faster than a simple linear search, especially for dense
graph.

Regards,
Alpar