[Lemon-user] EdgeLookup for SmartGraph

[Kovács Péter]

Hi,

I'm trying to explain some basic concepts and design decisions.

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

Certainly. :)

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

Note that there are several graph structures in LEMON, which can serve 
entirely different purposes. E.g. general (di)graph structures 
(ListDigraph, ListGraph etc.), special graph structures (FullGraph, 
GridGraph etc.), graph adaptors, arc/edge set classes. The basic 
concepts and tools must apply to _all_ of them, although they are 
implemented variously. This is the main reason for the design decisions 
you are talking about.

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

Some basic tools are separated from the concrete graph classes, since 
they can be implemented in the same way for all structures. There are 
general implementations that apply to _all_ graph structures (including 
sophisticated adaptors), but they are specialized for those classes that 
can support faster implementation.

A good example is counting nodes/arcs. A general graph structure could 
easily store and update these numbers, so countNodes() and countArcs() 
are typically O(1) for them. However consider the FilterNodes adaptor, 
in which you can hide/show nodes by simply switching a bool value in a 
node map. For this class countArcs() is an O(e) function (it traverses 
all the arcs), since the adaptor does not maintain this number.

Similar ideas apply to arc/edge lookup. They are implemented in
O(d) and O(log d) time for Smart/List graph classes (using findArc() 
function or ArcLookup classes, respectively), but e.g. they are 
implemented in O(1) time for FullDigraph and FullGraph, instead of
O(log n) (using findArc() function).

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

Firstly, the basic concepts and tools must apply to _all_ graph 
structures. Secondly, O(1) time node/arc insertion and deletion are 
ensured for e.g. ListDigraph, and traversing the outgoing/incoming arcs 
should be as fast as possible.

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

Definitely. A good tutorial should be written, which should provide such 
explanations, too. We are planning this, but up to now, we did not have 
enough time for that. Any contribution is welcomed!
http://lemon.cs.elte.hu/pub/tutorial/

Regards,
Peter


 > ________________________________________
 > 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
 >
 > _______________________________________________
 > Lemon-user mailing list
 > Lemon-user at lemon.cs.elte.hu
 > http://lemon.cs.elte.hu/mailman/listinfo/lemon-user