Changeset 49:c8c5a2a4ec71 in lemontutorial
 Timestamp:
 02/22/10 02:03:25 (8 years ago)
 Branch:
 default
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

algorithms.dox
r46 r49 24 24 25 25 In addition to the graph structures, the most important parts of LEMON are 26 the various algorithm implementations, which can be used quite flexibly and 27 efficiently. 26 the various algorithms related to graph theory and combinatorial optimization. 27 The library probvides quite flexible and efficient implementations 28 for wellknown fundamental algorithms, such as breadthfirst 29 search (BFS), depthfirst 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 arcdisjoint 33 paths. 28 34 29 35 In this section, we present only some of the most fundamental algorithms. … … 32 38 [SEC]sec_graph_search[SEC] Graph Search 33 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 34 43 See \ref Bfs, \ref Dfs and \ref graph_properties. 35 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 onebyone. 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 36 174 [SEC]sec_shortest_paths[SEC] Shortest Paths 37 175 38 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, functiontype 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> dijktra(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 functiontype 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 stepbystep. 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 39 220 40 221 [SEC]sec_max_flow[SEC] Maximum Flows 
maps.dox
r46 r49 23 23 \todo This page is under construction. 24 24 25 \todo The following contents are ported from the LEMON 0.x tutorial, 26 thus they have to thouroughly revised, reorganized and reworked. 27 28 The LEMON maps are not only just storage classes, but also 29 they are %concepts of any keyvalue based data access. 30 Beside the standard digraph maps, LEMON contains several "lightweight" 31 \e map \e adaptor \e classes, which perform various operations on the 32 data of the adapted maps when their access operations are called, 33 but without actually copying or modifying the original storage. 34 These classes also conform to the map %concepts, thus they can be used 35 like standard LEMON maps. 36 37 Let us suppose that we have a traffic network stored in a LEMON digraph 38 structure with two arc maps \c length and \c speed, which 39 denote the physical length of each arc and the maximum (or average) 40 speed that can be achieved on the corresponding roadsection, 41 respectively. If we are interested in the best traveling times, 42 the following code can be used. 43 44 \code 45 dijkstra(g, divMap(length, speed)).distMap(dist).run(s); 46 \endcode 47 48 49 Maps play a central role in LEMON. As their name suggests, they map a 50 certain range of \e keys to certain \e values. Each map has two 51 <tt>typedef</tt>'s to determine the types of keys and values, like this: 52 53 \code 54 typedef Arc Key; 55 typedef double Value; 56 \endcode 57 58 A map can be 59 \e readable (\ref lemon::concepts::ReadMap "ReadMap", for short), 60 \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both 61 (\ref lemon::concepts::ReadWriteMap "ReadWriteMap"). 62 There also exists a special type of 63 ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map". 64 In addition that you can 65 read and write the values of a key, a reference map 66 can also give you a reference to the 67 value belonging to a key, so you have a direct access to the memory address 68 where it is stored. 69 70 Each digraph structure in LEMON provides two standard map templates called 71 \c ArcMap and \c NodeMap. Both are reference maps and you can easily 72 assign data to the nodes and to the arcs of the digraph. For example if you 73 have a digraph \c g defined as 74 \code 75 ListDigraph g; 76 \endcode 77 and you want to assign a floating point value to each arc, you can do 78 it like this. 79 \code 80 ListDigraph::ArcMap<double> length(g); 81 \endcode 82 Note that you must give the underlying digraph to the constructor. 83 84 The value of a readable map can be obtained by <tt>operator[]</tt>. 85 \code 86 d=length[e]; 87 \endcode 88 where \c e is an instance of \c ListDigraph::Arc. 89 (Or anything else 90 that converts to \c ListDigraph::Arc, like \c ListDigraph::ArcIt or 91 \c ListDigraph::OutArcIt etc.) 92 93 There are two ways to assign a new value to a key 94 95  In case of a <em>reference map</em> <tt>operator[]</tt> 96 gives you a reference to the 97 value, thus you can use this. 98 \code 99 length[e]=3.5; 100 \endcode 101  <em>Writable maps</em> have 102 a member function \c set(Key,const Value &) 103 for this purpose. 104 \code 105 length.set(e,3.5); 106 \endcode 107 108 The first case is more comfortable and if you store complex structures in your 109 map, it might be more efficient. However, there are writable but 110 not reference maps, so if you want to write a generic algorithm, you should 111 insist on the second way. 112 113 \section howtowriteyourownmap How to Write Your Own Maps 114 115 \subsection readmaps Readable Maps 116 117 Readable maps are very frequently used as the input of an 118 algorithm. For this purpose the most straightforward way is the use of the 119 default maps provided by LEMON's digraph structures. 120 Very often however, it is more 121 convenient and/or more efficient to write your own readable map. 122 123 You can find some examples below. In these examples \c Digraph is the 124 type of the particular digraph structure you use. 125 126 127 This simple map assigns \f$\pi\f$ to each arc. 128 129 \code 130 struct MyMap 131 { 132 typedef double Value; 133 typedef Digraph::Arc Key; 134 double operator[](Key e) const { return PI;} 135 }; 136 \endcode 137 138 An alternative way to define maps is to use \c MapBase 139 140 \code 141 struct MyMap : public MapBase<Digraph::Arc,double> 142 { 143 Value operator[](Key e) const { return PI;} 144 }; 145 \endcode 146 147 Here is a bit more complex example. 148 It provides a length function obtained 149 from a base length function shifted by a potential difference. 150 151 \code 152 class ReducedLengthMap : public MapBase<Digraph::Arc,double> 153 { 154 const Digraph &g; 155 const Digraph::ArcMap<double> &orig_len; 156 const Digraph::NodeMap<double> &pot; 157 158 public: 159 Value operator[](Key e) const { 160 return orig_len[e](pot[g.target(e)]pot[g.source(e)]); 161 } 162 163 ReducedLengthMap(const Digraph &_g, 164 const Digraph::ArcMap &_o, 165 const Digraph::NodeMap &_p) 166 : g(_g), orig_len(_o), pot(_p) {}; 167 }; 168 \endcode 169 170 Then, you can call e.g. Dijkstra algoritm on this map like this: 171 \code 172 ... 173 ReducedLengthMap rm(g,len,pot); 174 Dijkstra<Digraph,ReducedLengthMap> dij(g,rm); 175 dij.run(s); 176 ... 177 \endcode 178 179 180 In the previous section we discussed digraph topology. That is the skeleton a complex 181 digraph represented dataset needs. But how to assign the data itself to that skeleton?<br> 182 Here come the \b maps in. 183 184 \section maps_intro Introduction to maps 185 Maps play a central role in LEMON. As their name suggests, they map a certain range of <i>keys</i> to certain <i>values</i>. 186 In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this: 187 \code 188 typedef Arc Key; 189 typedef double Value; 190 \endcode 191 (Except matrix maps, they have two key types.) 192 193 To make easy to use them  especially as template parameters  there are <i>map concepts</i> like by digraph classes. 194 <ul> 195 <li>\ref concepts::ReadMap "ReadMap"  values can be read out with the \c operator[]. 196 \code value_typed_variable = map_instance[key_value]; \endcode 197 </li> 198 <li>\ref concepts::WriteMap "WriteMap"  values can be set with the \c set() member function. 199 \code map_instance.set(key_value, value_typed_expression); \endcode 200 </li> 201 <li>\ref concepts::ReadWriteMap "ReadWriteMap"  it's just a shortcut to indicate that the map is both 202 readable and writable. It is delivered from them. 203 </li> 204 <li>\ref concepts::ReferenceMap "ReferenceMap"  a subclass of ReadWriteMap. It has two additional typedefs 205 <i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to 206 providing you constant or nonconstant reference to the value belonging to a key, 207 so you have a direct access to the memory address where it is stored. 208 </li> 209 <li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys. 210 The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap", 211 \ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap", 212 \ref concepts::ReferenceMatrixMap "ReferenceMatrixMap") 213 </li> 214 </ul> 215 216 \section maps_graph Digraphs' maps 217 Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE> 218 satisfying the \ref DigraphMap concept. 219 If you want to assign data to nodes, just declare a NodeMap with the corresponding 220 type. As an example, think of a arcweighted digraph. 221 \code ListDigraph::ArcMap<int> weight(digraph); \endcode 222 You can see that the map needs the digraph whose arcs will mapped, but nothing more. 223 224 If the digraph class is extendable or erasable the map will automatically follow 225 the changes you make. If a new node is added a default value is mapped to it. 226 You can define the default value by passing a second argument to the map's constructor. 227 \code ListDigraph::ArcMap<int> weight(digraph, 13); \endcode 228 But keep in mind that \c VALUE has to have copy constructor. 229 230 Of course \c VALUE can be a rather complex type. 231 232 For practice let's see the following template function (from \ref maps_summary "mapssummary.cc" in the \ref demo directory)! 233 \dontinclude maps_summary.cc 234 \skip template 235 \until } 236 The task is simple. We need the summary of some kind of data assigned to a digraph's nodes. 237 (Whit a little trick the summary can be calculated only to a subdigraph without changing 238 this code. See \ref SubDigraph techniques  that's LEMON's true potential.) 239 240 And the usage is simpler than the declaration suggests. The compiler deduces the 241 template specialization, so the usage is like a simple function call. 242 \skip std 243 \until ; 244 245 Most of the time you will probably use digraph maps, but keep in mind, that in LEMON maps are more general and can be used widely. 246 247 If you want some 'reallife' examples see the next page, where we discuss \ref algorithms 248 (coming soon) and will use maps hardly. 249 Or if you want to know more about maps read these \ref maps2 "advanced map techniques". 250 251 Here we discuss some advanced map techniques. Like writing your own maps or how to 252 extend/modify a maps functionality with adaptors. 253 254 \section custom_maps Writing Custom ReadMap 255 \subsection custom_read_maps Readable Maps 256 257 Readable maps are very frequently used as the input of an 258 algorithm. For this purpose the most straightforward way is the use of the 259 default maps provided by LEMON's digraph structures. 260 Very often however, it is more 261 convenient and/or more efficient to write your own readable map. 262 263 You can find some examples below. In these examples \c Digraph is the 264 type of the particular digraph structure you use. 265 266 267 This simple map assigns \f$\pi\f$ to each arc. 268 269 \code 270 struct MyMap 271 { 272 typedef double Value; 273 typedef Digraph::Arc Key; 274 double operator[](const Key &e) const { return PI;} 275 }; 276 \endcode 277 278 An alternative way to define maps is to use MapBase 279 280 \code 281 struct MyMap : public MapBase<Digraph::Arc,double> 282 { 283 Value operator[](const Key& e) const { return PI;} 284 }; 285 \endcode 286 287 Here is a bit more complex example. 288 It provides a length function obtained 289 from a base length function shifted by a potential difference. 290 291 \code 292 class ReducedLengthMap : public MapBase<Digraph::Arc,double> 293 { 294 const Digraph &g; 295 const Digraph::ArcMap<double> &orig_len; 296 const Digraph::NodeMap<double> &pot; 297 298 public: 299 Value operator[](Key e) const { 300 return orig_len[e](pot[g.target(e)]pot[g.source(e)]); 301 } 302 303 ReducedLengthMap(const Digraph &_g, 304 const Digraph::ArcMap &_o, 305 const Digraph::NodeMap &_p) 306 : g(_g), orig_len(_o), pot(_p) {}; 307 }; 308 \endcode 309 310 Then, you can call e.g. Dijkstra algoritm on this map like this: 311 \code 312 ... 313 ReducedLengthMap rm(g,len,pot); 314 Dijkstra<Digraph,ReducedLengthMap> dij(g,rm); 315 dij.run(s); 316 ... 317 \endcode 318 319 25 320 [SEC]sec_map_concepts[SEC] Map Concepts 26 321 … … 39 334 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps 40 335 41 ... 336 The basic functionality of the algorithms can be highly extended using 337 special purpose map types for their internal data structures. 338 For example, the \ref Dijkstra class stores a 339 ef ProcessedMap, 340 which has to be a writable node map of \ref bool value type. 341 The assigned value of each node is set to \ref true when the node is 342 processed, i.e., its actual distance is found. 343 Applying a special map, \ref LoggerBoolMap, the processed order of 344 the nodes can easily be stored in a standard container. 345 346 Such specific map types can be passed to the algorithms using the technique of 347 named template parameters. Similarly to the named function parameters, 348 they allow specifying any subset of the parameters and in arbitrary order. 349 350 \code 351 typedef vector<ListDigraph::Node> Container; 352 typedef back_insert_iterator<Container> InsertIterator; 353 typedef LoggerBoolMap<InsertIterator> ProcessedMap; 354 Dijkstra<ListDigraph> 355 ::SetProcessedMap<ProcessedMap> 356 ::Create dijktra(g, length); 357 358 Container container; 359 InsertIterator iterator(container); 360 ProcessedMap processed(iterator); 361 362 dijkstra.processedMap(processed).run(s); 363 \endcode 364 365 The functiontype interfaces are considerably simpler, but they can be 366 used in almost all practical cases. Surprisingly, even the above example 367 can also be implemented using the \ref dijkstra() function and 368 named parameters, as follows. 369 Note that the functiontype interface has the major advantage 370 that temporary objects can be passed as parameters. 371 372 \code 373 vector<ListDigraph::Node> process_order; 374 dijkstra(g, length) 375 .processedMap(loggerBoolMap(back_inserter(process_order))) 376 .run(s); 377 \endcode 378 379 LEMON also contains visitor based algorithm classes for 380 BFS and DFS. 381 382 Skeleton visitor classes are defined for both BFS and DFS, the concrete 383 implementations can be inherited from them. 384 \code 385 template <typename GR> 386 struct DfsVisitor { 387 void start(const typename GR::Node& node) {} 388 void stop(const typename GR::Node& node) {} 389 void reach(const typename GR::Node& node) {} 390 void leave(const typename GR::Node& node) {} 391 void discover(const typename GR::Arc& arc) {} 392 void examine(const typename GR::Arc& arc) {} 393 void backtrack(const typename GR::Arc& arc) {} 394 }; 395 \endcode 396 397 In the following example, the \ref discover()} and \code{examine() 398 events are processed and the DFS tree is stored in an arc map. 399 The values of this map indicate whether the corresponding arc 400 reaches a new node or its target node is already reached. 401 \code 402 template <typename GR> 403 struct TreeVisitor : public DfsVisitor<GR> { 404 TreeVisitor(typename GR::ArcMap<bool>& tree) 405 : _tree(tree) {} 406 void discover(const typename GR::Arc& arc) 407 { _tree[arc] = true; } 408 void examine(const typename GR::Arc& arc) 409 { _tree[arc] = false; } 410 typename GR::ArcMap<bool>& _tree; 411 }; 412 \endcode 413 42 414 43 415 [TRAILER]
Note: See TracChangeset
for help on using the changeset viewer.