diff -r a5457a780c34 -r c8c5a2a4ec71 algorithms.dox --- a/algorithms.dox Mon Feb 22 02:00:51 2010 +0100 +++ b/algorithms.dox Mon Feb 22 02:03:25 2010 +0100 @@ -23,20 +23,201 @@ \todo This page is under construction. In addition to the graph structures, the most important parts of LEMON are -the various algorithm implementations, which can be used quite flexibly and -efficiently. +the various algorithms related to graph theory and combinatorial optimization. +The library probvides 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 and arc-disjoint +paths. In this section, we present only some of the most fundamental algorithms. For a complete overview, see the \ref algs module of the reference manual. [SEC]sec_graph_search[SEC] Graph Search +\todo The following contents are ported from the LEMON 0.x tutorial, +thus they have to thouroughly revised, reorganized and reworked. + See \ref Bfs, \ref Dfs and \ref graph_properties. +Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient +implementations of the well known algorithms. The algorithms are placed most cases in +separated files named after the algorithm itself but lower case as all other header file names. +For example the next Bfs class is in the \c lemon/bfs.h. + +The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function. +The class has two template parameters: \b GR and \b TR.
+GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type. +TR is a Traits class commonly used to easy the parametrization of templates. In most cases you +wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits". + +To use the class, declare it! +\code +Bfs bfs(gr); +\endcode +Note the lack of second template argument because of the default parameter. + +It provides a simple but powerful interface to control the execution. +\code +int dist = bfs.run(s,t); +\endcode +It finds the shortest path from node \c s to node \c t and returns it, or zero +if there is no path from \c s to \c t.
+If you want the shortest path from a specified node to all other node, just write: +\code +bfs.run(s); +\endcode +Now the distances and path information are stored in maps which you can access with +member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".
+Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm +is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode +"predNode()" can be called. + +For an example let's say we want to print the shortest path of those nodes which +are in a certain distance. +\code +bfs.run(s); + +for( ListGraph::NodeIt n(gr); 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; + } +} +\endcode + +In the previous code we only used \c run(). Now we introduce the way you can directly +control the execution of the algorithm. + +First you have to initialize the variables with \ref lemon::Bfs::init "init()". +\code + bfs.init(); +\endcode + +Then you add one or more source nodes to the queue. They will be processed, as they would +be reached by the algorithm before. And yes - you can add more sources during the execution. +\code + bfs.addSource(node_1); + bfs.addSource(node_2); + ... +\endcode + +And finally you can start the process with \ref lemon::Bfs::start "start()", or +you can write your own loop to process the nodes one-by-one. + + +Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example +to demonstrate Dfs's capabilities. + +We will see a program, which solves the problem of topological ordering. +We need to know in which order we should put on our clothes. The program will do the following: +
    +
  1. We run the dfs algorithm to all nodes. +
  2. Put every node into a list when processed completely. +
  3. Write out the list in reverse order. +
+ +\dontinclude topological_ordering.cc +First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering +will be done through it. +\skip MyOrdererMap +\until }; +The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing +we need to do is insert the key - that is the node whose processing just finished - into the beginning +of the list.
+Although we implemented this needed helper class ourselves it was not necessary. +The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly +what we needed. To be correct it's more general - and it's all in \c LEMON. But +we wanted to show you, how easy is to add additional functionality. + +First we declare the needed data structures: the digraph and a map to store the nodes' label. +\skip ListDigraph +\until label + +Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological +ordering. +\skip belt +\until trousers +We label them... +\skip label +\until trousers +Then add arcs which represent the precedences between those items. +\skip trousers, belt +\until ); + +See how easy is to access the internal information of this algorithm trough maps. +We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap". +\skip Dfs +\until run + +And now comes the third part. Write out the list in reverse order. But the list was +composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it. +\skip std +\until endl + +The program is to be found in the \ref demo directory: \ref topological_ordering.cc + +\todo Check the linking of the demo file, the code samples are missing. + +More algorithms are described in the \ref algorithms2 "second part". + + [SEC]sec_shortest_paths[SEC] Shortest Paths See \ref Dijkstra and \ref BellmanFord. + +If you want to solve some transportation problems in a network then you +will want to find shortest paths between nodes of a graph. This is +usually solved using Dijkstra's algorithm. A utility that solves this is +the LEMON Dijkstra class. The following code is a simple program using +the LEMON Dijkstra class: it calculates the shortest path between node s +and t in a graph g. We omit the part reading the graph g and the length +map len. + +
+ +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 \ref Dijkstra +template class, but the \ref dijkstra() function is also defined, +which can still be used quite flexibly due to named parameters. + +The original sample code could also use the class interface as follows. + +\code + Dijkstra dijktra(g, length); + dijkstra.distMap(dist); + dijsktra.init(); + dijkstra.addSource(u); + dijkstra.start(); +\endcode + +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 \ref dijkstra.start(). + +\code + while (!dijkstra.emptyQueue()) { + ListDigraph::Node n = dijkstra.processNextNode(); + cout << g.id(n) << ' ' << dijkstra.dist(g) << endl; + } +\endcode + + [SEC]sec_max_flow[SEC] Maximum Flows See \ref Preflow.