algorithms.dox
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 28 Feb 2010 19:38:57 +0100
changeset 53 0f695eac7e07
parent 49 c8c5a2a4ec71
child 57 18404ec968ca
permissions -rw-r--r--
Show demo files in the menu
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2010
     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]sec_algorithms[PAGE] Algorithms
    22 
    23 \todo This page is under construction.
    24 
    25 In addition to the graph structures, the most important parts of LEMON are
    26 the various algorithms related to graph theory and combinatorial optimization.
    27 The library probvides quite flexible and efficient implementations
    28 for well-known fundamental algorithms, such as breadth-first
    29 search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm
    30 and methods for discovering graph properties like connectivity, bipartiteness
    31 or Euler property, as well as more complex optimization algorithms for finding
    32 maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint
    33 paths.
    34 
    35 In this section, we present only some of the most fundamental algorithms.
    36 For a complete overview, see the \ref algs module of the reference manual.
    37 
    38 [SEC]sec_graph_search[SEC] Graph Search
    39 
    40 \todo The following contents are ported from the LEMON 0.x tutorial,
    41 thus they have to thouroughly revised, reorganized and reworked.
    42 
    43 See \ref Bfs, \ref Dfs and \ref graph_properties.
    44 
    45 Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
    46 implementations of the well known algorithms. The algorithms are placed most cases in
    47 separated files named after the algorithm itself but lower case as all other header file names.
    48 For example the next Bfs class is in the \c lemon/bfs.h.
    49 
    50 The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
    51 The class has two template parameters: \b GR and \b TR.<br>
    52 GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type.
    53 TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
    54 wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
    55 
    56 To use the class, declare it!
    57 \code
    58 Bfs<ListGraph>  bfs(gr);
    59 \endcode
    60 Note the lack of second template argument because of the default parameter.
    61 
    62 It provides a simple but powerful interface to control the execution.
    63 \code
    64 int dist = bfs.run(s,t);
    65 \endcode
    66 It finds the shortest path from node \c s to node \c t and returns it, or zero
    67 if there is no path from \c s to \c t.<br>
    68 If you want the shortest path from a specified node to all other node, just write:
    69 \code
    70 bfs.run(s);
    71 \endcode
    72 Now the distances and path information are stored in maps which you can access with
    73 member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
    74 Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm
    75 is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
    76 "predNode()" can be called.
    77 
    78 For an example let's say we want to print the shortest path of those nodes which
    79 are in a certain distance.
    80 \code
    81 bfs.run(s);
    82 
    83 for( ListGraph::NodeIt  n(gr); n != INVALID; ++n ) {
    84   if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
    85     std::cout << gr.id(n);
    86 
    87     Node  prev = bfs.prevNode(n);
    88     while( prev != INVALID ) {
    89       std::cout << "<-" << gr.id(prev);
    90       prev = bfs.prevNode(n);
    91     }
    92     
    93     std::cout << std::endl;
    94   }
    95 }
    96 \endcode
    97 
    98 In the previous code we only used \c run(). Now we introduce the way you can directly
    99 control the execution of the algorithm.
   100 
   101 First you have to initialize the variables with \ref lemon::Bfs::init "init()".
   102 \code
   103   bfs.init();
   104 \endcode
   105 
   106 Then you add one or more source nodes to the queue. They will be processed, as they would
   107 be reached by the algorithm before. And yes - you can add more sources during the execution.
   108 \code
   109   bfs.addSource(node_1);
   110   bfs.addSource(node_2);
   111   ...
   112 \endcode
   113 
   114 And finally you can start the process with \ref lemon::Bfs::start "start()", or
   115 you can write your own loop to process the nodes one-by-one.
   116 
   117 
   118 Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
   119 to demonstrate Dfs's capabilities.
   120 
   121 We will see a program, which solves the problem of <b>topological ordering</b>.
   122 We need to know in which order we should put on our clothes. The program will do the following:
   123 <ol>
   124 <li>We run the dfs algorithm to all nodes.
   125 <li>Put every node into a list when processed completely.
   126 <li>Write out the list in reverse order.
   127 </ol>
   128 
   129 \dontinclude topological_ordering.cc
   130 First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
   131 will be done through it.
   132 \skip MyOrdererMap
   133 \until };
   134 The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
   135 we need to do is insert the key - that is the node whose processing just finished - into the beginning
   136 of the list.<br>
   137 Although we implemented this needed helper class ourselves it was not necessary.
   138 The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
   139 what we needed. To be correct it's more general - and it's all in \c LEMON. But
   140 we wanted to show you, how easy is to add additional functionality.
   141 
   142 First we declare the needed data structures: the digraph and a map to store the nodes' label.
   143 \skip ListDigraph
   144 \until label
   145 
   146 Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
   147 ordering.
   148 \skip belt
   149 \until trousers
   150 We label them...
   151 \skip label
   152 \until trousers
   153 Then add arcs which represent the precedences between those items.
   154 \skip trousers, belt
   155 \until );
   156 
   157 See how easy is to access the internal information of this algorithm trough maps.
   158 We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
   159 \skip Dfs
   160 \until run
   161 
   162 And now comes the third part. Write out the list in reverse order. But the list was
   163 composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
   164 \skip std
   165 \until endl
   166 
   167 The program is to be found in the \ref demo directory: \ref topological_ordering.cc
   168 
   169 \todo Check the linking of the demo file, the code samples are missing.
   170 
   171 More algorithms are described in the \ref algorithms2 "second part".
   172 
   173 
   174 [SEC]sec_shortest_paths[SEC] Shortest Paths
   175 
   176 See \ref Dijkstra and \ref BellmanFord.
   177 
   178 
   179 If you want to solve some transportation problems in a network then you
   180 will want to find shortest paths between nodes of a graph. This is
   181 usually solved using Dijkstra's algorithm. A utility that solves this is
   182 the LEMON Dijkstra class. The following code is a simple program using
   183 the LEMON Dijkstra class: it calculates the shortest path between node s
   184 and t in a graph g. We omit the part reading the graph g and the length
   185 map len.
   186 
   187 <hr>
   188  
   189 In LEMON, the algorithms are implemented basically as classes, but
   190 for some of them, function-type interfaces are also available
   191 for the sake of convenience.
   192 For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra
   193 template class, but the \ref dijkstra() function is also defined,
   194 which can still be used quite flexibly due to named parameters.
   195 
   196 The original sample code could also use the class interface as follows.
   197 
   198 \code
   199   Dijkstra<ListDigraph> dijkstra(g, length);
   200   dijkstra.distMap(dist);
   201   dijsktra.init();
   202   dijkstra.addSource(u);
   203   dijkstra.start();
   204 \endcode
   205 
   206 The previous code is obviously longer than the original, but the
   207 execution can be controlled to a higher extent. While using the function-type
   208 interface, only one source can be added to the algorithm, the class
   209 interface makes it possible to specify several root nodes.
   210 Moreover, the algorithm can also be executed step-by-step. For instance,
   211 the following code can be used instead of \ref dijkstra.start().
   212 
   213 \code
   214   while (!dijkstra.emptyQueue()) {
   215     ListDigraph::Node n = dijkstra.processNextNode();
   216     cout << g.id(n) << ' ' << dijkstra.dist(g) << endl;
   217   }
   218 \endcode
   219 
   220 
   221 [SEC]sec_max_flow[SEC] Maximum Flows
   222 
   223 See \ref Preflow.
   224 
   225 [TRAILER]
   226 */
   227 }