COIN-OR::LEMON - Graph Library

Changeset 58:10b6a5b7d4c0 in lemon-tutorial for algorithms.dox

03/01/10 02:30:00 (11 years ago)
Peter Kovacs <kpeter@…>

Improve Algorithms section (it is still under construction)

1 edited


  • algorithms.dox

    r57 r58  
    2323\todo This page is under construction.
    25 \todo The following contents are mainly ported from the LEMON 0.x tutorial,
    26 thus they have to be thoroughly revised and reworked.
    28 \warning Currently, this section may contain old or faulty contents.
     24\todo This section should be revised and extended.
    3026In addition to the graph structures, the most important parts of LEMON are
    3127the various algorithms related to graph theory and combinatorial optimization.
    3228The library provides quite flexible and efficient implementations
    33 for well-known fundamental algorithms, such as breadth-first
    34 search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm
    35 and methods for discovering graph properties like connectivity, bipartiteness
    36 or Euler property, as well as more complex optimization algorithms for finding
    37 maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint
    38 paths.
     29for well-known fundamental algorithms, such as \ref Bfs
     30"breadth-first search (BFS)", \ref Dfs "depth-first search (DFS)",
     31\ref Dijkstra "Dijkstra algorithm", \ref kruskal "Kruskal algorithm"
     32and methods for discovering \ref graph_properties "graph properties" like
     33connectivity, bipartiteness or Euler property, as well as more complex
     34optimization algorithms for finding \ref max_flow "maximum flows",
     35\ref min_cut "minimum cuts", \ref matching "matchings",
     36\ref min_cost_flow_algs "minimum cost flows" etc.
    4038In this section, we present only some of the most fundamental algorithms.
    4341[SEC]sec_graph_search[SEC] Graph Search
    45 See \ref Bfs, \ref Dfs and \ref graph_properties.
    47 Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
    48 implementations of the well known algorithms. The algorithms are placed most cases in
    49 separated files named after the algorithm itself but lower case as all other header file names.
    50 For example the next Bfs class is in the \c lemon/bfs.h.
    52 The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
    53 The class has two template parameters: \b GR and \b TR.<br>
    54 GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type.
    55 TR is a Traits class commonly used to easy the parameterization of templates. In most cases you
    56 wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
    58 To use the class, declare it!
    59 \code
    60 Bfs<ListGraph>  bfs(gr);
    61 \endcode
    62 Note the lack of second template argument because of the default parameter.
    64 It provides a simple but powerful interface to control the execution.
    65 \code
    66 int dist =,t);
    67 \endcode
    68 It finds the shortest path from node \c s to node \c t and returns it, or zero
    69 if there is no path from \c s to \c t.<br>
    70 If you want the shortest path from a specified node to all other node, just write:
     43The common graph search algorithms, namely \ref Bfs "breadth-first search (BFS)"
     44and \ref Dfs "depth-first search (DFS)" are implemented in highly adaptable and
     45efficient algorithm classes \ref Bfs and \ref Dfs. In LEMON,
     46the algorithms are typically placed in separated files, which are named after
     47the algorithm itself but with lower case like all other header files.
     48For example, we have to include <tt>bfs.h</tt> for using \ref Bfs.
     51   #include <lemon/bfs.h>
     54Basically, all algorithms are implemented in template classes.
     55The template parameters typically specify the used graph type (for more
     56information, see \ref sec_graph_structures) and the required map types.
     57For example, an instance of the \ref BFs class can be created like this.
     60  ListDigraph g;
     61  Bfs<ListDigraph> bfs(g);
     64This class provides a simple but powerful interface to control the execution
     65of the algorithm and to obtain all the results.
     66You can execute the algorithm from a given source node by calling
     67the \ref Bfs::run() "run()" function.
     73This operation finds the shortest paths from \c s to all other nodes.
     74If you are looking for an s-t path for a certain target node \c t,
     75you can also call the \ref Bfs::run() "run()" function with two
     76parameters. In this case, the BFS search will terminate once it has found
     77the shortest path from \c s to \c t.
     83By default, the distances and the path information are stored in internal
     84maps, which you can access with member functions like \ref lemon::Bfs::distMap
     85"distMap()" and \ref lemon::Bfs::predMap() "predMap()" or more directly with
     86other member functions like \ref lemon::Bfs::dist() "dist()",
     87\ref lemon::Bfs::path() "path()", \ref lemon::Bfs::predNode() "predNode()",
     88\ref lemon::Bfs::predArc() "predArc()". Once the execution of the algorithm
     89is finished, these query functions can be called.
     91For an example, let us say we want to print the shortest path of those nodes
     92that are at most in a certain distance \c max_dist.
    73 \endcode
    74 Now the distances and path information are stored in maps which you can access with
    75 member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
    76 Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm
    77 is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
    78 "predNode()" can be called.
    80 For an example let's say we want to print the shortest path of those nodes which
    81 are in a certain distance.
    82 \code
    85 for( ListGraph::NodeIt  n(gr); n != INVALID; ++n ) {
    86   if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
     96for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
     97  if (bfs.reached(n) && bfs.dist(n) <= max_dist) {
    8798    std::cout <<;
    89     Node  prev = bfs.prevNode(n);
    90     while( prev != INVALID ) {
     99    Node prev = bfs.prevNode(n);
     100    while (prev != INVALID) {
    91101      std::cout << "<-" <<;
    92102      prev = bfs.prevNode(n);
     103    }   
     104    std::cout << std::endl;
     105  }
     109The class interfaces of the algorithms also support a finer control on
     110the execution. For example, we can specify more source nodes and we can
     111even run the algorithm step-by-step.
     112If you need such control on the execution, you have to use more functions
     113instead of \ref Bfs::run() "run()". First, you have to call \ref Bfs::init()
     114"init()" to initialize the internal data structures.
     117  bfs.init();
     120Then you can add one or more source nodes to the queue with
     121\ref Bfs::addSource() "addSource()". They will be processed, as they would
     122be reached by the algorithm before. And yes, you can even add more sources
     123during the execution.
     126  bfs.addSource(s1);
     127  bfs.addSource(s2);
     128  ...
     131Finally, the actual path computation of the algorithm can be performed with
     132the \ref Bfs::start() "start()" function.
     135  bfs.start(t);
     138Instead of using \ref Bfs::start() "start()", you can even execute the
     139algorithm step-by-step, so you can write your own loop to process the
     140nodes one-by-one.
     141For example, the following code will executes the algorithm in such a way,
     142that it reaches all nodes in the digraph, namely the algorithm is started
     143for each node that is not visited before.
     146  bfs.init();
     147  for (NodeIt n(g); n != INVALID; ++n) {
     148    if (!bfs.reached(n)) {
     149      bfs.addSource(n);
     150      bfs.start();
    93151    }
    95     std::cout << std::endl;
    96   }
    97 }
    98 \endcode
    100 In the previous code we only used \c run(). Now we introduce the way you can directly
    101 control the execution of the algorithm.
    103 First you have to initialize the variables with \ref lemon::Bfs::init "init()".
    104 \code
    105   bfs.init();
    106 \endcode
    108 Then you add one or more source nodes to the queue. They will be processed, as they would
    109 be reached by the algorithm before. And yes - you can add more sources during the execution.
    110 \code
    111   bfs.addSource(node_1);
    112   bfs.addSource(node_2);
    113   ...
    114 \endcode
    116 And finally you can start the process with \ref lemon::Bfs::start "start()", or
    117 you can write your own loop to process the nodes one-by-one.
    120 Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
    121 to demonstrate Dfs's capabilities.
    123 We will see a program, which solves the problem of <b>topological ordering</b>.
    124 We need to know in which order we should put on our clothes. The program will do the following:
    125 <ol>
    126 <li>We run the dfs algorithm to all nodes.
    127 <li>Put every node into a list when processed completely.
    128 <li>Write out the list in reverse order.
    129 </ol>
    131 \dontinclude
    132 First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
    133 will be done through it.
    134 \skip MyOrdererMap
    135 \until };
    136 The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
    137 we need to do is insert the key - that is the node whose processing just finished - into the beginning
    138 of the list.<br>
    139 Although we implemented this needed helper class ourselves it was not necessary.
    140 The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
    141 what we needed. To be correct it's more general - and it's all in \c LEMON. But
    142 we wanted to show you, how easy is to add additional functionality.
    144 First we declare the needed data structures: the digraph and a map to store the nodes' label.
    145 \skip ListDigraph
    146 \until label
    148 Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
    149 ordering.
    150 \skip belt
    151 \until trousers
    152 We label them...
    153 \skip label
    154 \until trousers
    155 Then add arcs which represent the precedences between those items.
    156 \skip trousers, belt
    157 \until );
    159 See how easy is to access the internal information of this algorithm trough maps.
    160 We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
    161 \skip Dfs
    162 \until run
    164 And now comes the third part. Write out the list in reverse order. But the list was
    165 composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
    166 \skip std
    167 \until endl
    169 The program is to be found in the \ref demo directory: \ref
    171 \todo Check the linking of the demo file, the code samples are missing.
    173 More algorithms are described in the \ref algorithms2 "second part".
     152  }
     155<tt>bfs.start()</tt> is only a shortcut of the following code.
     158  while (!bfs.emptyQueue()) {
     159    bfs.processNextNode();
     160  }
     163\todo Write about function-type interfaces
     166Since the DFS algorithm is very similar to BFS with a few tiny differences,
     167the \ref Dfs class can be used similarly to \ref Bfs.
    176170[SEC]sec_shortest_paths[SEC] Shortest Paths
    178 See \ref Dijkstra and \ref BellmanFord.
    181 If you want to solve some transportation problems in a network then you
    182 will want to find shortest paths between nodes of a graph. This is
    183 usually solved using Dijkstra's algorithm. A utility that solves this is
    184 the LEMON Dijkstra class. The following code is a simple program using
    185 the LEMON Dijkstra class: it calculates the shortest path between node s
    186 and t in a graph g. We omit the part reading the graph g and the length
    187 map len.
    189 <hr>
     172If you would like to solve some transportation problems in a network, then
     173you will most likely want to find shortest paths between nodes of a graph.
     174This is usually solved using Dijkstra's algorithm.
     175The following code is a simple program using the LEMON \ref Dijkstra class
     176through the function-type interface \ref dijkstra().
     177It calculates the shortest path between node \c s and \c t in a digraph \c g.
     180  dijkstra(g, length).distMap(dist).run(s,t);
    191183In LEMON, the algorithms are implemented basically as classes, but
    196188which can still be used quite flexibly due to named parameters.
    198 The original sample code could also use the class interface as follows.
     190The above sample code could also use the class interface as follows.
    202194  dijkstra.distMap(dist);
    203195  dijsktra.init();
    204   dijkstra.addSource(u);
     196  dijkstra.addSource(s);
    205197  dijkstra.start();
     214LEMON provides several other algorithms for findign shortest paths in
     215specific or more general cases. For example, \ref BellmanFord can be used
     216instead of \ref Dijkstra when the graph contains an arc with negative cost.
     217You may check the \ref shortest_path module of the reference manual for
     218more details.
    223221[SEC]sec_max_flow[SEC] Maximum Flows
    225223See \ref Preflow.
     225\todo Write this subsection.
Note: See TracChangeset for help on using the changeset viewer.