[Lemon-user] Build Static Graph from ListGraph and maintain node ids

[Kovács Péter]

Dear Zenna,

> Hi there
>
> I have just started using lemon for fairly large graph algorithms but
> have some questions.
>
> 1. Is there no undirected static graph?

No, there isn't. However, SmartGraph certainly meets your requirements.
Because of the special structure of an undirected graph, we could not 
implement a StaticGraph that is faster than SmartGraph. That's why it is 
missing.

In case of directed graphs, StaticDigraph is smaller and could be 
slightly faster than SmartDigraph, but the differences are typically 
small. However, the differences between the efficiency of the List and 
Smart implementations are much larger. So consider to use Smart(Di)Graph 
instead of List(Di)Graph whenever you don't need to remove nodes and 
edges/arcs from the graph.

> 2. How can I build a static graph from a a normal graph and maintain
> the id of the nodes.  In other words, the node ids of the the original
> graph will correspond to the same same nodes (with the same
> connections) in the static graph

The recommended way is to use DigraphCopy (GraphCopy for undirected 
graphs). It works for all general graph types (List, Smart, Static). It 
does not ensure any relation between the node/arc ids in the two graph 
structures, but it can create reference maps for the items. For more 
information, see
http://lemon.cs.elte.hu/pub/doc/1.2/a00100.html

Actually, you can copy a SmartDigraph to a StaticDigraph strucutre 
ensuring equal ids for the corresponding nodes, but is not so nice and 
safe as the above solution.

Another alternative is to build up a StaticDigraph structure directly 
(without any graph copy). For this, you can use this build() function of 
the class:
http://lemon.cs.elte.hu/pub/doc/1.2/a00341.html#52bc4ff72c4cd954b5e54b36b5e6972a

> I am looking to use a static graph because it seems that iterating
> through edges can become painfully slow on a normal graph.

Did you also try SmartGraph? It is much faster than ListGraph in this sense!

> I would also like to note that I learned most how to use lemon by
> searching through the tests.

Nice. Was it your first step or did you study our tutorial first?
http://lemon.cs.elte.hu/pub/tutorial/

Regards,
Peter