Changeset 58:10b6a5b7d4c0 in lemontutorial
 Timestamp:
 03/01/10 02:30:00 (9 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

algorithms.dox
r57 r58 22 22 23 23 \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. 29 25 30 26 In addition to the graph structures, the most important parts of LEMON are 31 27 the various algorithms related to graph theory and combinatorial optimization. 32 28 The library provides quite flexible and efficient implementations 33 for wellknown fundamental algorithms, such as breadthfirst 34 search (BFS), depthfirst 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 arcdisjoint 38 paths. 29 for wellknown fundamental algorithms, such as \ref Bfs 30 "breadthfirst search (BFS)", \ref Dfs "depthfirst search (DFS)", 31 \ref Dijkstra "Dijkstra algorithm", \ref kruskal "Kruskal algorithm" 32 and methods for discovering \ref graph_properties "graph properties" like 33 connectivity, bipartiteness or Euler property, as well as more complex 34 optimization 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. 39 37 40 38 In this section, we present only some of the most fundamental algorithms. … … 43 41 [SEC]sec_graph_search[SEC] Graph Search 44 42 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: 43 The common graph search algorithms, namely \ref Bfs "breadthfirst search (BFS)" 44 and \ref Dfs "depthfirst search (DFS)" are implemented in highly adaptable and 45 efficient algorithm classes \ref Bfs and \ref Dfs. In LEMON, 46 the algorithms are typically placed in separated files, which are named after 47 the algorithm itself but with lower case like all other header files. 48 For example, we have to include <tt>bfs.h</tt> for using \ref Bfs. 49 50 \code 51 #include <lemon/bfs.h> 52 \endcode 53 54 Basically, all algorithms are implemented in template classes. 55 The template parameters typically specify the used graph type (for more 56 information, see \ref sec_graph_structures) and the required map types. 57 For 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 64 This class provides a simple but powerful interface to control the execution 65 of the algorithm and to obtain all the results. 66 You can execute the algorithm from a given source node by calling 67 the \ref Bfs::run() "run()" function. 68 69 \code 70 bfs.run(s); 71 \endcode 72 73 This operation finds the shortest paths from \c s to all other nodes. 74 If you are looking for an st path for a certain target node \c t, 75 you can also call the \ref Bfs::run() "run()" function with two 76 parameters. In this case, the BFS search will terminate once it has found 77 the shortest path from \c s to \c t. 78 79 \code 80 bfs.run(s,t); 81 \endcode 82 83 By default, the distances and the path information are stored in internal 84 maps, which you can access with member functions like \ref lemon::Bfs::distMap 85 "distMap()" and \ref lemon::Bfs::predMap() "predMap()" or more directly with 86 other 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 89 is finished, these query functions can be called. 90 91 For an example, let us say we want to print the shortest path of those nodes 92 that are at most in a certain distance \c max_dist. 71 93 \code 72 94 bfs.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 96 for (ListGraph::NodeIt n(g); n != INVALID; ++n) { 97 if (bfs.reached(n) && bfs.dist(n) <= max_dist) { 87 98 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) { 91 101 std::cout << "<" << gr.id(prev); 92 102 prev = bfs.prevNode(n); 103 } 104 std::cout << std::endl; 105 } 106 } 107 \endcode 108 109 The class interfaces of the algorithms also support a finer control on 110 the execution. For example, we can specify more source nodes and we can 111 even run the algorithm stepbystep. 112 If you need such control on the execution, you have to use more functions 113 instead 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 120 Then you can add one or more source nodes to the queue with 121 \ref Bfs::addSource() "addSource()". They will be processed, as they would 122 be reached by the algorithm before. And yes, you can even add more sources 123 during the execution. 124 125 \code 126 bfs.addSource(s1); 127 bfs.addSource(s2); 128 ... 129 \endcode 130 131 Finally, the actual path computation of the algorithm can be performed with 132 the \ref Bfs::start() "start()" function. 133 134 \code 135 bfs.start(t); 136 \endcode 137 138 Instead of using \ref Bfs::start() "start()", you can even execute the 139 algorithm stepbystep, so you can write your own loop to process the 140 nodes onebyone. 141 For example, the following code will executes the algorithm in such a way, 142 that it reaches all nodes in the digraph, namely the algorithm is started 143 for 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(); 93 151 } 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 onebyone. 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 functiontype interfaces 164 165 166 Since the DFS algorithm is very similar to BFS with a few tiny differences, 167 the \ref Dfs class can be used similarly to \ref Bfs. 174 168 175 169 176 170 [SEC]sec_shortest_paths[SEC] Shortest Paths 177 171 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> 172 If you would like to solve some transportation problems in a network, then 173 you will most likely want to find shortest paths between nodes of a graph. 174 This is usually solved using Dijkstra's algorithm. 175 The following code is a simple program using the LEMON \ref Dijkstra class 176 through the functiontype interface \ref dijkstra(). 177 It 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 190 182 191 183 In LEMON, the algorithms are implemented basically as classes, but … … 196 188 which can still be used quite flexibly due to named parameters. 197 189 198 The originalsample code could also use the class interface as follows.190 The above sample code could also use the class interface as follows. 199 191 200 192 \code … … 202 194 dijkstra.distMap(dist); 203 195 dijsktra.init(); 204 dijkstra.addSource( u);196 dijkstra.addSource(s); 205 197 dijkstra.start(); 206 198 \endcode … … 220 212 \endcode 221 213 214 LEMON provides several other algorithms for findign shortest paths in 215 specific or more general cases. For example, \ref BellmanFord can be used 216 instead of \ref Dijkstra when the graph contains an arc with negative cost. 217 You may check the \ref shortest_path module of the reference manual for 218 more details. 219 222 220 223 221 [SEC]sec_max_flow[SEC] Maximum Flows 224 222 225 223 See \ref Preflow. 224 225 \todo Write this subsection. 226 226 227 227 [TRAILER] 
maps.dox
r57 r58 36 36 These classes also conform to the map %concepts, thus they can be used 37 37 like standard LEMON maps. 38 39 Let us suppose that we have a traffic network stored in a LEMON digraph40 structure with two arc maps \c length and \c speed, which41 denote the physical length of each arc and the maximum (or average)42 speed that can be achieved on the corresponding roadsection,43 respectively. If we are interested in the best traveling times,44 the following code can be used.45 46 \code47 dijkstra(g, divMap(length, speed)).distMap(dist).run(s);48 \endcode49 50 38 51 39 Maps play a central role in LEMON. As their name suggests, they map a … … 336 324 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps 337 325 326 338 327 The basic functionality of the algorithms can be highly extended using 339 328 special purpose map types for their internal data structures. … … 350 339 they allow specifying any subset of the parameters and in arbitrary order. 351 340 341 Let us suppose that we have a traffic network stored in a LEMON digraph 342 structure with two arc maps \c length and \c speed, which 343 denote the physical length of each arc and the maximum (or average) 344 speed that can be achieved on the corresponding roadsection, 345 respectively. If we are interested in the best traveling times, 346 the following code can be used. 347 348 \code 349 dijkstra(g, divMap(length, speed)).distMap(dist).run(s); 350 \endcode 351 352 352 \code 353 353 typedef vector<ListDigraph::Node> Container; … … 378 378 .run(s); 379 379 \endcode 380 381 Let us see a bit more complex example to demonstrate Dfs's capabilities. 382 383 We will see a program, which solves the problem of <b>topological ordering</b>. 384 We 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 392 First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering 393 will be done through it. 394 \skip MyOrdererMap 395 \until }; 396 The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing 397 we need to do is insert the key  that is the node whose processing just finished  into the beginning 398 of the list.<br> 399 Although we implemented this needed helper class ourselves it was not necessary. 400 The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly 401 what we needed. To be correct it's more general  and it's all in \c LEMON. But 402 we wanted to show you, how easy is to add additional functionality. 403 404 First we declare the needed data structures: the digraph and a map to store the nodes' label. 405 \skip ListDigraph 406 \until label 407 408 Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological 409 ordering. 410 \skip belt 411 \until trousers 412 We label them... 413 \skip label 414 \until trousers 415 Then add arcs which represent the precedences between those items. 416 \skip trousers, belt 417 \until ); 418 419 See how easy is to access the internal information of this algorithm trough maps. 420 We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap". 421 \skip Dfs 422 \until run 423 424 And now comes the third part. Write out the list in reverse order. But the list was 425 composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it. 426 \skip std 427 \until endl 428 429 The program is to be found in the \ref demo directory: \ref topological_ordering.cc 380 430 381 431 LEMON also contains visitor based algorithm classes for
Note: See TracChangeset
for help on using the changeset viewer.