[Lemon-user] Thread safety and other issues

[Alpár Jüttner]

Hi Zenna,


> 
> 1. Thread safety of data structures.  I have read this issue
> http://lemon.cs.elte.hu/trac/lemon/ticket/224 last modified 15 months
> ago. 

This is indeed a shame.

>  Has this been resolved,

Unfortunately this issue hasn't been resolved yet, mainly because of a
lack of a major driving force. So, repeated requests will certainly
speed up the process.

>  can I run dijisktra's algorithm on the same graph in parallel?  If
> not will I need to implement my own graph structure, dijisktra
> algorithm or both?

The only point where the graph data structures are not thread safe is
when you allocate new graph-maps. Dijkstra only does it in his init()
member function. So a workaround you can do is to split dij.run(s) into
a sequence of

dij.init();
dij.addSource(s);
dij.start();

You must make sure that init() functions of each Dijkstra instance is
run sequentially, but then addsource() and start() calls of different
instances can safely be made in parallel.

> 2. From a subset of nods of a graph, I want to find all a pairwise
> distances (note: this is AFAIK not the same as Floyd Warshall as I
> don't look at ALL nodes in the graph).  At the moment I am running
> dijisktra's on all pairs N(N-1)/2 within my subset.  Do you know of
> any more efficient method? 

Dijkstra is able to find the shortest path from a given source to all
destinations in a single run. So N executions are enough to compute all
the pairwise shortest paths.
> 
> 3. Is lemon::findEdge linear in the number of nodes?

lemon::findEdge(a,d) simply iterates through the edges of node a, thus
its running time is linear in the degree of node a.

>   I am using a static graph, and it seems to be occupying most of my
> runtime.  (I use it to check an edge has not already been added,
> before adding)

You may want to give a try to one of the ArcLookUp tools. Most probably
DynArcLookUp (http://lemon.cs.elte.hu/pub/doc/1.2.1/a00120.html ) is
your choice, but is you look up a lot, but add new edges rarely, the
ArcLookup (http://lemon.cs.elte.hu/pub/doc/1.2.1/a00025.html ) with
manually refresh()-ing, the datastructure might be faster.

If it is still too slow, I would suggest pre-filtering your queries with
some simple hashing technique.

> 4. In my lab we have built a fairly comprehensive complex network
> analysis toolkit around the lemon library, we intend to release it
> soon and hope it will be useful for others.

This sound really great!

Regards,
Alpar