COIN-OR::LEMON - Graph Library

Changeset 49:c8c5a2a4ec71 in lemon-tutorial


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

Port the remaining 0.x tutorial contents from SVN -r 3524

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • algorithms.dox

    r46 r49  
    2424 
    2525In 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. 
     26the various algorithms related to graph theory and combinatorial optimization. 
     27The library probvides quite flexible and efficient implementations 
     28for well-known fundamental algorithms, such as breadth-first 
     29search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm 
     30and methods for discovering graph properties like connectivity, bipartiteness 
     31or Euler property, as well as more complex optimization algorithms for finding 
     32maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint 
     33paths. 
    2834 
    2935In this section, we present only some of the most fundamental algorithms. 
     
    3238[SEC]sec_graph_search[SEC] Graph Search 
    3339 
     40\todo The following contents are ported from the LEMON 0.x tutorial, 
     41thus they have to thouroughly revised, reorganized and reworked. 
     42 
    3443See \ref Bfs, \ref Dfs and \ref graph_properties. 
    3544 
     45Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient 
     46implementations of the well known algorithms. The algorithms are placed most cases in 
     47separated files named after the algorithm itself but lower case as all other header file names. 
     48For example the next Bfs class is in the \c lemon/bfs.h. 
     49 
     50The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function. 
     51The class has two template parameters: \b GR and \b TR.<br> 
     52GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type. 
     53TR is a Traits class commonly used to easy the parametrization of templates. In most cases you 
     54wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>". 
     55 
     56To use the class, declare it! 
     57\code 
     58Bfs<ListGraph>  bfs(gr); 
     59\endcode 
     60Note the lack of second template argument because of the default parameter. 
     61 
     62It provides a simple but powerful interface to control the execution. 
     63\code 
     64int dist = bfs.run(s,t); 
     65\endcode 
     66It finds the shortest path from node \c s to node \c t and returns it, or zero 
     67if there is no path from \c s to \c t.<br> 
     68If you want the shortest path from a specified node to all other node, just write: 
     69\code 
     70bfs.run(s); 
     71\endcode 
     72Now the distances and path information are stored in maps which you can access with 
     73member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br> 
     74Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm 
     75is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode 
     76"predNode()" can be called. 
     77 
     78For an example let's say we want to print the shortest path of those nodes which 
     79are in a certain distance. 
     80\code 
     81bfs.run(s); 
     82 
     83for( 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 
     98In the previous code we only used \c run(). Now we introduce the way you can directly 
     99control the execution of the algorithm. 
     100 
     101First you have to initialize the variables with \ref lemon::Bfs::init "init()". 
     102\code 
     103  bfs.init(); 
     104\endcode 
     105 
     106Then you add one or more source nodes to the queue. They will be processed, as they would 
     107be 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 
     114And finally you can start the process with \ref lemon::Bfs::start "start()", or 
     115you can write your own loop to process the nodes one-by-one. 
     116 
     117 
     118Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example 
     119to demonstrate Dfs's capabilities. 
     120 
     121We will see a program, which solves the problem of <b>topological ordering</b>. 
     122We 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 
     130First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering 
     131will be done through it. 
     132\skip MyOrdererMap 
     133\until }; 
     134The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing 
     135we need to do is insert the key - that is the node whose processing just finished - into the beginning 
     136of the list.<br> 
     137Although we implemented this needed helper class ourselves it was not necessary. 
     138The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly 
     139what we needed. To be correct it's more general - and it's all in \c LEMON. But 
     140we wanted to show you, how easy is to add additional functionality. 
     141 
     142First we declare the needed data structures: the digraph and a map to store the nodes' label. 
     143\skip ListDigraph 
     144\until label 
     145 
     146Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological 
     147ordering. 
     148\skip belt 
     149\until trousers 
     150We label them... 
     151\skip label 
     152\until trousers 
     153Then add arcs which represent the precedences between those items. 
     154\skip trousers, belt 
     155\until ); 
     156 
     157See how easy is to access the internal information of this algorithm trough maps. 
     158We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap". 
     159\skip Dfs 
     160\until run 
     161 
     162And now comes the third part. Write out the list in reverse order. But the list was 
     163composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it. 
     164\skip std 
     165\until endl 
     166 
     167The 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 
     171More algorithms are described in the \ref algorithms2 "second part". 
     172 
     173 
    36174[SEC]sec_shortest_paths[SEC] Shortest Paths 
    37175 
    38176See \ref Dijkstra and \ref BellmanFord. 
     177 
     178 
     179If you want to solve some transportation problems in a network then you 
     180will want to find shortest paths between nodes of a graph. This is 
     181usually solved using Dijkstra's algorithm. A utility that solves this is 
     182the LEMON Dijkstra class. The following code is a simple program using 
     183the LEMON Dijkstra class: it calculates the shortest path between node s 
     184and t in a graph g. We omit the part reading the graph g and the length 
     185map len. 
     186 
     187<hr> 
     188  
     189In LEMON, the algorithms are implemented basically as classes, but 
     190for some of them, function-type interfaces are also available 
     191for the sake of convenience. 
     192For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra 
     193template class, but the \ref dijkstra() function is also defined, 
     194which can still be used quite flexibly due to named parameters. 
     195 
     196The 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 
     206The previous code is obviously longer than the original, but the 
     207execution can be controlled to a higher extent. While using the function-type 
     208interface, only one source can be added to the algorithm, the class 
     209interface makes it possible to specify several root nodes. 
     210Moreover, the algorithm can also be executed step-by-step. For instance, 
     211the 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 
    39220 
    40221[SEC]sec_max_flow[SEC] Maximum Flows 
  • maps.dox

    r46 r49  
    2323\todo This page is under construction. 
    2424 
     25\todo The following contents are ported from the LEMON 0.x tutorial, 
     26thus they have to thouroughly revised, reorganized and reworked. 
     27 
     28The LEMON maps are not only just storage classes, but also 
     29they are %concepts of any key--value based data access. 
     30Beside the standard digraph maps, LEMON contains several "lightweight" 
     31\e map \e adaptor \e classes, which perform various operations on the 
     32data of the adapted maps when their access operations are called, 
     33but without actually copying or modifying the original storage. 
     34These classes also conform to the map %concepts, thus they can be used 
     35like standard LEMON maps. 
     36 
     37Let us suppose that we have a traffic network stored in a LEMON digraph 
     38structure with two arc maps \c length and \c speed, which 
     39denote the physical length of each arc and the maximum (or average) 
     40speed that can be achieved on the corresponding road-section, 
     41respectively. If we are interested in the best traveling times, 
     42the following code can be used. 
     43 
     44\code 
     45  dijkstra(g, divMap(length, speed)).distMap(dist).run(s); 
     46\endcode 
     47 
     48 
     49Maps play a central role in LEMON. As their name suggests, they map a 
     50certain 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 
     58A 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"). 
     62There also exists a special type of 
     63ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map". 
     64In addition that you can 
     65read and write the values of a key, a reference map 
     66can also give you a reference to the 
     67value belonging to a key, so you have a direct access to the memory address 
     68where it is stored. 
     69 
     70Each digraph structure in LEMON provides two standard map templates called 
     71\c ArcMap and \c NodeMap. Both are reference maps and you can easily 
     72assign data to the nodes and to the arcs of the digraph. For example if you 
     73have a digraph \c g defined as 
     74\code 
     75  ListDigraph g; 
     76\endcode 
     77and you want to assign a floating point value to each arc, you can do 
     78it like this. 
     79\code 
     80  ListDigraph::ArcMap<double> length(g); 
     81\endcode 
     82Note that you must give the underlying digraph to the constructor. 
     83 
     84The value of a readable map can be obtained by <tt>operator[]</tt>. 
     85\code 
     86  d=length[e]; 
     87\endcode 
     88where \c e is an instance of \c ListDigraph::Arc. 
     89(Or anything else 
     90that converts to \c ListDigraph::Arc, like  \c ListDigraph::ArcIt or 
     91\c ListDigraph::OutArcIt etc.) 
     92 
     93There are two ways to assign a new value to a key 
     94 
     95- In case of a <em>reference map</em> <tt>operator[]</tt> 
     96gives you a reference to the 
     97value, thus you can use this. 
     98\code 
     99  length[e]=3.5; 
     100\endcode 
     101- <em>Writable maps</em> have 
     102a member function \c set(Key,const Value &) 
     103for this purpose. 
     104\code 
     105  length.set(e,3.5); 
     106\endcode 
     107 
     108The first case is more comfortable and if you store complex structures in your 
     109map, it might be more efficient. However, there are writable but 
     110not reference maps, so if you want to write a generic algorithm, you should 
     111insist on the second way. 
     112 
     113\section how-to-write-your-own-map How to Write Your Own Maps 
     114 
     115\subsection read-maps Readable Maps 
     116 
     117Readable maps are very frequently used as the input of an 
     118algorithm.  For this purpose the most straightforward way is the use of the 
     119default maps provided by LEMON's digraph structures. 
     120Very often however, it is more 
     121convenient and/or more efficient to write your own readable map. 
     122 
     123You can find some examples below. In these examples \c Digraph is the 
     124type of the particular digraph structure you use. 
     125 
     126 
     127This simple map assigns \f$\pi\f$ to each arc. 
     128 
     129\code 
     130struct MyMap  
     131{ 
     132  typedef double Value; 
     133  typedef Digraph::Arc Key; 
     134  double operator[](Key e) const { return PI;} 
     135}; 
     136\endcode 
     137 
     138An alternative way to define maps is to use \c MapBase 
     139 
     140\code 
     141struct MyMap : public MapBase<Digraph::Arc,double> 
     142{ 
     143  Value operator[](Key e) const { return PI;} 
     144}; 
     145\endcode 
     146 
     147Here is a bit more complex example. 
     148It provides a length function obtained 
     149from a base length function shifted by a potential difference. 
     150 
     151\code 
     152class 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   
     158public: 
     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 
     170Then, 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 
     180In the previous section we discussed digraph topology. That is the skeleton a complex 
     181digraph represented data-set needs. But how to assign the data itself to that skeleton?<br> 
     182Here come the \b maps in. 
     183 
     184\section maps_intro Introduction to maps 
     185Maps play a central role in LEMON. As their name suggests, they map a certain range of <i>keys</i> to certain <i>values</i>. 
     186In 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 
     193To 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 
     202readable 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 
     206providing you constant or non-constant reference to the value belonging to a key, 
     207so 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. 
     210The 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 
     217Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE> 
     218satisfying the \ref DigraphMap concept. 
     219If you want to assign data to nodes, just declare a NodeMap with the corresponding 
     220type. As an example, think of a arc-weighted digraph. 
     221\code ListDigraph::ArcMap<int>  weight(digraph); \endcode 
     222You can see that the map needs the digraph whose arcs will mapped, but nothing more. 
     223 
     224If the digraph class is extendable or erasable the map will automatically follow 
     225the changes you make. If a new node is added a default value is mapped to it. 
     226You can define the default value by passing a second argument to the map's constructor. 
     227\code ListDigraph::ArcMap<int>  weight(digraph, 13); \endcode 
     228But keep in mind that \c VALUE has to have copy constructor. 
     229 
     230Of course \c VALUE can be a rather complex type. 
     231 
     232For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)! 
     233\dontinclude maps_summary.cc 
     234\skip template 
     235\until } 
     236The 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 sub-digraph without changing 
     238this code. See \ref SubDigraph techniques - that's LEMON's true potential.) 
     239 
     240And the usage is simpler than the declaration suggests. The compiler deduces the 
     241template specialization, so the usage is like a simple function call. 
     242\skip std 
     243\until ; 
     244 
     245Most 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 
     247If you want some 'real-life' examples see the next page, where we discuss \ref algorithms 
     248(coming soon) and will use maps hardly. 
     249Or if you want to know more about maps read these \ref maps2 "advanced map techniques". 
     250 
     251Here we discuss some advanced map techniques. Like writing your own maps or how to 
     252extend/modify a maps functionality with adaptors. 
     253 
     254\section custom_maps Writing Custom ReadMap 
     255\subsection custom_read_maps Readable Maps 
     256 
     257Readable maps are very frequently used as the input of an 
     258algorithm.  For this purpose the most straightforward way is the use of the 
     259default maps provided by LEMON's digraph structures. 
     260Very often however, it is more 
     261convenient and/or more efficient to write your own readable map. 
     262 
     263You can find some examples below. In these examples \c Digraph is the 
     264type of the particular digraph structure you use. 
     265 
     266 
     267This simple map assigns \f$\pi\f$ to each arc. 
     268 
     269\code 
     270struct MyMap  
     271{ 
     272  typedef double Value; 
     273  typedef Digraph::Arc Key; 
     274  double operator[](const Key &e) const { return PI;} 
     275}; 
     276\endcode 
     277 
     278An alternative way to define maps is to use MapBase 
     279 
     280\code 
     281struct MyMap : public MapBase<Digraph::Arc,double> 
     282{ 
     283  Value operator[](const Key& e) const { return PI;} 
     284}; 
     285\endcode 
     286 
     287Here is a bit more complex example. 
     288It provides a length function obtained 
     289from a base length function shifted by a potential difference. 
     290 
     291\code 
     292class 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   
     298public: 
     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 
     310Then, 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 
    25320[SEC]sec_map_concepts[SEC] Map Concepts 
    26321 
     
    39334[SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps 
    40335 
    41 ... 
     336The basic functionality of the algorithms can be highly extended using 
     337special purpose map types for their internal data structures. 
     338For example, the \ref Dijkstra class stores a  
     339ef ProcessedMap, 
     340which has to be a writable node map of \ref bool value type. 
     341The assigned value of each node is set to \ref true when the node is 
     342processed, i.e., its actual distance is found. 
     343Applying a special map, \ref LoggerBoolMap, the processed order of 
     344the nodes can easily be stored in a standard container. 
     345 
     346Such specific map types can be passed to the algorithms using the technique of 
     347named template parameters. Similarly to the named function parameters, 
     348they 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 
     365The function-type interfaces are considerably simpler, but they can be 
     366used in almost all practical cases. Surprisingly, even the above example 
     367can also be implemented using the \ref dijkstra() function and 
     368named parameters, as follows. 
     369Note that the function-type interface has the major advantage 
     370that 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 
     379LEMON also contains visitor based algorithm classes for 
     380BFS and DFS. 
     381 
     382Skeleton visitor classes are defined for both BFS and DFS, the concrete 
     383implementations 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 
     397In the following example, the \ref discover()} and \code{examine() 
     398events are processed and the DFS tree is stored in an arc map. 
     399The values of this map indicate whether the corresponding arc 
     400reaches 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 
    42414 
    43415[TRAILER] 
Note: See TracChangeset for help on using the changeset viewer.