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

[Szabolcs Horvát]

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}}; // already sorted

StaticDigraph digraph;

digraph.build(3, edges.begin(), edges.end());


If I want a ListGraph, I believe I could do this:

ListGraph lg;

IdMap<ListGraph, ListGraph::Node> nodeMap(lg);

auto inverseMap = nodeMap.inverse();

for (int i=0; i < 3; ++i)

    lg.addNode();

for (const auto &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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20180523/0fe4e560/attachment.html>