1.1 --- a/algorithms.dox Mon Feb 22 02:00:51 2010 +0100
1.2 +++ b/algorithms.dox Mon Feb 22 02:03:25 2010 +0100
1.3 @@ -23,20 +23,201 @@
1.4 \todo This page is under construction.
1.5
1.6 In addition to the graph structures, the most important parts of LEMON are
1.7 -the various algorithm implementations, which can be used quite flexibly and
1.8 -efficiently.
1.9 +the various algorithms related to graph theory and combinatorial optimization.
1.10 +The library probvides quite flexible and efficient implementations
1.11 +for well-known fundamental algorithms, such as breadth-first
1.12 +search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm
1.13 +and methods for discovering graph properties like connectivity, bipartiteness
1.14 +or Euler property, as well as more complex optimization algorithms for finding
1.15 +maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint
1.16 +paths.
1.17
1.18 In this section, we present only some of the most fundamental algorithms.
1.19 For a complete overview, see the \ref algs module of the reference manual.
1.20
1.21 [SEC]sec_graph_search[SEC] Graph Search
1.22
1.23 +\todo The following contents are ported from the LEMON 0.x tutorial,
1.24 +thus they have to thouroughly revised, reorganized and reworked.
1.25 +
1.26 See \ref Bfs, \ref Dfs and \ref graph_properties.
1.27
1.28 +Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
1.29 +implementations of the well known algorithms. The algorithms are placed most cases in
1.30 +separated files named after the algorithm itself but lower case as all other header file names.
1.31 +For example the next Bfs class is in the \c lemon/bfs.h.
1.32 +
1.33 +The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
1.34 +The class has two template parameters: \b GR and \b TR.<br>
1.35 +GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type.
1.36 +TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
1.37 +wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
1.38 +
1.39 +To use the class, declare it!
1.40 +\code
1.41 +Bfs<ListGraph> bfs(gr);
1.42 +\endcode
1.43 +Note the lack of second template argument because of the default parameter.
1.44 +
1.45 +It provides a simple but powerful interface to control the execution.
1.46 +\code
1.47 +int dist = bfs.run(s,t);
1.48 +\endcode
1.49 +It finds the shortest path from node \c s to node \c t and returns it, or zero
1.50 +if there is no path from \c s to \c t.<br>
1.51 +If you want the shortest path from a specified node to all other node, just write:
1.52 +\code
1.53 +bfs.run(s);
1.54 +\endcode
1.55 +Now the distances and path information are stored in maps which you can access with
1.56 +member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
1.57 +Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm
1.58 +is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
1.59 +"predNode()" can be called.
1.60 +
1.61 +For an example let's say we want to print the shortest path of those nodes which
1.62 +are in a certain distance.
1.63 +\code
1.64 +bfs.run(s);
1.65 +
1.66 +for( ListGraph::NodeIt n(gr); n != INVALID; ++n ) {
1.67 + if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
1.68 + std::cout << gr.id(n);
1.69 +
1.70 + Node prev = bfs.prevNode(n);
1.71 + while( prev != INVALID ) {
1.72 + std::cout << "<-" << gr.id(prev);
1.73 + prev = bfs.prevNode(n);
1.74 + }
1.75 +
1.76 + std::cout << std::endl;
1.77 + }
1.78 +}
1.79 +\endcode
1.80 +
1.81 +In the previous code we only used \c run(). Now we introduce the way you can directly
1.82 +control the execution of the algorithm.
1.83 +
1.84 +First you have to initialize the variables with \ref lemon::Bfs::init "init()".
1.85 +\code
1.86 + bfs.init();
1.87 +\endcode
1.88 +
1.89 +Then you add one or more source nodes to the queue. They will be processed, as they would
1.90 +be reached by the algorithm before. And yes - you can add more sources during the execution.
1.91 +\code
1.92 + bfs.addSource(node_1);
1.93 + bfs.addSource(node_2);
1.94 + ...
1.95 +\endcode
1.96 +
1.97 +And finally you can start the process with \ref lemon::Bfs::start "start()", or
1.98 +you can write your own loop to process the nodes one-by-one.
1.99 +
1.100 +
1.101 +Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
1.102 +to demonstrate Dfs's capabilities.
1.103 +
1.104 +We will see a program, which solves the problem of <b>topological ordering</b>.
1.105 +We need to know in which order we should put on our clothes. The program will do the following:
1.106 +<ol>
1.107 +<li>We run the dfs algorithm to all nodes.
1.108 +<li>Put every node into a list when processed completely.
1.109 +<li>Write out the list in reverse order.
1.110 +</ol>
1.111 +
1.112 +\dontinclude topological_ordering.cc
1.113 +First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
1.114 +will be done through it.
1.115 +\skip MyOrdererMap
1.116 +\until };
1.117 +The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
1.118 +we need to do is insert the key - that is the node whose processing just finished - into the beginning
1.119 +of the list.<br>
1.120 +Although we implemented this needed helper class ourselves it was not necessary.
1.121 +The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
1.122 +what we needed. To be correct it's more general - and it's all in \c LEMON. But
1.123 +we wanted to show you, how easy is to add additional functionality.
1.124 +
1.125 +First we declare the needed data structures: the digraph and a map to store the nodes' label.
1.126 +\skip ListDigraph
1.127 +\until label
1.128 +
1.129 +Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
1.130 +ordering.
1.131 +\skip belt
1.132 +\until trousers
1.133 +We label them...
1.134 +\skip label
1.135 +\until trousers
1.136 +Then add arcs which represent the precedences between those items.
1.137 +\skip trousers, belt
1.138 +\until );
1.139 +
1.140 +See how easy is to access the internal information of this algorithm trough maps.
1.141 +We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
1.142 +\skip Dfs
1.143 +\until run
1.144 +
1.145 +And now comes the third part. Write out the list in reverse order. But the list was
1.146 +composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
1.147 +\skip std
1.148 +\until endl
1.149 +
1.150 +The program is to be found in the \ref demo directory: \ref topological_ordering.cc
1.151 +
1.152 +\todo Check the linking of the demo file, the code samples are missing.
1.153 +
1.154 +More algorithms are described in the \ref algorithms2 "second part".
1.155 +
1.156 +
1.157 [SEC]sec_shortest_paths[SEC] Shortest Paths
1.158
1.159 See \ref Dijkstra and \ref BellmanFord.
1.160
1.161 +
1.162 +If you want to solve some transportation problems in a network then you
1.163 +will want to find shortest paths between nodes of a graph. This is
1.164 +usually solved using Dijkstra's algorithm. A utility that solves this is
1.165 +the LEMON Dijkstra class. The following code is a simple program using
1.166 +the LEMON Dijkstra class: it calculates the shortest path between node s
1.167 +and t in a graph g. We omit the part reading the graph g and the length
1.168 +map len.
1.169 +
1.170 +<hr>
1.171 +
1.172 +In LEMON, the algorithms are implemented basically as classes, but
1.173 +for some of them, function-type interfaces are also available
1.174 +for the sake of convenience.
1.175 +For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra
1.176 +template class, but the \ref dijkstra() function is also defined,
1.177 +which can still be used quite flexibly due to named parameters.
1.178 +
1.179 +The original sample code could also use the class interface as follows.
1.180 +
1.181 +\code
1.182 + Dijkstra<ListDigraph> dijktra(g, length);
1.183 + dijkstra.distMap(dist);
1.184 + dijsktra.init();
1.185 + dijkstra.addSource(u);
1.186 + dijkstra.start();
1.187 +\endcode
1.188 +
1.189 +The previous code is obviously longer than the original, but the
1.190 +execution can be controlled to a higher extent. While using the function-type
1.191 +interface, only one source can be added to the algorithm, the class
1.192 +interface makes it possible to specify several root nodes.
1.193 +Moreover, the algorithm can also be executed step-by-step. For instance,
1.194 +the following code can be used instead of \ref dijkstra.start().
1.195 +
1.196 +\code
1.197 + while (!dijkstra.emptyQueue()) {
1.198 + ListDigraph::Node n = dijkstra.processNextNode();
1.199 + cout << g.id(n) << ' ' << dijkstra.dist(g) << endl;
1.200 + }
1.201 +\endcode
1.202 +
1.203 +
1.204 [SEC]sec_max_flow[SEC] Maximum Flows
1.205
1.206 See \ref Preflow.