1.1 --- a/algorithms.dox Mon Mar 01 02:28:44 2010 +0100
1.2 +++ b/algorithms.dox Mon Mar 01 02:30:00 2010 +0100
1.3 @@ -21,172 +21,164 @@
1.4 [PAGE]sec_algorithms[PAGE] Algorithms
1.5
1.6 \todo This page is under construction.
1.7 -
1.8 -\todo The following contents are mainly ported from the LEMON 0.x tutorial,
1.9 -thus they have to be thoroughly revised and reworked.
1.10 -
1.11 -\warning Currently, this section may contain old or faulty contents.
1.12 +\todo This section should be revised and extended.
1.13
1.14 In addition to the graph structures, the most important parts of LEMON are
1.15 the various algorithms related to graph theory and combinatorial optimization.
1.16 The library provides quite flexible and efficient implementations
1.17 -for well-known fundamental algorithms, such as breadth-first
1.18 -search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm
1.19 -and methods for discovering graph properties like connectivity, bipartiteness
1.20 -or Euler property, as well as more complex optimization algorithms for finding
1.21 -maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint
1.22 -paths.
1.23 +for well-known fundamental algorithms, such as \ref Bfs
1.24 +"breadth-first search (BFS)", \ref Dfs "depth-first search (DFS)",
1.25 +\ref Dijkstra "Dijkstra algorithm", \ref kruskal "Kruskal algorithm"
1.26 +and methods for discovering \ref graph_properties "graph properties" like
1.27 +connectivity, bipartiteness or Euler property, as well as more complex
1.28 +optimization algorithms for finding \ref max_flow "maximum flows",
1.29 +\ref min_cut "minimum cuts", \ref matching "matchings",
1.30 +\ref min_cost_flow_algs "minimum cost flows" etc.
1.31
1.32 In this section, we present only some of the most fundamental algorithms.
1.33 For a complete overview, see the \ref algs module of the reference manual.
1.34
1.35 [SEC]sec_graph_search[SEC] Graph Search
1.36
1.37 -See \ref Bfs, \ref Dfs and \ref graph_properties.
1.38 +The common graph search algorithms, namely \ref Bfs "breadth-first search (BFS)"
1.39 +and \ref Dfs "depth-first search (DFS)" are implemented in highly adaptable and
1.40 +efficient algorithm classes \ref Bfs and \ref Dfs. In LEMON,
1.41 +the algorithms are typically placed in separated files, which are named after
1.42 +the algorithm itself but with lower case like all other header files.
1.43 +For example, we have to include <tt>bfs.h</tt> for using \ref Bfs.
1.44
1.45 -Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
1.46 -implementations of the well known algorithms. The algorithms are placed most cases in
1.47 -separated files named after the algorithm itself but lower case as all other header file names.
1.48 -For example the next Bfs class is in the \c lemon/bfs.h.
1.49 +\code
1.50 + #include <lemon/bfs.h>
1.51 +\endcode
1.52
1.53 -The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
1.54 -The class has two template parameters: \b GR and \b TR.<br>
1.55 -GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type.
1.56 -TR is a Traits class commonly used to easy the parameterization of templates. In most cases you
1.57 -wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
1.58 +Basically, all algorithms are implemented in template classes.
1.59 +The template parameters typically specify the used graph type (for more
1.60 +information, see \ref sec_graph_structures) and the required map types.
1.61 +For example, an instance of the \ref BFs class can be created like this.
1.62
1.63 -To use the class, declare it!
1.64 \code
1.65 -Bfs<ListGraph> bfs(gr);
1.66 + ListDigraph g;
1.67 + Bfs<ListDigraph> bfs(g);
1.68 \endcode
1.69 -Note the lack of second template argument because of the default parameter.
1.70
1.71 -It provides a simple but powerful interface to control the execution.
1.72 +This class provides a simple but powerful interface to control the execution
1.73 +of the algorithm and to obtain all the results.
1.74 +You can execute the algorithm from a given source node by calling
1.75 +the \ref Bfs::run() "run()" function.
1.76 +
1.77 \code
1.78 -int dist = bfs.run(s,t);
1.79 + bfs.run(s);
1.80 \endcode
1.81 -It finds the shortest path from node \c s to node \c t and returns it, or zero
1.82 -if there is no path from \c s to \c t.<br>
1.83 -If you want the shortest path from a specified node to all other node, just write:
1.84 +
1.85 +This operation finds the shortest paths from \c s to all other nodes.
1.86 +If you are looking for an s-t path for a certain target node \c t,
1.87 +you can also call the \ref Bfs::run() "run()" function with two
1.88 +parameters. In this case, the BFS search will terminate once it has found
1.89 +the shortest path from \c s to \c t.
1.90 +
1.91 \code
1.92 -bfs.run(s);
1.93 + bfs.run(s,t);
1.94 \endcode
1.95 -Now the distances and path information are stored in maps which you can access with
1.96 -member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
1.97 -Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm
1.98 -is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
1.99 -"predNode()" can be called.
1.100
1.101 -For an example let's say we want to print the shortest path of those nodes which
1.102 -are in a certain distance.
1.103 +By default, the distances and the path information are stored in internal
1.104 +maps, which you can access with member functions like \ref lemon::Bfs::distMap
1.105 +"distMap()" and \ref lemon::Bfs::predMap() "predMap()" or more directly with
1.106 +other member functions like \ref lemon::Bfs::dist() "dist()",
1.107 +\ref lemon::Bfs::path() "path()", \ref lemon::Bfs::predNode() "predNode()",
1.108 +\ref lemon::Bfs::predArc() "predArc()". Once the execution of the algorithm
1.109 +is finished, these query functions can be called.
1.110 +
1.111 +For an example, let us say we want to print the shortest path of those nodes
1.112 +that are at most in a certain distance \c max_dist.
1.113 \code
1.114 bfs.run(s);
1.115
1.116 -for( ListGraph::NodeIt n(gr); n != INVALID; ++n ) {
1.117 - if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
1.118 +for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
1.119 + if (bfs.reached(n) && bfs.dist(n) <= max_dist) {
1.120 std::cout << gr.id(n);
1.121 -
1.122 - Node prev = bfs.prevNode(n);
1.123 - while( prev != INVALID ) {
1.124 + Node prev = bfs.prevNode(n);
1.125 + while (prev != INVALID) {
1.126 std::cout << "<-" << gr.id(prev);
1.127 prev = bfs.prevNode(n);
1.128 - }
1.129 -
1.130 + }
1.131 std::cout << std::endl;
1.132 }
1.133 }
1.134 \endcode
1.135
1.136 -In the previous code we only used \c run(). Now we introduce the way you can directly
1.137 -control the execution of the algorithm.
1.138 +The class interfaces of the algorithms also support a finer control on
1.139 +the execution. For example, we can specify more source nodes and we can
1.140 +even run the algorithm step-by-step.
1.141 +If you need such control on the execution, you have to use more functions
1.142 +instead of \ref Bfs::run() "run()". First, you have to call \ref Bfs::init()
1.143 +"init()" to initialize the internal data structures.
1.144
1.145 -First you have to initialize the variables with \ref lemon::Bfs::init "init()".
1.146 \code
1.147 bfs.init();
1.148 \endcode
1.149
1.150 -Then you add one or more source nodes to the queue. They will be processed, as they would
1.151 -be reached by the algorithm before. And yes - you can add more sources during the execution.
1.152 +Then you can add one or more source nodes to the queue with
1.153 +\ref Bfs::addSource() "addSource()". They will be processed, as they would
1.154 +be reached by the algorithm before. And yes, you can even add more sources
1.155 +during the execution.
1.156 +
1.157 \code
1.158 - bfs.addSource(node_1);
1.159 - bfs.addSource(node_2);
1.160 + bfs.addSource(s1);
1.161 + bfs.addSource(s2);
1.162 ...
1.163 \endcode
1.164
1.165 -And finally you can start the process with \ref lemon::Bfs::start "start()", or
1.166 -you can write your own loop to process the nodes one-by-one.
1.167 +Finally, the actual path computation of the algorithm can be performed with
1.168 +the \ref Bfs::start() "start()" function.
1.169
1.170 +\code
1.171 + bfs.start(t);
1.172 +\endcode
1.173
1.174 -Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
1.175 -to demonstrate Dfs's capabilities.
1.176 +Instead of using \ref Bfs::start() "start()", you can even execute the
1.177 +algorithm step-by-step, so you can write your own loop to process the
1.178 +nodes one-by-one.
1.179 +For example, the following code will executes the algorithm in such a way,
1.180 +that it reaches all nodes in the digraph, namely the algorithm is started
1.181 +for each node that is not visited before.
1.182
1.183 -We will see a program, which solves the problem of <b>topological ordering</b>.
1.184 -We need to know in which order we should put on our clothes. The program will do the following:
1.185 -<ol>
1.186 -<li>We run the dfs algorithm to all nodes.
1.187 -<li>Put every node into a list when processed completely.
1.188 -<li>Write out the list in reverse order.
1.189 -</ol>
1.190 +\code
1.191 + bfs.init();
1.192 + for (NodeIt n(g); n != INVALID; ++n) {
1.193 + if (!bfs.reached(n)) {
1.194 + bfs.addSource(n);
1.195 + bfs.start();
1.196 + }
1.197 + }
1.198 +\endcode
1.199
1.200 -\dontinclude topological_ordering.cc
1.201 -First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
1.202 -will be done through it.
1.203 -\skip MyOrdererMap
1.204 -\until };
1.205 -The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
1.206 -we need to do is insert the key - that is the node whose processing just finished - into the beginning
1.207 -of the list.<br>
1.208 -Although we implemented this needed helper class ourselves it was not necessary.
1.209 -The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
1.210 -what we needed. To be correct it's more general - and it's all in \c LEMON. But
1.211 -we wanted to show you, how easy is to add additional functionality.
1.212 +<tt>bfs.start()</tt> is only a shortcut of the following code.
1.213
1.214 -First we declare the needed data structures: the digraph and a map to store the nodes' label.
1.215 -\skip ListDigraph
1.216 -\until label
1.217 +\code
1.218 + while (!bfs.emptyQueue()) {
1.219 + bfs.processNextNode();
1.220 + }
1.221 +\endcode
1.222
1.223 -Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
1.224 -ordering.
1.225 -\skip belt
1.226 -\until trousers
1.227 -We label them...
1.228 -\skip label
1.229 -\until trousers
1.230 -Then add arcs which represent the precedences between those items.
1.231 -\skip trousers, belt
1.232 -\until );
1.233 +\todo Write about function-type interfaces
1.234
1.235 -See how easy is to access the internal information of this algorithm trough maps.
1.236 -We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
1.237 -\skip Dfs
1.238 -\until run
1.239
1.240 -And now comes the third part. Write out the list in reverse order. But the list was
1.241 -composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
1.242 -\skip std
1.243 -\until endl
1.244 -
1.245 -The program is to be found in the \ref demo directory: \ref topological_ordering.cc
1.246 -
1.247 -\todo Check the linking of the demo file, the code samples are missing.
1.248 -
1.249 -More algorithms are described in the \ref algorithms2 "second part".
1.250 +Since the DFS algorithm is very similar to BFS with a few tiny differences,
1.251 +the \ref Dfs class can be used similarly to \ref Bfs.
1.252
1.253
1.254 [SEC]sec_shortest_paths[SEC] Shortest Paths
1.255
1.256 -See \ref Dijkstra and \ref BellmanFord.
1.257 +If you would like to solve some transportation problems in a network, then
1.258 +you will most likely want to find shortest paths between nodes of a graph.
1.259 +This is usually solved using Dijkstra's algorithm.
1.260 +The following code is a simple program using the LEMON \ref Dijkstra class
1.261 +through the function-type interface \ref dijkstra().
1.262 +It calculates the shortest path between node \c s and \c t in a digraph \c g.
1.263
1.264 -
1.265 -If you want to solve some transportation problems in a network then you
1.266 -will want to find shortest paths between nodes of a graph. This is
1.267 -usually solved using Dijkstra's algorithm. A utility that solves this is
1.268 -the LEMON Dijkstra class. The following code is a simple program using
1.269 -the LEMON Dijkstra class: it calculates the shortest path between node s
1.270 -and t in a graph g. We omit the part reading the graph g and the length
1.271 -map len.
1.272 -
1.273 -<hr>
1.274 +\code
1.275 + dijkstra(g, length).distMap(dist).run(s,t);
1.276 +\endcode
1.277
1.278 In LEMON, the algorithms are implemented basically as classes, but
1.279 for some of them, function-type interfaces are also available
1.280 @@ -195,13 +187,13 @@
1.281 template class, but the \ref dijkstra() function is also defined,
1.282 which can still be used quite flexibly due to named parameters.
1.283
1.284 -The original sample code could also use the class interface as follows.
1.285 +The above sample code could also use the class interface as follows.
1.286
1.287 \code
1.288 Dijkstra<ListDigraph> dijkstra(g, length);
1.289 dijkstra.distMap(dist);
1.290 dijsktra.init();
1.291 - dijkstra.addSource(u);
1.292 + dijkstra.addSource(s);
1.293 dijkstra.start();
1.294 \endcode
1.295
1.296 @@ -219,11 +211,19 @@
1.297 }
1.298 \endcode
1.299
1.300 +LEMON provides several other algorithms for findign shortest paths in
1.301 +specific or more general cases. For example, \ref BellmanFord can be used
1.302 +instead of \ref Dijkstra when the graph contains an arc with negative cost.
1.303 +You may check the \ref shortest_path module of the reference manual for
1.304 +more details.
1.305 +
1.306
1.307 [SEC]sec_max_flow[SEC] Maximum Flows
1.308
1.309 See \ref Preflow.
1.310
1.311 +\todo Write this subsection.
1.312 +
1.313 [TRAILER]
1.314 */
1.315 }
2.1 --- a/maps.dox Mon Mar 01 02:28:44 2010 +0100
2.2 +++ b/maps.dox Mon Mar 01 02:30:00 2010 +0100
2.3 @@ -36,18 +36,6 @@
2.4 These classes also conform to the map %concepts, thus they can be used
2.5 like standard LEMON maps.
2.6
2.7 -Let us suppose that we have a traffic network stored in a LEMON digraph
2.8 -structure with two arc maps \c length and \c speed, which
2.9 -denote the physical length of each arc and the maximum (or average)
2.10 -speed that can be achieved on the corresponding road-section,
2.11 -respectively. If we are interested in the best traveling times,
2.12 -the following code can be used.
2.13 -
2.14 -\code
2.15 - dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
2.16 -\endcode
2.17 -
2.18 -
2.19 Maps play a central role in LEMON. As their name suggests, they map a
2.20 certain range of \e keys to certain \e values. Each map has two
2.21 <tt>typedef</tt>'s to determine the types of keys and values, like this:
2.22 @@ -335,6 +323,7 @@
2.23
2.24 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
2.25
2.26 +
2.27 The basic functionality of the algorithms can be highly extended using
2.28 special purpose map types for their internal data structures.
2.29 For example, the \ref Dijkstra class stores a
2.30 @@ -349,6 +338,17 @@
2.31 named template parameters. Similarly to the named function parameters,
2.32 they allow specifying any subset of the parameters and in arbitrary order.
2.33
2.34 +Let us suppose that we have a traffic network stored in a LEMON digraph
2.35 +structure with two arc maps \c length and \c speed, which
2.36 +denote the physical length of each arc and the maximum (or average)
2.37 +speed that can be achieved on the corresponding road-section,
2.38 +respectively. If we are interested in the best traveling times,
2.39 +the following code can be used.
2.40 +
2.41 +\code
2.42 + dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
2.43 +\endcode
2.44 +
2.45 \code
2.46 typedef vector<ListDigraph::Node> Container;
2.47 typedef back_insert_iterator<Container> InsertIterator;
2.48 @@ -378,6 +378,56 @@
2.49 .run(s);
2.50 \endcode
2.51
2.52 +Let us see a bit more complex example to demonstrate Dfs's capabilities.
2.53 +
2.54 +We will see a program, which solves the problem of <b>topological ordering</b>.
2.55 +We need to know in which order we should put on our clothes. The program will do the following:
2.56 +<ol>
2.57 +<li>We run the dfs algorithm to all nodes.
2.58 +<li>Put every node into a list when processed completely.
2.59 +<li>Write out the list in reverse order.
2.60 +</ol>
2.61 +
2.62 +\dontinclude topological_ordering.cc
2.63 +First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
2.64 +will be done through it.
2.65 +\skip MyOrdererMap
2.66 +\until };
2.67 +The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
2.68 +we need to do is insert the key - that is the node whose processing just finished - into the beginning
2.69 +of the list.<br>
2.70 +Although we implemented this needed helper class ourselves it was not necessary.
2.71 +The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
2.72 +what we needed. To be correct it's more general - and it's all in \c LEMON. But
2.73 +we wanted to show you, how easy is to add additional functionality.
2.74 +
2.75 +First we declare the needed data structures: the digraph and a map to store the nodes' label.
2.76 +\skip ListDigraph
2.77 +\until label
2.78 +
2.79 +Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
2.80 +ordering.
2.81 +\skip belt
2.82 +\until trousers
2.83 +We label them...
2.84 +\skip label
2.85 +\until trousers
2.86 +Then add arcs which represent the precedences between those items.
2.87 +\skip trousers, belt
2.88 +\until );
2.89 +
2.90 +See how easy is to access the internal information of this algorithm trough maps.
2.91 +We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
2.92 +\skip Dfs
2.93 +\until run
2.94 +
2.95 +And now comes the third part. Write out the list in reverse order. But the list was
2.96 +composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
2.97 +\skip std
2.98 +\until endl
2.99 +
2.100 +The program is to be found in the \ref demo directory: \ref topological_ordering.cc
2.101 +
2.102 LEMON also contains visitor based algorithm classes for
2.103 BFS and DFS.
2.104