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:
+
+- We run the dfs algorithm to all nodes.
+
- Put every node into a list when processed completely.
+
- 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.