COIN-OR::LEMON - Graph Library

Changeset 49:c8c5a2a4ec71 in lemon-tutorial


Ignore:
Timestamp:
02/22/10 02:03:25 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
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.