COIN-OR::LEMON - Graph Library

Changeset 49:c8c5a2a4ec71 in lemon-tutorial for algorithms.dox


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

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

File:
1 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
Note: See TracChangeset for help on using the changeset viewer.