LEMON Graph Library
LEMON stands for Library for Efficient Modeling and Optimization in Networks. It is a C++ template library providing efficient implementations of common data structures and algorithms with focus on combinatorial optimization tasks connected mainly with graphs and networks.
http://lemon.cs.elte.hu/trac/lemon
I like LEMON because of its nice and simple API. There is also a mailing list which offers quick support. Its latest version 1.3.1 was updated in August 2014.
So let’s see what’s on the agenda:
- Prerequisites
- Populate a graph
- Setup a shortest path solver
- Solve it, get the cost and the path
1. Prerequisites
For simplicity I put all the code into a single file: main.cpp.
First we have to define a couple of includes in order to use the functionality of LEMON.
// c++ STL containers #include <vector> #include <map> #include <string> // LEMON #include "lemon/smart_graph.h" #include "lemon/dijkstra.h"
In my example I use the SmartDigraph class of LEMON because it provides more efficiency than the ListDigraph and I don’t have the need of removing nodes or arcs.
You can choose between several graph representations with LEMON – both directed and undirected ones.
Have a look in the LEMON tutorials for more information.
Next we instantiate our Graph.
//instantiate directed smart graph lemon::SmartDigraph g;
For the Dijkstra Class we need a container with costs on each arc of the graph. This is done with a so called LEMON Map. Any attribute on a graph’s arc or node is held in additional containers that are indexed from the arc’s or node’s ids. So the graph class stores only indexes but not extra information. This is called the LEMON Map Concept.
So for the costs (or weights) of the arcs of the graph we need an ArcMap (sounds familiar for ESRI ArcGIS users..) which has a template parameter for the data type of the costs (integer, double, etc.). This class depends of the graph type, so we define it like that:
//instantiate a LEMON map of arc costs lemon::SmartDigraph::ArcMap<double> costMap(g);
Same procedure on the nodes side:
lemon::SmartDigraph::NodeMap<std::string> nodeMap(g);
Now I a little map to hold the information about external node ID and the internal node index. Additionally I use a struct that represent an arc of the graph.
struct Arc
{
std::string sourceID;
std::string targetID;
double cost;
};
std::map<std::string, int> nodes = {
std::make_pair("A",0),
std::make_pair("B",1),
std::make_pair("C",2),
std::make_pair("D",3),
std::make_pair("E",4),
std::make_pair("F",5)
};
std::vector<Arc> arcs = { Arc {"A","B",4},
Arc {"A","C",2},
Arc {"B","D",10},
Arc {"B","C",5},
Arc {"C","E",3},
Arc {"E","D",4},
Arc {"D","F",11}
};
Because of the template mechanism of LEMON and its inherent verbosity it’s simpler to define a type of the shortest path solver with a using-statement once.
Note that defined the Dijkstra Class with the graph type and the type of the cost map.
// defining the type of the Dijkstra Class using SptSolver = lemon::Dijkstra<lemon::SmartDigraph, lemon::SmartDigraph::ArcMap<double>>;
Now we’re ready to poulate the graph.
2. Populate the graph
We populate a graph with two functions of the graph: addNode() and addArc().
So we iterate over our node vector and do two things: call addNode() which gives us a LEMON Node object and populate the nodeMap with the current node as the key and the name of the node from the vector as the value of the LEMON node map.
//populate graph
//nodes first
SmartDigraph::Node currentNode;
for (auto nodesIter = nodes.begin(); nodesIter != nodes.end(); ++nodesIter)
{
string key = nodesIter->first;
currentNode = g.addNode();
nodeMap[currentNode] = key;
}
//then the arcs with the costs through the cost map
SmartDigraph::Arc currentArc;
for (auto arcsIter = arcs.begin(); arcsIter != arcs.end(); ++arcsIter)
{
int sourceIndex = nodes.at(arcsIter->sourceID);
int targetIndex = nodes.at(arcsIter->targetID);
SmartDigraph::Node sourceNode = g.nodeFromId(sourceIndex);
SmartDigraph::Node targetNode = g.nodeFromId(targetIndex);
currentArc = g.addArc(sourceNode, targetNode);
costMap[currentArc] = arcsIter->cost;
}
So now we are ready for #3: setup the shortest path solver.
3. Setup a shortest path solver
First we need a start and an end node, so let’s say we want to know the shortest path from node „A“ to „E“. Then we instantiate the Dijkstra shortest path solver.
SmartDigraph::Node start = g.nodeFromId( nodes.at("A") );
SmartDigraph::Node end = g.nodeFromId( nodes.at("E") );
SptSolver spt(g, costMap);
4. Solve it, get the cost and the path
You can start the solver simply with
spt.run(start, end);
Note that the execution stops when it reaches the end node. If you just type spt.run(start); the whole shortest path tree to all reacheable nodes from at the start node will be calculated.
Constructing the path and retrieving the cost from the shortest path solver will be as follows:
iterate over all nodes (in a special LEMON construct) and push every node in the so called predecessor shortest path tree to the path.
Lastly you retrieve the total cost from the origin to the given node via the dist() method of the Dijkstra class.
/* Walk in whole SPT is possible from specified orig and end
but dest must be part of the SPT and
an orig node must not be a dest node */
std::vector<lemon::SmartDigraph::Node> path;
for (lemon::SmartDigraph::Node v = endN; v != startN; v = spt.predNode(v))
{
if (v != lemon::INVALID && spt.reached(v)) //special LEMON node constant
{
path.push_back(v);
}
}
path.push_back(startN);
double cost = spt.dist(endN);
Because the predecessor walks from the destination node of a shortest path tree to a start node one must reverse the order of the nodes.
//print out the path with reverse iterator
std::cout << "Path from " << " to " << " is: " << std::endl;
for (auto p = path.rbegin(); p != path.rend(); ++p)
std::cout << nodeMap[*p] << std::endl;
std::cout << "Total cost for the shortest path is: "<< cost << std::endl;
So that’s all! If you wish you can control the execution of the algorithm more detailed. Please have a look in the LEMON Docs.
All the code is available on GitHub.