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
[email protected]
http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
_______________________________________________
Lemon-user mailing list
[email protected]
http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
