Lemon Graph Library C++ - Directed Graph

Question

I am looking at Lemon to handle my pathfinding, since it has search and shortest paths algorithms, among other things.

The thing is, I am already stuck right at the start in understanding how Lemon works, and they have a tutorial but no forum to ask.

My understanding of a directed graph is that you have a node, and it can link or not link to another node and then you have a weight on it.

Example:

     A    B    C
A    0    1    0
B    1    0    5
C    0    0    0

In this, A is connected to B with a weight of 1, C is connected to nothing (so once you get to C you are stuck), and B connects to A with a value of 1 and B connects to C with a value of 5.

The tutorial says to do something like this:

ListDigraph g;
ListDigraph::Node A = g.addNode();
ListDigraph::Node B = g.addNode();
ListDigraph::Node C = g.addNode();

So now I have a graph g with the three nodes. Now what? Where / how do I add the connectivity information as well as the weight values?

Answer 1

From the Lemon tutorial

  ListDigraph g;

  ListDigraph::Node x = g.addNode();
  ListDigraph::Node y = g.addNode();
  ListDigraph::Node z = g.addNode();

  g.addArc(x,y);
  g.addArc(y,z);
  g.addArc(z,x);

Never used this library mind, I'm just quoting what I've read.

Answer 2

LEMON uses slightly different terminology than most graph theory texts, but in my opinion that makes using the library a bit easier.

Firstly, the difference between an edge and an arc in LEMON is simply that an edge is an undirected edge between two nodes, and an arc is a directed edge.

---

As for adding edges and weights and whatnot, graphs themselves only manage nodes and edges/arcs, the only data associated with each is an integral identifier.

You can find this identifier using:

graph.id(node);

To attach pieces of data to the nodes/edges, you use maps. There are a few different types of maps, but they generally boil down to a NodeMap, EdgeMap, or ArcMap - and, as you probably guessed, they are associative maps of <Node, V>, <Edge, V> and <Arc, V>, respectively, where V is the value type (which can be anything that has a default constructor).

---

To add edges (in an undirected graph) or arcs (in a digraph), you simply create the two nodes and then use .addEdge(n1, n2) or .addArc(n1, n2).

For example:

ListDigraph graph;

ListDigraph::Node n1 = graph.addNode();
ListDigraph::Node n2 = graph.addNode();

ListDigraph::Arc a = graph.addArc(n1, n2);

And to associate a some value with that arc:

ArcMap<std::string> arcMap;

arcMap[a] = "This is an arc value!";