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 |
}
|