COIN-OR::LEMON - Graph Library

Changeset 58:10b6a5b7d4c0 in lemon-tutorial


Ignore:
Timestamp:
03/01/10 02:30:00 (8 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Improve Algorithms section (it is still under construction)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • algorithms.dox

    r57 r58  
    2222 
    2323\todo This page is under construction. 
    24  
    25 \todo The following contents are mainly ported from the LEMON 0.x tutorial, 
    26 thus they have to be thoroughly revised and reworked. 
    27  
    28 \warning Currently, this section may contain old or faulty contents. 
     24\todo This section should be revised and extended. 
    2925 
    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. 
    3937 
    4038In this section, we present only some of the most fundamental algorithms. 
     
    4341[SEC]sec_graph_search[SEC] Graph Search 
    4442 
    45 See \ref Bfs, \ref Dfs and \ref graph_properties. 
    46  
    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. 
    51  
    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>". 
    57  
    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. 
    63  
    64 It provides a simple but powerful interface to control the execution. 
    65 \code 
    66 int dist = bfs.run(s,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. 
     49 
     50\code 
     51   #include <lemon/bfs.h> 
     52\endcode 
     53 
     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. 
     58 
     59\code 
     60  ListDigraph g; 
     61  Bfs<ListDigraph> bfs(g); 
     62\endcode 
     63 
     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. 
     68 
     69\code 
     70  bfs.run(s); 
     71\endcode 
     72 
     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.  
     78 
     79\code 
     80  bfs.run(s,t); 
     81\endcode 
     82 
     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. 
     90 
     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. 
    7193\code 
    7294bfs.run(s); 
    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. 
    79  
    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 
    83 bfs.run(s); 
    84  
    85 for( ListGraph::NodeIt  n(gr); n != INVALID; ++n ) { 
    86   if( bfs.reached(n) && bfs.dist(n) <= max_dist ) { 
     95 
     96for (ListGraph::NodeIt n(g); n != INVALID; ++n) { 
     97  if (bfs.reached(n) && bfs.dist(n) <= max_dist) { 
    8798    std::cout << gr.id(n); 
    88  
    89     Node  prev = bfs.prevNode(n); 
    90     while( prev != INVALID ) { 
     99    Node prev = bfs.prevNode(n); 
     100    while (prev != INVALID) { 
    91101      std::cout << "<-" << gr.id(prev); 
    92102      prev = bfs.prevNode(n); 
     103    }     
     104    std::cout << std::endl; 
     105  } 
     106} 
     107\endcode 
     108 
     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. 
     115 
     116\code 
     117  bfs.init(); 
     118\endcode 
     119 
     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. 
     124 
     125\code 
     126  bfs.addSource(s1); 
     127  bfs.addSource(s2); 
     128  ... 
     129\endcode 
     130 
     131Finally, the actual path computation of the algorithm can be performed with 
     132the \ref Bfs::start() "start()" function. 
     133 
     134\code 
     135  bfs.start(t); 
     136\endcode 
     137 
     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. 
     144 
     145\code 
     146  bfs.init(); 
     147  for (NodeIt n(g); n != INVALID; ++n) { 
     148    if (!bfs.reached(n)) { 
     149      bfs.addSource(n); 
     150      bfs.start(); 
    93151    } 
    94      
    95     std::cout << std::endl; 
    96   } 
    97 } 
    98 \endcode 
    99  
    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. 
    102  
    103 First you have to initialize the variables with \ref lemon::Bfs::init "init()". 
    104 \code 
    105   bfs.init(); 
    106 \endcode 
    107  
    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 
    115  
    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. 
    118  
    119  
    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. 
    122  
    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> 
    130  
    131 \dontinclude topological_ordering.cc 
    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. 
    143  
    144 First we declare the needed data structures: the digraph and a map to store the nodes' label. 
    145 \skip ListDigraph 
    146 \until label 
    147  
    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 ); 
    158  
    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 
    163  
    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 
    168  
    169 The program is to be found in the \ref demo directory: \ref topological_ordering.cc 
    170  
    171 \todo Check the linking of the demo file, the code samples are missing. 
    172  
    173 More algorithms are described in the \ref algorithms2 "second part". 
     152  } 
     153\endcode 
     154 
     155<tt>bfs.start()</tt> is only a shortcut of the following code. 
     156 
     157\code 
     158  while (!bfs.emptyQueue()) { 
     159    bfs.processNextNode(); 
     160  } 
     161\endcode 
     162 
     163\todo Write about function-type interfaces 
     164 
     165 
     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. 
    174168 
    175169 
    176170[SEC]sec_shortest_paths[SEC] Shortest Paths 
    177171 
    178 See \ref Dijkstra and \ref BellmanFord. 
    179  
    180  
    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. 
    188  
    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. 
     178 
     179\code 
     180  dijkstra(g, length).distMap(dist).run(s,t); 
     181\endcode 
    190182  
    191183In LEMON, the algorithms are implemented basically as classes, but 
     
    196188which can still be used quite flexibly due to named parameters. 
    197189 
    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. 
    199191 
    200192\code 
     
    202194  dijkstra.distMap(dist); 
    203195  dijsktra.init(); 
    204   dijkstra.addSource(u); 
     196  dijkstra.addSource(s); 
    205197  dijkstra.start(); 
    206198\endcode 
     
    220212\endcode 
    221213 
     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. 
     219 
    222220 
    223221[SEC]sec_max_flow[SEC] Maximum Flows 
    224222 
    225223See \ref Preflow. 
     224 
     225\todo Write this subsection. 
    226226 
    227227[TRAILER] 
  • maps.dox

    r57 r58  
    3636These classes also conform to the map %concepts, thus they can be used 
    3737like standard LEMON maps. 
    38  
    39 Let us suppose that we have a traffic network stored in a LEMON digraph 
    40 structure with two arc maps \c length and \c speed, which 
    41 denote the physical length of each arc and the maximum (or average) 
    42 speed that can be achieved on the corresponding road-section, 
    43 respectively. If we are interested in the best traveling times, 
    44 the following code can be used. 
    45  
    46 \code 
    47   dijkstra(g, divMap(length, speed)).distMap(dist).run(s); 
    48 \endcode 
    49  
    5038 
    5139Maps play a central role in LEMON. As their name suggests, they map a 
     
    336324[SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps 
    337325 
     326 
    338327The basic functionality of the algorithms can be highly extended using 
    339328special purpose map types for their internal data structures. 
     
    350339they allow specifying any subset of the parameters and in arbitrary order. 
    351340 
     341Let us suppose that we have a traffic network stored in a LEMON digraph 
     342structure with two arc maps \c length and \c speed, which 
     343denote the physical length of each arc and the maximum (or average) 
     344speed that can be achieved on the corresponding road-section, 
     345respectively. If we are interested in the best traveling times, 
     346the following code can be used. 
     347 
     348\code 
     349  dijkstra(g, divMap(length, speed)).distMap(dist).run(s); 
     350\endcode 
     351 
    352352\code 
    353353  typedef vector<ListDigraph::Node> Container; 
     
    378378    .run(s); 
    379379\endcode 
     380 
     381Let us see a bit more complex example to demonstrate Dfs's capabilities. 
     382 
     383We will see a program, which solves the problem of <b>topological ordering</b>. 
     384We need to know in which order we should put on our clothes. The program will do the following: 
     385<ol> 
     386<li>We run the dfs algorithm to all nodes. 
     387<li>Put every node into a list when processed completely. 
     388<li>Write out the list in reverse order. 
     389</ol> 
     390 
     391\dontinclude topological_ordering.cc 
     392First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering 
     393will be done through it. 
     394\skip MyOrdererMap 
     395\until }; 
     396The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing 
     397we need to do is insert the key - that is the node whose processing just finished - into the beginning 
     398of the list.<br> 
     399Although we implemented this needed helper class ourselves it was not necessary. 
     400The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly 
     401what we needed. To be correct it's more general - and it's all in \c LEMON. But 
     402we wanted to show you, how easy is to add additional functionality. 
     403 
     404First we declare the needed data structures: the digraph and a map to store the nodes' label. 
     405\skip ListDigraph 
     406\until label 
     407 
     408Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological 
     409ordering. 
     410\skip belt 
     411\until trousers 
     412We label them... 
     413\skip label 
     414\until trousers 
     415Then add arcs which represent the precedences between those items. 
     416\skip trousers, belt 
     417\until ); 
     418 
     419See how easy is to access the internal information of this algorithm trough maps. 
     420We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap". 
     421\skip Dfs 
     422\until run 
     423 
     424And now comes the third part. Write out the list in reverse order. But the list was 
     425composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it. 
     426\skip std 
     427\until endl 
     428 
     429The program is to be found in the \ref demo directory: \ref topological_ordering.cc 
    380430 
    381431LEMON also contains visitor based algorithm classes for 
Note: See TracChangeset for help on using the changeset viewer.