1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
2 | * |
---|
3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
4 | * |
---|
5 | * Copyright (C) 2003-2010 |
---|
6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
8 | * |
---|
9 | * Permission to use, modify and distribute this software is granted |
---|
10 | * provided that this copyright notice appears in all copies. For |
---|
11 | * precise terms see the accompanying LICENSE file. |
---|
12 | * |
---|
13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
14 | * express or implied, and with no claim as to its suitability for any |
---|
15 | * purpose. |
---|
16 | * |
---|
17 | */ |
---|
18 | |
---|
19 | namespace lemon { |
---|
20 | /** |
---|
21 | [PAGE]sec_algorithms[PAGE] Algorithms |
---|
22 | |
---|
23 | \todo This page is under construction. |
---|
24 | \todo This section should be revised and extended. |
---|
25 | |
---|
26 | In addition to the graph structures, the most important parts of LEMON are |
---|
27 | the various algorithms related to graph theory and combinatorial optimization. |
---|
28 | The library provides quite flexible and efficient implementations |
---|
29 | for 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" |
---|
32 | and methods for discovering \ref graph_properties "graph properties" like |
---|
33 | connectivity, bipartiteness or Euler property, as well as more complex |
---|
34 | optimization 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. |
---|
37 | |
---|
38 | In this section, we present only some of the most fundamental algorithms. |
---|
39 | For a complete overview, see the \ref algs module of the reference manual. |
---|
40 | |
---|
41 | [SEC]sec_graph_search[SEC] Graph Search |
---|
42 | |
---|
43 | The common graph search algorithms, namely \ref Bfs "breadth-first search (BFS)" |
---|
44 | and \ref Dfs "depth-first search (DFS)" are implemented in highly adaptable and |
---|
45 | efficient algorithm classes \ref Bfs and \ref Dfs. In LEMON, |
---|
46 | the algorithms are typically placed in separated files, which are named after |
---|
47 | the algorithm itself but with lower case like all other header files. |
---|
48 | For example, we have to include <tt>bfs.h</tt> for using \ref Bfs. |
---|
49 | |
---|
50 | \code |
---|
51 | #include <lemon/bfs.h> |
---|
52 | \endcode |
---|
53 | |
---|
54 | Basically, all algorithms are implemented in template classes. |
---|
55 | The template parameters typically specify the used graph type (for more |
---|
56 | information, see \ref sec_graph_structures) and the required map types. |
---|
57 | For 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 | |
---|
64 | This class provides a simple but powerful interface to control the execution |
---|
65 | of the algorithm and to obtain all the results. |
---|
66 | You can execute the algorithm from a given source node by calling |
---|
67 | the \ref Bfs::run() "run()" function. |
---|
68 | |
---|
69 | \code |
---|
70 | bfs.run(s); |
---|
71 | \endcode |
---|
72 | |
---|
73 | This operation finds the shortest paths from \c s to all other nodes. |
---|
74 | If you are looking for an s-t path for a certain target node \c t, |
---|
75 | you can also call the \ref Bfs::run() "run()" function with two |
---|
76 | parameters. In this case, the BFS search will terminate once it has found |
---|
77 | the shortest path from \c s to \c t. |
---|
78 | |
---|
79 | \code |
---|
80 | bfs.run(s,t); |
---|
81 | \endcode |
---|
82 | |
---|
83 | By default, the distances and the path information are stored in internal |
---|
84 | maps, which you can access with member functions like \ref lemon::Bfs::distMap |
---|
85 | "distMap()" and \ref lemon::Bfs::predMap() "predMap()" or more directly with |
---|
86 | other 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 |
---|
89 | is finished, these query functions can be called. |
---|
90 | |
---|
91 | For an example, let us say we want to print the shortest path of those nodes |
---|
92 | that are at most in a certain distance \c max_dist. |
---|
93 | \code |
---|
94 | bfs.run(s); |
---|
95 | |
---|
96 | for (ListGraph::NodeIt n(g); n != INVALID; ++n) { |
---|
97 | if (bfs.reached(n) && bfs.dist(n) <= max_dist) { |
---|
98 | std::cout << gr.id(n); |
---|
99 | Node prev = bfs.prevNode(n); |
---|
100 | while (prev != INVALID) { |
---|
101 | std::cout << "<-" << gr.id(prev); |
---|
102 | prev = bfs.prevNode(n); |
---|
103 | } |
---|
104 | std::cout << std::endl; |
---|
105 | } |
---|
106 | } |
---|
107 | \endcode |
---|
108 | |
---|
109 | The class interfaces of the algorithms also support a finer control on |
---|
110 | the execution. For example, we can specify more source nodes and we can |
---|
111 | even run the algorithm step-by-step. |
---|
112 | If you need such control on the execution, you have to use more functions |
---|
113 | instead 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 | |
---|
120 | Then you can add one or more source nodes to the queue with |
---|
121 | \ref Bfs::addSource() "addSource()". They will be processed, as they would |
---|
122 | be reached by the algorithm before. And yes, you can even add more sources |
---|
123 | during the execution. |
---|
124 | |
---|
125 | \code |
---|
126 | bfs.addSource(s1); |
---|
127 | bfs.addSource(s2); |
---|
128 | ... |
---|
129 | \endcode |
---|
130 | |
---|
131 | Finally, the actual path computation of the algorithm can be performed with |
---|
132 | the \ref Bfs::start() "start()" function. |
---|
133 | |
---|
134 | \code |
---|
135 | bfs.start(t); |
---|
136 | \endcode |
---|
137 | |
---|
138 | Instead of using \ref Bfs::start() "start()", you can even execute the |
---|
139 | algorithm step-by-step, so you can write your own loop to process the |
---|
140 | nodes one-by-one. |
---|
141 | For example, the following code will executes the algorithm in such a way, |
---|
142 | that it reaches all nodes in the digraph, namely the algorithm is started |
---|
143 | for 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(); |
---|
151 | } |
---|
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 | |
---|
166 | Since the DFS algorithm is very similar to BFS with a few tiny differences, |
---|
167 | the \ref Dfs class can be used similarly to \ref Bfs. |
---|
168 | |
---|
169 | |
---|
170 | [SEC]sec_shortest_paths[SEC] Shortest Paths |
---|
171 | |
---|
172 | If you would like to solve some transportation problems in a network, then |
---|
173 | you will most likely want to find shortest paths between nodes of a graph. |
---|
174 | This is usually solved using Dijkstra's algorithm. |
---|
175 | The following code is a simple program using the LEMON \ref Dijkstra class |
---|
176 | through the function-type interface \ref dijkstra(). |
---|
177 | It 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 |
---|
182 | |
---|
183 | In LEMON, the algorithms are implemented basically as classes, but |
---|
184 | for some of them, function-type interfaces are also available |
---|
185 | for the sake of convenience. |
---|
186 | For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra |
---|
187 | template class, but the \ref dijkstra() function is also defined, |
---|
188 | which can still be used quite flexibly due to named parameters. |
---|
189 | |
---|
190 | The above sample code could also use the class interface as follows. |
---|
191 | |
---|
192 | \code |
---|
193 | Dijkstra<ListDigraph> dijkstra(g, length); |
---|
194 | dijkstra.distMap(dist); |
---|
195 | dijsktra.init(); |
---|
196 | dijkstra.addSource(s); |
---|
197 | dijkstra.start(); |
---|
198 | \endcode |
---|
199 | |
---|
200 | The previous code is obviously longer than the original, but the |
---|
201 | execution can be controlled to a higher extent. While using the function-type |
---|
202 | interface, only one source can be added to the algorithm, the class |
---|
203 | interface makes it possible to specify several root nodes. |
---|
204 | Moreover, the algorithm can also be executed step-by-step. For instance, |
---|
205 | the following code can be used instead of \ref dijkstra.start(). |
---|
206 | |
---|
207 | \code |
---|
208 | while (!dijkstra.emptyQueue()) { |
---|
209 | ListDigraph::Node n = dijkstra.processNextNode(); |
---|
210 | cout << g.id(n) << ' ' << dijkstra.dist(g) << endl; |
---|
211 | } |
---|
212 | \endcode |
---|
213 | |
---|
214 | LEMON provides several other algorithms for findign shortest paths in |
---|
215 | specific or more general cases. For example, \ref BellmanFord can be used |
---|
216 | instead of \ref Dijkstra when the graph contains an arc with negative cost. |
---|
217 | You may check the \ref shortest_path module of the reference manual for |
---|
218 | more details. |
---|
219 | |
---|
220 | |
---|
221 | [SEC]sec_max_flow[SEC] Maximum Flows |
---|
222 | |
---|
223 | See \ref Preflow. |
---|
224 | |
---|
225 | \todo Write this subsection. |
---|
226 | |
---|
227 | [TRAILER] |
---|
228 | */ |
---|
229 | } |
---|