[Lemon-user] How do I build a graph from an edge list?

[Péter Kovács]

Hi Szabolcs,

There are multiple ways to build a ListGraph or SmartGraph, but 
basically you should add the nodes and edges one by one. Your code is 
correct and efficient. A simpler way would be to put the nodes into an 
std::vector when you create them by addNode(), and then use this vector 
instead of the inverseMap of your code. Or you could also use the 
nodeFromId() method of the graph for the same purpose.

 > Is there a better way to look up nodes by ID?  Should I be using 
RangeIdMap instead, or will that get messed up during the process of 
adding nodes and edges?  With IdMap, will the node ID always be n-1 for 
the nth node added?  What about RangeIdMap?

RangeIdMap always provides IDs in the range [0..n-1], even if you remove 
nodes and edges (it won't get messed up). In contrast, IdMap is more 
efficient, but may provide IDs that do not form a continuous range if 
you use ListGraph and some nodes/edges are removed. If you only add 
nodes/edges, the ID range will be [0..n-1] for both maps and for both 
graph types.

Instead of IdMap, you can also use the appropriate methods of the graph 
classes directly (id(), nodeFromId(), edgeFromId()). Note that these 
methods are common to all graph classes, they are part of the Graph concept:
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00183.html

Regards,
Péter


On 2018-05-23 09:23, Szabolcs Horvát wrote:
> Hello everyone,
>
> I am still new to Lemon, and not very confident with its concepts.  I 
> would like to know the "proper" way to construct a ListGraph or 
> SmartGraph from a list of edges.
>
> For simplicity, support the edges are given as an std::vector of 
> std::pair<int,int>.  Then it is very easy to build a StaticDigraph.
>
> vector<pair<int,int>>edges={{0,1},{1,0},{1,2}};//alreadysorted
> StaticDigraphdigraph;
> digraph.build(3,edges.begin(),edges.end());
> If I want a ListGraph, I believe I could do this:
>
> ListGraphlg;
> IdMap<ListGraph,ListGraph::Node>nodeMap(lg);
> autoinverseMap=nodeMap.inverse();
> for(inti=0;i<3;++i)
> lg.addNode();
> for(constauto&edge:edges)
> lg.addEdge(inverseMap[edge.first],inverseMap[edge.second]);
> Is this the best way to do it?  Is there a simpler or faster way?  Do 
> I really need to call .addNode() as many times as the number of 
> nodes?  Is there a better way to look up nodes by ID?  Should I be 
> using RangeIdMap instead, or will that get messed up during the 
> process of adding nodes and edges?  With IdMap, will the node ID 
> always be n-1 for the nth node added? What about RangeIdMap?
>
> Thanks for any advice in advance.
>
> Szabolcs
>
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20180523/81e6d77a/attachment-0001.html>