algorithms.dox
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 28 Feb 2010 19:38:57 +0100
changeset 53 0f695eac7e07
parent 49 c8c5a2a4ec71
child 57 18404ec968ca
permissions -rw-r--r--
Show demo files in the menu
kpeter@46
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@46
     2
 *
kpeter@46
     3
 * This file is a part of LEMON, a generic C++ optimization library.
kpeter@46
     4
 *
kpeter@46
     5
 * Copyright (C) 2003-2010
kpeter@46
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@46
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@46
     8
 *
kpeter@46
     9
 * Permission to use, modify and distribute this software is granted
kpeter@46
    10
 * provided that this copyright notice appears in all copies. For
kpeter@46
    11
 * precise terms see the accompanying LICENSE file.
kpeter@46
    12
 *
kpeter@46
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@46
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@46
    15
 * purpose.
kpeter@46
    16
 *
kpeter@46
    17
 */
kpeter@46
    18
kpeter@46
    19
namespace lemon {
kpeter@46
    20
/**
kpeter@46
    21
[PAGE]sec_algorithms[PAGE] Algorithms
kpeter@46
    22
kpeter@46
    23
\todo This page is under construction.
kpeter@46
    24
kpeter@46
    25
In addition to the graph structures, the most important parts of LEMON are
kpeter@49
    26
the various algorithms related to graph theory and combinatorial optimization.
kpeter@49
    27
The library probvides quite flexible and efficient implementations
kpeter@49
    28
for well-known fundamental algorithms, such as breadth-first
kpeter@49
    29
search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm
kpeter@49
    30
and methods for discovering graph properties like connectivity, bipartiteness
kpeter@49
    31
or Euler property, as well as more complex optimization algorithms for finding
kpeter@49
    32
maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint
kpeter@49
    33
paths.
kpeter@46
    34
kpeter@46
    35
In this section, we present only some of the most fundamental algorithms.
kpeter@46
    36
For a complete overview, see the \ref algs module of the reference manual.
kpeter@46
    37
kpeter@46
    38
[SEC]sec_graph_search[SEC] Graph Search
kpeter@46
    39
kpeter@49
    40
\todo The following contents are ported from the LEMON 0.x tutorial,
kpeter@49
    41
thus they have to thouroughly revised, reorganized and reworked.
kpeter@49
    42
kpeter@46
    43
See \ref Bfs, \ref Dfs and \ref graph_properties.
kpeter@46
    44
kpeter@49
    45
Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
kpeter@49
    46
implementations of the well known algorithms. The algorithms are placed most cases in
kpeter@49
    47
separated files named after the algorithm itself but lower case as all other header file names.
kpeter@49
    48
For example the next Bfs class is in the \c lemon/bfs.h.
kpeter@49
    49
kpeter@49
    50
The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
kpeter@49
    51
The class has two template parameters: \b GR and \b TR.<br>
kpeter@49
    52
GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type.
kpeter@49
    53
TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
kpeter@49
    54
wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
kpeter@49
    55
kpeter@49
    56
To use the class, declare it!
kpeter@49
    57
\code
kpeter@49
    58
Bfs<ListGraph>  bfs(gr);
kpeter@49
    59
\endcode
kpeter@49
    60
Note the lack of second template argument because of the default parameter.
kpeter@49
    61
kpeter@49
    62
It provides a simple but powerful interface to control the execution.
kpeter@49
    63
\code
kpeter@49
    64
int dist = bfs.run(s,t);
kpeter@49
    65
\endcode
kpeter@49
    66
It finds the shortest path from node \c s to node \c t and returns it, or zero
kpeter@49
    67
if there is no path from \c s to \c t.<br>
kpeter@49
    68
If you want the shortest path from a specified node to all other node, just write:
kpeter@49
    69
\code
kpeter@49
    70
bfs.run(s);
kpeter@49
    71
\endcode
kpeter@49
    72
Now the distances and path information are stored in maps which you can access with
kpeter@49
    73
member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
kpeter@49
    74
Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm
kpeter@49
    75
is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
kpeter@49
    76
"predNode()" can be called.
kpeter@49
    77
kpeter@49
    78
For an example let's say we want to print the shortest path of those nodes which
kpeter@49
    79
are in a certain distance.
kpeter@49
    80
\code
kpeter@49
    81
bfs.run(s);
kpeter@49
    82
kpeter@49
    83
for( ListGraph::NodeIt  n(gr); n != INVALID; ++n ) {
kpeter@49
    84
  if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
kpeter@49
    85
    std::cout << gr.id(n);
kpeter@49
    86
kpeter@49
    87
    Node  prev = bfs.prevNode(n);
kpeter@49
    88
    while( prev != INVALID ) {
kpeter@49
    89
      std::cout << "<-" << gr.id(prev);
kpeter@49
    90
      prev = bfs.prevNode(n);
kpeter@49
    91
    }
kpeter@49
    92
    
kpeter@49
    93
    std::cout << std::endl;
kpeter@49
    94
  }
kpeter@49
    95
}
kpeter@49
    96
\endcode
kpeter@49
    97
kpeter@49
    98
In the previous code we only used \c run(). Now we introduce the way you can directly
kpeter@49
    99
control the execution of the algorithm.
kpeter@49
   100
kpeter@49
   101
First you have to initialize the variables with \ref lemon::Bfs::init "init()".
kpeter@49
   102
\code
kpeter@49
   103
  bfs.init();
kpeter@49
   104
\endcode
kpeter@49
   105
kpeter@49
   106
Then you add one or more source nodes to the queue. They will be processed, as they would
kpeter@49
   107
be reached by the algorithm before. And yes - you can add more sources during the execution.
kpeter@49
   108
\code
kpeter@49
   109
  bfs.addSource(node_1);
kpeter@49
   110
  bfs.addSource(node_2);
kpeter@49
   111
  ...
kpeter@49
   112
\endcode
kpeter@49
   113
kpeter@49
   114
And finally you can start the process with \ref lemon::Bfs::start "start()", or
kpeter@49
   115
you can write your own loop to process the nodes one-by-one.
kpeter@49
   116
kpeter@49
   117
kpeter@49
   118
Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
kpeter@49
   119
to demonstrate Dfs's capabilities.
kpeter@49
   120
kpeter@49
   121
We will see a program, which solves the problem of <b>topological ordering</b>.
kpeter@49
   122
We need to know in which order we should put on our clothes. The program will do the following:
kpeter@49
   123
<ol>
kpeter@49
   124
<li>We run the dfs algorithm to all nodes.
kpeter@49
   125
<li>Put every node into a list when processed completely.
kpeter@49
   126
<li>Write out the list in reverse order.
kpeter@49
   127
</ol>
kpeter@49
   128
kpeter@49
   129
\dontinclude topological_ordering.cc
kpeter@49
   130
First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
kpeter@49
   131
will be done through it.
kpeter@49
   132
\skip MyOrdererMap
kpeter@49
   133
\until };
kpeter@49
   134
The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
kpeter@49
   135
we need to do is insert the key - that is the node whose processing just finished - into the beginning
kpeter@49
   136
of the list.<br>
kpeter@49
   137
Although we implemented this needed helper class ourselves it was not necessary.
kpeter@49
   138
The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
kpeter@49
   139
what we needed. To be correct it's more general - and it's all in \c LEMON. But
kpeter@49
   140
we wanted to show you, how easy is to add additional functionality.
kpeter@49
   141
kpeter@49
   142
First we declare the needed data structures: the digraph and a map to store the nodes' label.
kpeter@49
   143
\skip ListDigraph
kpeter@49
   144
\until label
kpeter@49
   145
kpeter@49
   146
Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
kpeter@49
   147
ordering.
kpeter@49
   148
\skip belt
kpeter@49
   149
\until trousers
kpeter@49
   150
We label them...
kpeter@49
   151
\skip label
kpeter@49
   152
\until trousers
kpeter@49
   153
Then add arcs which represent the precedences between those items.
kpeter@49
   154
\skip trousers, belt
kpeter@49
   155
\until );
kpeter@49
   156
kpeter@49
   157
See how easy is to access the internal information of this algorithm trough maps.
kpeter@49
   158
We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
kpeter@49
   159
\skip Dfs
kpeter@49
   160
\until run
kpeter@49
   161
kpeter@49
   162
And now comes the third part. Write out the list in reverse order. But the list was
kpeter@49
   163
composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
kpeter@49
   164
\skip std
kpeter@49
   165
\until endl
kpeter@49
   166
kpeter@49
   167
The program is to be found in the \ref demo directory: \ref topological_ordering.cc
kpeter@49
   168
kpeter@49
   169
\todo Check the linking of the demo file, the code samples are missing.
kpeter@49
   170
kpeter@49
   171
More algorithms are described in the \ref algorithms2 "second part".
kpeter@49
   172
kpeter@49
   173
kpeter@46
   174
[SEC]sec_shortest_paths[SEC] Shortest Paths
kpeter@46
   175
kpeter@46
   176
See \ref Dijkstra and \ref BellmanFord.
kpeter@46
   177
kpeter@49
   178
kpeter@49
   179
If you want to solve some transportation problems in a network then you
kpeter@49
   180
will want to find shortest paths between nodes of a graph. This is
kpeter@49
   181
usually solved using Dijkstra's algorithm. A utility that solves this is
kpeter@49
   182
the LEMON Dijkstra class. The following code is a simple program using
kpeter@49
   183
the LEMON Dijkstra class: it calculates the shortest path between node s
kpeter@49
   184
and t in a graph g. We omit the part reading the graph g and the length
kpeter@49
   185
map len.
kpeter@49
   186
kpeter@49
   187
<hr>
kpeter@49
   188
 
kpeter@49
   189
In LEMON, the algorithms are implemented basically as classes, but
kpeter@49
   190
for some of them, function-type interfaces are also available
kpeter@49
   191
for the sake of convenience.
kpeter@49
   192
For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra
kpeter@49
   193
template class, but the \ref dijkstra() function is also defined,
kpeter@49
   194
which can still be used quite flexibly due to named parameters.
kpeter@49
   195
kpeter@49
   196
The original sample code could also use the class interface as follows.
kpeter@49
   197
kpeter@49
   198
\code
kpeter@50
   199
  Dijkstra<ListDigraph> dijkstra(g, length);
kpeter@49
   200
  dijkstra.distMap(dist);
kpeter@49
   201
  dijsktra.init();
kpeter@49
   202
  dijkstra.addSource(u);
kpeter@49
   203
  dijkstra.start();
kpeter@49
   204
\endcode
kpeter@49
   205
kpeter@49
   206
The previous code is obviously longer than the original, but the
kpeter@49
   207
execution can be controlled to a higher extent. While using the function-type
kpeter@49
   208
interface, only one source can be added to the algorithm, the class
kpeter@49
   209
interface makes it possible to specify several root nodes.
kpeter@49
   210
Moreover, the algorithm can also be executed step-by-step. For instance,
kpeter@49
   211
the following code can be used instead of \ref dijkstra.start().
kpeter@49
   212
kpeter@49
   213
\code
kpeter@49
   214
  while (!dijkstra.emptyQueue()) {
kpeter@49
   215
    ListDigraph::Node n = dijkstra.processNextNode();
kpeter@49
   216
    cout << g.id(n) << ' ' << dijkstra.dist(g) << endl;
kpeter@49
   217
  }
kpeter@49
   218
\endcode
kpeter@49
   219
kpeter@49
   220
kpeter@46
   221
[SEC]sec_max_flow[SEC] Maximum Flows
kpeter@46
   222
kpeter@46
   223
See \ref Preflow.
kpeter@46
   224
kpeter@46
   225
[TRAILER]
kpeter@46
   226
*/
kpeter@46
   227
}