doc/algorithms.dox
author kpeter
Mon, 18 Feb 2008 03:34:16 +0000
changeset 2577 2c6204d4b0f6
parent 2476 059dcdda37c5
permissions -rw-r--r--
Add a cost scaling min cost flow algorithm.

Add a cost scaling algorithm, which is performing generalized
push-relabel operations. It is almost as efficient as the capacity
scaling algorithm, but slower than network simplex.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 namespace lemon {
    20 /**
    21 \page algorithms Algorithms
    22 
    23 \section algo_bfs_dfs Bfs/Dfs
    24 Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
    25 implementations of the well known algorithms. The algorithms are placed most cases in
    26 separated files named after the algorithm itself but lower case as all other header file names.
    27 For example the next Bfs class is in the \c lemon/bfs.h.
    28 
    29 \subsection Bfs
    30 The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
    31 The class has two template parameters: \b GR and \b TR.<br>
    32 GR is the graph the algorithm runs on. It has \ref lemon::ListGraph "ListGraph" as default type.
    33 TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
    34 wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
    35 
    36 To use the class, declare it!
    37 \code
    38 Bfs<ListUGraph>  bfs(gr);
    39 \endcode
    40 Note the lack of second template argument because of the default parameter.
    41 
    42 It provides a simple but powerful interface to control the execution.
    43 \code
    44 int dist = bfs.run(s,t);
    45 \endcode
    46 It finds the shortest path from node \c s to node \c t and returns it, or zero
    47 if there is no path from \c s to \c t.<br>
    48 If you want the shortest path from a specified node to all other node, just write:
    49 \code
    50 bfs.run(s);
    51 \endcode
    52 Now the distances and path information are stored in maps which you can access with
    53 member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
    54 Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm
    55 is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
    56 "predNode()" can be called.
    57 
    58 For an example let's say we want to print the shortest path of those nodes which
    59 are in a certain distance.
    60 \code
    61 bfs.run(s);
    62 
    63 for( ListUGraph::NodeIt  n(gr); n != INVALID; ++n ) {
    64   if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
    65     std::cout << gr.id(n);
    66 
    67     Node  prev = bfs.prevNode(n);
    68     while( prev != INVALID ) {
    69       std::cout << "<-" << gr.id(prev);
    70       prev = bfs.prevNode(n);
    71     }
    72     
    73     std::cout << std::endl;
    74   }
    75 }
    76 \endcode
    77 
    78 \subsubsection bfs_adv_control Advanced control
    79 In the previous code we only used \c run(). Now we introduce the way you can directly
    80 control the execution of the algorithm.
    81 
    82 First you have to initialize the variables with \ref lemon::Bfs::init "init()".
    83 \code
    84   bfs.init();
    85 \endcode
    86 
    87 Then you add one or more source nodes to the queue. They will be processed, as they would
    88 be reached by the algorithm before. And yes - you can add more sources during the execution.
    89 \code
    90   bfs.addSource(node_1);
    91   bfs.addSource(node_2);
    92   ...
    93 \endcode
    94 
    95 And finally you can start the process with \ref lemon::Bfs::start "start()", or
    96 you can write your own loop to process the nodes one-by-one.
    97 
    98 \todo Demo for Bfs advanced control.
    99 
   100 \subsection Dfs
   101 Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
   102 to demonstrate Dfs's capabilities.
   103 
   104 We will see a program, which solves the problem of <b>topological ordering</b>.
   105 We need to know in which order we should put on our clothes. The program will do the following:
   106 <ol>
   107 <li>We run the dfs algorithm to all nodes.
   108 <li>Put every node into a list when processed completely.
   109 <li>Write out the list in reverse order.
   110 </ol>
   111 
   112 \dontinclude topological_ordering.cc
   113 First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
   114 will be done through it.
   115 \skip MyOrdererMap
   116 \until };
   117 The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
   118 we need to do is insert the key - that is the node whose processing just finished - into the beginning
   119 of the list.<br>
   120 Although we implemented this needed helper class ourselves it was not necessary.
   121 The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
   122 what we needed. To be correct it's more general - and it's all in \c LEMON. But
   123 we wanted to show you, how easy is to add additional functionality.
   124 
   125 First we declare the needed data structures: the graph and a map to store the nodes' label.
   126 \skip ListGraph
   127 \until label
   128 
   129 Now we build a graph. But keep in mind that it must be DAG because cyclic graphs has no topological
   130 ordering.
   131 \skip belt
   132 \until trousers
   133 We label them...
   134 \skip label
   135 \until trousers
   136 Then add directed edges which represent the precedences between those items.
   137 \skip trousers, belt
   138 \until );
   139 
   140 See how easy is to access the internal information of this algorithm trough maps.
   141 We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
   142 \skip Dfs
   143 \until run
   144 
   145 And now comes the third part. Write out the list in reverse order. But the list was
   146 composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
   147 \skip std
   148 \until endl
   149 
   150 The program is to be found in the \ref demo directory: \ref topological_ordering.cc
   151 
   152 \todo Check the linking of the demo file, the code samples are missing.
   153 
   154 More algorithms are described in the \ref algorithms2 "second part".
   155 */
   156 }