doc/algorithms.dox
author hegyi
Fri, 27 Oct 2006 15:08:58 +0000
changeset 2265 5bb8867a9351
parent 2196 09af6d2b683b
child 2281 55b15666560f
permissions -rw-r--r--
NEWS updated to Rel0.6
     1 namespace lemon {
     2 /**
     3 \page algorithms Algorithms
     4 
     5 \section algo_bfs_dfs Bfs/Dfs
     6 Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
     7 implementations of the well known algorithms. The algorithms are placed most cases in
     8 separated files named after the algorithm itself but lower case as all other header file names.
     9 For example the next Bfs class is in the \c lemon/bfs.h.
    10 
    11 \subsection Bfs
    12 The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
    13 The class has two template parameters: \b GR and \TR.<br>
    14 GR is the graph the algorithm runs on. It has \ref lemon::ListGraph "ListGraph" as default type.
    15 TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
    16 wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
    17 
    18 To use the class, declare it!
    19 \code
    20 Bfs<ListUGraph>  bfs(gr);
    21 \endcode
    22 Note the lack of second template argument because of the default parameter.
    23 
    24 It provides a simple but powerful interface to control the execution.
    25 \code
    26 int dist = bfs.run(s,t);
    27 \endcode
    28 It finds the shortest path from node \c s to node \c t and returns it, or zero
    29 if there is no path from \c s to \c t.<br>
    30 If you want the shortest path from a specified node to all other node, just write:
    31 \code
    32 bfs.run(s);
    33 \endcode
    34 Now the distances and path information are stored in maps which you can access with
    35 member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
    36 Or more directly whit other member functions like \c predNode(). Once the algorithm
    37 is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
    38 "predNode()" can be called.
    39 
    40 For an example let's say we want to print the shortest path of those nodes which
    41 are in a certain distance.
    42 \code
    43 bfs.run(s);
    44 
    45 for( ListUGraph::NodeIt  n(gr); n != INVALID; ++n ) {
    46   if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
    47     std::cout << gr.id(n);
    48 
    49     Node  prev = bfs.prevNode(n);
    50     while( prev != INVALID ) {
    51       std::cout << "<-" << gr.id(prev);
    52       prev = bfs.prevNode(n);
    53     }
    54     
    55     std::cout << std::endl;
    56   }
    57 }
    58 \endcode
    59 
    60 \subsubsection bfs_adv_control Advanced control
    61 In the previous code we only used \c run(). Now we introduce the way you can directly
    62 control the execution of the algorithm.
    63 
    64 First you have to initialize the variables with \ref lemon::Bfs::init "init()".
    65 \code
    66   bfs.init();
    67 \endcode
    68 
    69 Then you add one or more source nodes to the queue. They will be processed, as they would
    70 be reached by the algorithm before. And yes - you can add more sources during the execution.
    71 \code
    72   bfs.addSource(node_1);
    73   bfs.addSource(node_2);
    74   ...
    75 \endcode
    76 
    77 And finally you can start the process with \ref lemon::Bfs::start "start()", or
    78 you can write your own loop to process the nodes one-by-one.
    79 
    80 \todo demo for bfs advanced control
    81 
    82 \subsection Dfs
    83 Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
    84 to demonstrate Dfs's capabilities.
    85 
    86 We will see a program, which solves the problem of <b>topological ordering</b>.
    87 We need to know in which order we should put on our clothes. The program will do the following:
    88 <ol>
    89 <li>We run the dfs algorithm to all nodes.
    90 <li>Put every node into a list when processed completely.
    91 <li>Write out the list in reverse order.
    92 </ol>
    93 
    94 \dontinclude topological_ordering.cc
    95 First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
    96 will be done through it.
    97 \skip SerializingWriteMap
    98 \until };
    99 The class meets the \ref lemon::WriteMap "WriteMap" concept. In it's \c set() method the only thing
   100 we need to do is insert the key - that is the node who's processing just finished - into the beginning
   101 of the list.
   102 
   103 First we declare the needed data structures: the graph and a map to store the nodes' label.
   104 \skip ListGraph
   105 \until label
   106 
   107 Now we build a graph. But keep in mind that it must be DAG because cyclic graphs has no topological
   108 ordering.
   109 \skip belt
   110 \until trousers
   111 We label them...
   112 \skip label
   113 \until trousers
   114 Then add directed edges which represent the precedences between those items.
   115 \skip trousers, belt
   116 \until );
   117 
   118 See how easy is to access the internal information of this algorithm trough maps.
   119 We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
   120 \skip Dfs
   121 \until run
   122 
   123 And now comes the third part. Write out the list in reverse order. But the list was
   124 composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
   125 \skip std
   126 \until endl
   127 
   128 The program is to be found in the \ref demo directory: \ref topological_ordering.cc
   129 */
   130 }