[46] | 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. |
---|
[58] | 24 | \todo This section should be revised and extended. |
---|
[57] | 25 | |
---|
[46] | 26 | In addition to the graph structures, the most important parts of LEMON are |
---|
[49] | 27 | the various algorithms related to graph theory and combinatorial optimization. |
---|
[57] | 28 | The library provides quite flexible and efficient implementations |
---|
[58] | 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. |
---|
[46] | 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 | |
---|
[58] | 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. |
---|
[46] | 49 | |
---|
[58] | 50 | \code |
---|
| 51 | #include <lemon/bfs.h> |
---|
| 52 | \endcode |
---|
[49] | 53 | |
---|
[58] | 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. |
---|
[49] | 58 | |
---|
| 59 | \code |
---|
[58] | 60 | ListDigraph g; |
---|
| 61 | Bfs<ListDigraph> bfs(g); |
---|
[49] | 62 | \endcode |
---|
| 63 | |
---|
[58] | 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 | |
---|
[49] | 69 | \code |
---|
[58] | 70 | bfs.run(s); |
---|
[49] | 71 | \endcode |
---|
[58] | 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 | |
---|
[49] | 79 | \code |
---|
[58] | 80 | bfs.run(s,t); |
---|
[49] | 81 | \endcode |
---|
| 82 | |
---|
[58] | 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. |
---|
[49] | 93 | \code |
---|
| 94 | bfs.run(s); |
---|
| 95 | |
---|
[58] | 96 | for (ListGraph::NodeIt n(g); n != INVALID; ++n) { |
---|
| 97 | if (bfs.reached(n) && bfs.dist(n) <= max_dist) { |
---|
[49] | 98 | std::cout << gr.id(n); |
---|
[58] | 99 | Node prev = bfs.prevNode(n); |
---|
| 100 | while (prev != INVALID) { |
---|
[49] | 101 | std::cout << "<-" << gr.id(prev); |
---|
| 102 | prev = bfs.prevNode(n); |
---|
[58] | 103 | } |
---|
[49] | 104 | std::cout << std::endl; |
---|
| 105 | } |
---|
| 106 | } |
---|
| 107 | \endcode |
---|
| 108 | |
---|
[58] | 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. |
---|
[49] | 115 | |
---|
| 116 | \code |
---|
| 117 | bfs.init(); |
---|
| 118 | \endcode |
---|
| 119 | |
---|
[58] | 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 | |
---|
[49] | 125 | \code |
---|
[58] | 126 | bfs.addSource(s1); |
---|
| 127 | bfs.addSource(s2); |
---|
[49] | 128 | ... |
---|
| 129 | \endcode |
---|
| 130 | |
---|
[58] | 131 | Finally, the actual path computation of the algorithm can be performed with |
---|
| 132 | the \ref Bfs::start() "start()" function. |
---|
[49] | 133 | |
---|
[58] | 134 | \code |
---|
| 135 | bfs.start(t); |
---|
| 136 | \endcode |
---|
[49] | 137 | |
---|
[58] | 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. |
---|
[49] | 144 | |
---|
[58] | 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 |
---|
[49] | 154 | |
---|
[58] | 155 | <tt>bfs.start()</tt> is only a shortcut of the following code. |
---|
[49] | 156 | |
---|
[58] | 157 | \code |
---|
| 158 | while (!bfs.emptyQueue()) { |
---|
| 159 | bfs.processNextNode(); |
---|
| 160 | } |
---|
| 161 | \endcode |
---|
[49] | 162 | |
---|
[58] | 163 | \todo Write about function-type interfaces |
---|
[49] | 164 | |
---|
| 165 | |
---|
[58] | 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. |
---|
[49] | 168 | |
---|
| 169 | |
---|
[46] | 170 | [SEC]sec_shortest_paths[SEC] Shortest Paths |
---|
| 171 | |
---|
[58] | 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. |
---|
[46] | 178 | |
---|
[58] | 179 | \code |
---|
| 180 | dijkstra(g, length).distMap(dist).run(s,t); |
---|
| 181 | \endcode |
---|
[49] | 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 | |
---|
[58] | 190 | The above sample code could also use the class interface as follows. |
---|
[49] | 191 | |
---|
| 192 | \code |
---|
[50] | 193 | Dijkstra<ListDigraph> dijkstra(g, length); |
---|
[49] | 194 | dijkstra.distMap(dist); |
---|
| 195 | dijsktra.init(); |
---|
[58] | 196 | dijkstra.addSource(s); |
---|
[49] | 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 | |
---|
[58] | 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 | |
---|
[49] | 220 | |
---|
[46] | 221 | [SEC]sec_max_flow[SEC] Maximum Flows |
---|
| 222 | |
---|
| 223 | See \ref Preflow. |
---|
| 224 | |
---|
[58] | 225 | \todo Write this subsection. |
---|
| 226 | |
---|
[46] | 227 | [TRAILER] |
---|
| 228 | */ |
---|
| 229 | } |
---|