4 Algorithms

Todo:
This page is under construction.

This section should be revised and extended.

In addition to the graph structures, the most important parts of LEMON are the various algorithms related to graph theory and combinatorial optimization. The library provides quite flexible and efficient implementations for well-known fundamental algorithms, such as breadth-first search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm and methods for discovering graph properties like connectivity, bipartiteness or Euler property, as well as more complex optimization algorithms for finding maximum flows, minimum cuts, matchings, minimum cost flows etc.

In this section, we present only some of the most fundamental algorithms. For a complete overview, see the Algorithms module of the reference manual.

4.1 Graph Search

The common graph search algorithms, namely breadth-first search (BFS) and depth-first search (DFS) are implemented in highly adaptable and efficient algorithm classes Bfs and Dfs. In LEMON, the algorithms are typically placed in separated files, which are named after the algorithm itself but with lower case like all other header files. For example, we have to include bfs.h for using Bfs.

   #include <lemon/bfs.h>

Basically, all algorithms are implemented in template classes. The template parameters typically specify the used graph type (for more information, see 8 Graph Structures) and the required map types. For example, an instance of the BFs class can be created like this.

  ListDigraph g;
  Bfs<ListDigraph> bfs(g);

This class provides a simple but powerful interface to control the execution of the algorithm and to obtain all the results. You can execute the algorithm from a given source node by calling the run() function.

  bfs.run(s);

This operation finds the shortest paths from s to all other nodes. If you are looking for an s-t path for a certain target node t, you can also call the run() function with two parameters. In this case, the BFS search will terminate once it has found the shortest path from s to t.

  bfs.run(s,t);

By default, the distances and the path information are stored in internal maps, which you can access with member functions like distMap() and predMap() or more directly with other member functions like dist(), path(), predNode(), predArc(). Once the execution of the algorithm is finished, these query functions can be called.

For an example, let us say we want to print the shortest path of those nodes that are at most in a certain distance max_dist. 

bfs.run(s);

for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
  if (bfs.reached(n) && bfs.dist(n) <= max_dist) {
    std::cout << gr.id(n);
    Node prev = bfs.prevNode(n);
    while (prev != INVALID) {
      std::cout << "<-" << gr.id(prev);
      prev = bfs.prevNode(n);
    }    
    std::cout << std::endl;
  }
}

The class interfaces of the algorithms also support a finer control on the execution. For example, we can specify more source nodes and we can even run the algorithm step-by-step. If you need such control on the execution, you have to use more functions instead of run(). First, you have to call init() to initialize the internal data structures.

  bfs.init();

Then you can add one or more source nodes to the queue with addSource(). They will be processed, as they would be reached by the algorithm before. And yes, you can even add more sources during the execution.

  bfs.addSource(s1);
  bfs.addSource(s2);
  ...

Finally, the actual path computation of the algorithm can be performed with the start() function.

  bfs.start(t);

Instead of using start(), you can even execute the algorithm step-by-step, so you can write your own loop to process the nodes one-by-one. For example, the following code will executes the algorithm in such a way, that it reaches all nodes in the digraph, namely the algorithm is started for each node that is not visited before.

  bfs.init();
  for (NodeIt n(g); n != INVALID; ++n) {
    if (!bfs.reached(n)) {
      bfs.addSource(n);
      bfs.start();
    }
  }

bfs.start() is only a shortcut of the following code.

  while (!bfs.emptyQueue()) {
    bfs.processNextNode();
  }

Todo:
Write about function-type interfaces
Since the DFS algorithm is very similar to BFS with a few tiny differences, the Dfs class can be used similarly to Bfs.

4.2 Shortest Paths

If you would like to solve some transportation problems in a network, then you will most likely want to find shortest paths between nodes of a graph. This is usually solved using Dijkstra's algorithm. The following code is a simple program using the LEMON Dijkstra class through the function-type interface dijkstra(). It calculates the shortest path between node s and t in a digraph g.

  dijkstra(g, length).distMap(dist).run(s,t);

In LEMON, the algorithms are implemented basically as classes, but for some of them, function-type interfaces are also available for the sake of convenience. For instance, the Dijkstra algorithm is implemented in the Dijkstra template class, but the dijkstra() function is also defined, which can still be used quite flexibly due to named parameters.

The above sample code could also use the class interface as follows.

  Dijkstra<ListDigraph> dijkstra(g, length);
  dijkstra.distMap(dist);
  dijsktra.init();
  dijkstra.addSource(s);
  dijkstra.start();

The previous code is obviously longer than the original, but the execution can be controlled to a higher extent. While using the function-type interface, only one source can be added to the algorithm, the class interface makes it possible to specify several root nodes. Moreover, the algorithm can also be executed step-by-step. For instance, the following code can be used instead of dijkstra::start().

  while (!dijkstra.emptyQueue()) {
    ListDigraph::Node n = dijkstra.processNextNode();
    cout << g.id(n) << ' ' << dijkstra.dist(g) << endl;
  }

LEMON provides several other algorithms for findign shortest paths in specific or more general cases. For example, BellmanFord can be used instead of Dijkstra when the graph contains an arc with negative cost. You may check the Shortest Path Algorithms module of the reference manual for more details.

4.3 Maximum Flows

See Preflow.

Todo:
Write this subsection.
<< 3 Basic Concepts | Home | 5 Undirected Graphs >>
doxygen