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@58
|
24 |
\todo This section should be revised and extended.
|
kpeter@57
|
25 |
|
kpeter@46
|
26 |
In addition to the graph structures, the most important parts of LEMON are
|
kpeter@49
|
27 |
the various algorithms related to graph theory and combinatorial optimization.
|
kpeter@57
|
28 |
The library provides quite flexible and efficient implementations
|
kpeter@58
|
29 |
for well-known fundamental algorithms, such as \ref Bfs
|
kpeter@58
|
30 |
"breadth-first search (BFS)", \ref Dfs "depth-first search (DFS)",
|
kpeter@58
|
31 |
\ref Dijkstra "Dijkstra algorithm", \ref kruskal "Kruskal algorithm"
|
kpeter@58
|
32 |
and methods for discovering \ref graph_properties "graph properties" like
|
kpeter@58
|
33 |
connectivity, bipartiteness or Euler property, as well as more complex
|
kpeter@58
|
34 |
optimization algorithms for finding \ref max_flow "maximum flows",
|
kpeter@58
|
35 |
\ref min_cut "minimum cuts", \ref matching "matchings",
|
kpeter@58
|
36 |
\ref min_cost_flow_algs "minimum cost flows" etc.
|
kpeter@46
|
37 |
|
kpeter@46
|
38 |
In this section, we present only some of the most fundamental algorithms.
|
kpeter@46
|
39 |
For a complete overview, see the \ref algs module of the reference manual.
|
kpeter@46
|
40 |
|
kpeter@46
|
41 |
[SEC]sec_graph_search[SEC] Graph Search
|
kpeter@46
|
42 |
|
kpeter@58
|
43 |
The common graph search algorithms, namely \ref Bfs "breadth-first search (BFS)"
|
kpeter@58
|
44 |
and \ref Dfs "depth-first search (DFS)" are implemented in highly adaptable and
|
kpeter@58
|
45 |
efficient algorithm classes \ref Bfs and \ref Dfs. In LEMON,
|
kpeter@58
|
46 |
the algorithms are typically placed in separated files, which are named after
|
kpeter@58
|
47 |
the algorithm itself but with lower case like all other header files.
|
kpeter@58
|
48 |
For example, we have to include <tt>bfs.h</tt> for using \ref Bfs.
|
kpeter@46
|
49 |
|
kpeter@58
|
50 |
\code
|
kpeter@58
|
51 |
#include <lemon/bfs.h>
|
kpeter@58
|
52 |
\endcode
|
kpeter@49
|
53 |
|
kpeter@58
|
54 |
Basically, all algorithms are implemented in template classes.
|
kpeter@58
|
55 |
The template parameters typically specify the used graph type (for more
|
kpeter@58
|
56 |
information, see \ref sec_graph_structures) and the required map types.
|
kpeter@58
|
57 |
For example, an instance of the \ref BFs class can be created like this.
|
kpeter@49
|
58 |
|
kpeter@49
|
59 |
\code
|
kpeter@58
|
60 |
ListDigraph g;
|
kpeter@58
|
61 |
Bfs<ListDigraph> bfs(g);
|
kpeter@49
|
62 |
\endcode
|
kpeter@49
|
63 |
|
kpeter@58
|
64 |
This class provides a simple but powerful interface to control the execution
|
kpeter@58
|
65 |
of the algorithm and to obtain all the results.
|
kpeter@58
|
66 |
You can execute the algorithm from a given source node by calling
|
kpeter@58
|
67 |
the \ref Bfs::run() "run()" function.
|
kpeter@58
|
68 |
|
kpeter@49
|
69 |
\code
|
kpeter@58
|
70 |
bfs.run(s);
|
kpeter@49
|
71 |
\endcode
|
kpeter@58
|
72 |
|
kpeter@58
|
73 |
This operation finds the shortest paths from \c s to all other nodes.
|
kpeter@58
|
74 |
If you are looking for an s-t path for a certain target node \c t,
|
kpeter@58
|
75 |
you can also call the \ref Bfs::run() "run()" function with two
|
kpeter@58
|
76 |
parameters. In this case, the BFS search will terminate once it has found
|
kpeter@58
|
77 |
the shortest path from \c s to \c t.
|
kpeter@58
|
78 |
|
kpeter@49
|
79 |
\code
|
kpeter@58
|
80 |
bfs.run(s,t);
|
kpeter@49
|
81 |
\endcode
|
kpeter@49
|
82 |
|
kpeter@58
|
83 |
By default, the distances and the path information are stored in internal
|
kpeter@58
|
84 |
maps, which you can access with member functions like \ref lemon::Bfs::distMap
|
kpeter@58
|
85 |
"distMap()" and \ref lemon::Bfs::predMap() "predMap()" or more directly with
|
kpeter@58
|
86 |
other member functions like \ref lemon::Bfs::dist() "dist()",
|
kpeter@58
|
87 |
\ref lemon::Bfs::path() "path()", \ref lemon::Bfs::predNode() "predNode()",
|
kpeter@58
|
88 |
\ref lemon::Bfs::predArc() "predArc()". Once the execution of the algorithm
|
kpeter@58
|
89 |
is finished, these query functions can be called.
|
kpeter@58
|
90 |
|
kpeter@58
|
91 |
For an example, let us say we want to print the shortest path of those nodes
|
kpeter@58
|
92 |
that are at most in a certain distance \c max_dist.
|
kpeter@49
|
93 |
\code
|
kpeter@49
|
94 |
bfs.run(s);
|
kpeter@49
|
95 |
|
kpeter@58
|
96 |
for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
|
kpeter@58
|
97 |
if (bfs.reached(n) && bfs.dist(n) <= max_dist) {
|
kpeter@49
|
98 |
std::cout << gr.id(n);
|
kpeter@58
|
99 |
Node prev = bfs.prevNode(n);
|
kpeter@58
|
100 |
while (prev != INVALID) {
|
kpeter@49
|
101 |
std::cout << "<-" << gr.id(prev);
|
kpeter@49
|
102 |
prev = bfs.prevNode(n);
|
kpeter@58
|
103 |
}
|
kpeter@49
|
104 |
std::cout << std::endl;
|
kpeter@49
|
105 |
}
|
kpeter@49
|
106 |
}
|
kpeter@49
|
107 |
\endcode
|
kpeter@49
|
108 |
|
kpeter@58
|
109 |
The class interfaces of the algorithms also support a finer control on
|
kpeter@58
|
110 |
the execution. For example, we can specify more source nodes and we can
|
kpeter@58
|
111 |
even run the algorithm step-by-step.
|
kpeter@58
|
112 |
If you need such control on the execution, you have to use more functions
|
kpeter@58
|
113 |
instead of \ref Bfs::run() "run()". First, you have to call \ref Bfs::init()
|
kpeter@58
|
114 |
"init()" to initialize the internal data structures.
|
kpeter@49
|
115 |
|
kpeter@49
|
116 |
\code
|
kpeter@49
|
117 |
bfs.init();
|
kpeter@49
|
118 |
\endcode
|
kpeter@49
|
119 |
|
kpeter@58
|
120 |
Then you can add one or more source nodes to the queue with
|
kpeter@58
|
121 |
\ref Bfs::addSource() "addSource()". They will be processed, as they would
|
kpeter@58
|
122 |
be reached by the algorithm before. And yes, you can even add more sources
|
kpeter@58
|
123 |
during the execution.
|
kpeter@58
|
124 |
|
kpeter@49
|
125 |
\code
|
kpeter@58
|
126 |
bfs.addSource(s1);
|
kpeter@58
|
127 |
bfs.addSource(s2);
|
kpeter@49
|
128 |
...
|
kpeter@49
|
129 |
\endcode
|
kpeter@49
|
130 |
|
kpeter@58
|
131 |
Finally, the actual path computation of the algorithm can be performed with
|
kpeter@58
|
132 |
the \ref Bfs::start() "start()" function.
|
kpeter@49
|
133 |
|
kpeter@58
|
134 |
\code
|
kpeter@58
|
135 |
bfs.start(t);
|
kpeter@58
|
136 |
\endcode
|
kpeter@49
|
137 |
|
kpeter@58
|
138 |
Instead of using \ref Bfs::start() "start()", you can even execute the
|
kpeter@58
|
139 |
algorithm step-by-step, so you can write your own loop to process the
|
kpeter@58
|
140 |
nodes one-by-one.
|
kpeter@58
|
141 |
For example, the following code will executes the algorithm in such a way,
|
kpeter@58
|
142 |
that it reaches all nodes in the digraph, namely the algorithm is started
|
kpeter@58
|
143 |
for each node that is not visited before.
|
kpeter@49
|
144 |
|
kpeter@58
|
145 |
\code
|
kpeter@58
|
146 |
bfs.init();
|
kpeter@58
|
147 |
for (NodeIt n(g); n != INVALID; ++n) {
|
kpeter@58
|
148 |
if (!bfs.reached(n)) {
|
kpeter@58
|
149 |
bfs.addSource(n);
|
kpeter@58
|
150 |
bfs.start();
|
kpeter@58
|
151 |
}
|
kpeter@58
|
152 |
}
|
kpeter@58
|
153 |
\endcode
|
kpeter@49
|
154 |
|
kpeter@58
|
155 |
<tt>bfs.start()</tt> is only a shortcut of the following code.
|
kpeter@49
|
156 |
|
kpeter@58
|
157 |
\code
|
kpeter@58
|
158 |
while (!bfs.emptyQueue()) {
|
kpeter@58
|
159 |
bfs.processNextNode();
|
kpeter@58
|
160 |
}
|
kpeter@58
|
161 |
\endcode
|
kpeter@49
|
162 |
|
kpeter@58
|
163 |
\todo Write about function-type interfaces
|
kpeter@49
|
164 |
|
kpeter@49
|
165 |
|
kpeter@58
|
166 |
Since the DFS algorithm is very similar to BFS with a few tiny differences,
|
kpeter@58
|
167 |
the \ref Dfs class can be used similarly to \ref Bfs.
|
kpeter@49
|
168 |
|
kpeter@49
|
169 |
|
kpeter@46
|
170 |
[SEC]sec_shortest_paths[SEC] Shortest Paths
|
kpeter@46
|
171 |
|
kpeter@58
|
172 |
If you would like to solve some transportation problems in a network, then
|
kpeter@58
|
173 |
you will most likely want to find shortest paths between nodes of a graph.
|
kpeter@58
|
174 |
This is usually solved using Dijkstra's algorithm.
|
kpeter@58
|
175 |
The following code is a simple program using the LEMON \ref Dijkstra class
|
kpeter@58
|
176 |
through the function-type interface \ref dijkstra().
|
kpeter@58
|
177 |
It calculates the shortest path between node \c s and \c t in a digraph \c g.
|
kpeter@46
|
178 |
|
kpeter@58
|
179 |
\code
|
kpeter@58
|
180 |
dijkstra(g, length).distMap(dist).run(s,t);
|
kpeter@58
|
181 |
\endcode
|
kpeter@49
|
182 |
|
kpeter@49
|
183 |
In LEMON, the algorithms are implemented basically as classes, but
|
kpeter@49
|
184 |
for some of them, function-type interfaces are also available
|
kpeter@49
|
185 |
for the sake of convenience.
|
kpeter@49
|
186 |
For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra
|
kpeter@49
|
187 |
template class, but the \ref dijkstra() function is also defined,
|
kpeter@49
|
188 |
which can still be used quite flexibly due to named parameters.
|
kpeter@49
|
189 |
|
kpeter@58
|
190 |
The above sample code could also use the class interface as follows.
|
kpeter@49
|
191 |
|
kpeter@49
|
192 |
\code
|
kpeter@50
|
193 |
Dijkstra<ListDigraph> dijkstra(g, length);
|
kpeter@49
|
194 |
dijkstra.distMap(dist);
|
kpeter@49
|
195 |
dijsktra.init();
|
kpeter@58
|
196 |
dijkstra.addSource(s);
|
kpeter@49
|
197 |
dijkstra.start();
|
kpeter@49
|
198 |
\endcode
|
kpeter@49
|
199 |
|
kpeter@49
|
200 |
The previous code is obviously longer than the original, but the
|
kpeter@49
|
201 |
execution can be controlled to a higher extent. While using the function-type
|
kpeter@49
|
202 |
interface, only one source can be added to the algorithm, the class
|
kpeter@49
|
203 |
interface makes it possible to specify several root nodes.
|
kpeter@49
|
204 |
Moreover, the algorithm can also be executed step-by-step. For instance,
|
kpeter@49
|
205 |
the following code can be used instead of \ref dijkstra.start().
|
kpeter@49
|
206 |
|
kpeter@49
|
207 |
\code
|
kpeter@49
|
208 |
while (!dijkstra.emptyQueue()) {
|
kpeter@49
|
209 |
ListDigraph::Node n = dijkstra.processNextNode();
|
kpeter@49
|
210 |
cout << g.id(n) << ' ' << dijkstra.dist(g) << endl;
|
kpeter@49
|
211 |
}
|
kpeter@49
|
212 |
\endcode
|
kpeter@49
|
213 |
|
kpeter@58
|
214 |
LEMON provides several other algorithms for findign shortest paths in
|
kpeter@58
|
215 |
specific or more general cases. For example, \ref BellmanFord can be used
|
kpeter@58
|
216 |
instead of \ref Dijkstra when the graph contains an arc with negative cost.
|
kpeter@58
|
217 |
You may check the \ref shortest_path module of the reference manual for
|
kpeter@58
|
218 |
more details.
|
kpeter@58
|
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@58
|
225 |
\todo Write this subsection.
|
kpeter@58
|
226 |
|
kpeter@46
|
227 |
[TRAILER]
|
kpeter@46
|
228 |
*/
|
kpeter@46
|
229 |
}
|