COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 58:10b6a5b7d4c0 in lemon-tutorial


Ignore:
Timestamp:
03/01/10 02:30:00 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improve Algorithms section (it is still under construction)

Files:
2 edited

Legend:

Unmodified
Added
Removed

  • algorithms.dox

    r57 r58  
    2222
    2323\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.
    2925
    3026In addition to the graph structures, the most important parts of LEMON are
    3127the various algorithms related to graph theory and combinatorial optimization.
    3228The library provides quite flexible and efficient implementations
    33 for well-known fundamental algorithms, such as breadth-first
    34 search (BFS), depth-first 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 arc-disjoint
    38 paths.
     29for well-known fundamental algorithms, such as \ref Bfs
     30"breadth-first search (BFS)", \ref Dfs "depth-first search (DFS)",
     31\ref Dijkstra "Dijkstra algorithm", \ref kruskal "Kruskal algorithm"
     32and methods for discovering \ref graph_properties "graph properties" like
     33connectivity, bipartiteness or Euler property, as well as more complex
     34optimization 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.
    3937
    4038In this section, we present only some of the most fundamental algorithms.
    … …  
    4341[SEC]sec_graph_search[SEC] Graph Search
    4442
    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:
     43The common graph search algorithms, namely \ref Bfs "breadth-first search (BFS)"
     44and \ref Dfs "depth-first search (DFS)" are implemented in highly adaptable and
     45efficient algorithm classes \ref Bfs and \ref Dfs. In LEMON,
     46the algorithms are typically placed in separated files, which are named after
     47the algorithm itself but with lower case like all other header files.
     48For example, we have to include <tt>bfs.h</tt> for using \ref Bfs.
     49
     50\code
     51   #include <lemon/bfs.h>
     52\endcode
     53
     54Basically, all algorithms are implemented in template classes.
     55The template parameters typically specify the used graph type (for more
     56information, see \ref sec_graph_structures) and the required map types.
     57For 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
     64This class provides a simple but powerful interface to control the execution
     65of the algorithm and to obtain all the results.
     66You can execute the algorithm from a given source node by calling
     67the \ref Bfs::run() "run()" function.
     68
     69\code
     70  bfs.run(s);
     71\endcode
     72
     73This operation finds the shortest paths from \c s to all other nodes.
     74If you are looking for an s-t path for a certain target node \c t,
     75you can also call the \ref Bfs::run() "run()" function with two
     76parameters. In this case, the BFS search will terminate once it has found
     77the shortest path from \c s to \c t.
     78
     79\code
     80  bfs.run(s,t);
     81\endcode
     82
     83By default, the distances and the path information are stored in internal
     84maps, which you can access with member functions like \ref lemon::Bfs::distMap
     85"distMap()" and \ref lemon::Bfs::predMap() "predMap()" or more directly with
     86other 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
     89is finished, these query functions can be called.
     90
     91For an example, let us say we want to print the shortest path of those nodes
     92that are at most in a certain distance \c max_dist.
    7193\code
    7294bfs.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
     96for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
     97  if (bfs.reached(n) && bfs.dist(n) <= max_dist) {
    8798    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) {
    91101      std::cout << "<-" << gr.id(prev);
    92102      prev = bfs.prevNode(n);
     103    }   
     104    std::cout << std::endl;
     105  }
     106}
     107\endcode
     108
     109The class interfaces of the algorithms also support a finer control on
     110the execution. For example, we can specify more source nodes and we can
     111even run the algorithm step-by-step.
     112If you need such control on the execution, you have to use more functions
     113instead 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
     120Then you can add one or more source nodes to the queue with
     121\ref Bfs::addSource() "addSource()". They will be processed, as they would
     122be reached by the algorithm before. And yes, you can even add more sources
     123during the execution.
     124
     125\code
     126  bfs.addSource(s1);
     127  bfs.addSource(s2);
     128  ...
     129\endcode
     130
     131Finally, the actual path computation of the algorithm can be performed with
     132the \ref Bfs::start() "start()" function.
     133
     134\code
     135  bfs.start(t);
     136\endcode
     137
     138Instead of using \ref Bfs::start() "start()", you can even execute the
     139algorithm step-by-step, so you can write your own loop to process the
     140nodes one-by-one.
     141For example, the following code will executes the algorithm in such a way,
     142that it reaches all nodes in the digraph, namely the algorithm is started
     143for 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();
    93151    }
    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 one-by-one.
    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 function-type interfaces
     164
     165
     166Since the DFS algorithm is very similar to BFS with a few tiny differences,
     167the \ref Dfs class can be used similarly to \ref Bfs.
    174168
    175169
    176170[SEC]sec_shortest_paths[SEC] Shortest Paths
    177171
    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>
     172If you would like to solve some transportation problems in a network, then
     173you will most likely want to find shortest paths between nodes of a graph.
     174This is usually solved using Dijkstra's algorithm.
     175The following code is a simple program using the LEMON \ref Dijkstra class
     176through the function-type interface \ref dijkstra().
     177It 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
    190182 
    191183In LEMON, the algorithms are implemented basically as classes, but
    … …  
    196188which can still be used quite flexibly due to named parameters.
    197189
    198 The original sample code could also use the class interface as follows.
     190The above sample code could also use the class interface as follows.
    199191
    200192\code
    … …  
    202194  dijkstra.distMap(dist);
    203195  dijsktra.init();
    204   dijkstra.addSource(u);
     196  dijkstra.addSource(s);
    205197  dijkstra.start();
    206198\endcode
    … …  
    220212\endcode
    221213
     214LEMON provides several other algorithms for findign shortest paths in
     215specific or more general cases. For example, \ref BellmanFord can be used
     216instead of \ref Dijkstra when the graph contains an arc with negative cost.
     217You may check the \ref shortest_path module of the reference manual for
     218more details.
     219
    222220
    223221[SEC]sec_max_flow[SEC] Maximum Flows
    224222
    225223See \ref Preflow.
     224
     225\todo Write this subsection.
    226226
    227227[TRAILER]

  • maps.dox

    r57 r58  
    3636These classes also conform to the map %concepts, thus they can be used
    3737like standard LEMON maps.
    38 
    39 Let us suppose that we have a traffic network stored in a LEMON digraph
    40 structure with two arc maps \c length and \c speed, which
    41 denote the physical length of each arc and the maximum (or average)
    42 speed that can be achieved on the corresponding road-section,
    43 respectively. If we are interested in the best traveling times,
    44 the following code can be used.
    45 
    46 \code
    47   dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
    48 \endcode
    49 
    5038
    5139Maps play a central role in LEMON. As their name suggests, they map a
    … …  
    336324[SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
    337325
     326
    338327The basic functionality of the algorithms can be highly extended using
    339328special purpose map types for their internal data structures.
    … …  
    350339they allow specifying any subset of the parameters and in arbitrary order.
    351340
     341Let us suppose that we have a traffic network stored in a LEMON digraph
     342structure with two arc maps \c length and \c speed, which
     343denote the physical length of each arc and the maximum (or average)
     344speed that can be achieved on the corresponding road-section,
     345respectively. If we are interested in the best traveling times,
     346the following code can be used.
     347
     348\code
     349  dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
     350\endcode
     351
    352352\code
    353353  typedef vector<ListDigraph::Node> Container;
    … …  
    378378    .run(s);
    379379\endcode
     380
     381Let us see a bit more complex example to demonstrate Dfs's capabilities.
     382
     383We will see a program, which solves the problem of <b>topological ordering</b>.
     384We 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
     392First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
     393will be done through it.
     394\skip MyOrdererMap
     395\until };
     396The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
     397we need to do is insert the key - that is the node whose processing just finished - into the beginning
     398of the list.<br>
     399Although we implemented this needed helper class ourselves it was not necessary.
     400The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
     401what we needed. To be correct it's more general - and it's all in \c LEMON. But
     402we wanted to show you, how easy is to add additional functionality.
     403
     404First we declare the needed data structures: the digraph and a map to store the nodes' label.
     405\skip ListDigraph
     406\until label
     407
     408Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
     409ordering.
     410\skip belt
     411\until trousers
     412We label them...
     413\skip label
     414\until trousers
     415Then add arcs which represent the precedences between those items.
     416\skip trousers, belt
     417\until );
     418
     419See how easy is to access the internal information of this algorithm trough maps.
     420We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
     421\skip Dfs
     422\until run
     423
     424And now comes the third part. Write out the list in reverse order. But the list was
     425composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
     426\skip std
     427\until endl
     428
     429The program is to be found in the \ref demo directory: \ref topological_ordering.cc
    380430
    381431LEMON also contains visitor based algorithm classes for
Note: See TracChangeset for help on using the changeset viewer.