COIN-OR::LEMON - Graph Library

source: lemon-tutorial/algorithms.dox

Last change on this file was 58:10b6a5b7d4c0, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Improve Algorithms section (it is still under construction)

File size: 7.7 KB
Line 
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
19namespace 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
26In addition to the graph structures, the most important parts of LEMON are
27the various algorithms related to graph theory and combinatorial optimization.
28The library provides quite flexible and efficient implementations
29for 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"
32and methods for discovering \ref graph_properties "graph properties" like
33connectivity, bipartiteness or Euler property, as well as more complex
34optimization 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
38In this section, we present only some of the most fundamental algorithms.
39For a complete overview, see the \ref algs module of the reference manual.
40
41[SEC]sec_graph_search[SEC] Graph Search
42
43The common graph search algorithms, namely \ref Bfs "breadth-first search (BFS)"
44and \ref Dfs "depth-first search (DFS)" are implemented in highly adaptable and
45efficient algorithm classes \ref Bfs and \ref Dfs. In LEMON,
46the algorithms are typically placed in separated files, which are named after
47the algorithm itself but with lower case like all other header files.
48For example, we have to include <tt>bfs.h</tt> for using \ref Bfs.
49
50\code
51   #include <lemon/bfs.h>
52\endcode
53
54Basically, all algorithms are implemented in template classes.
55The template parameters typically specify the used graph type (for more
56information, see \ref sec_graph_structures) and the required map types.
57For 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
64This class provides a simple but powerful interface to control the execution
65of the algorithm and to obtain all the results.
66You can execute the algorithm from a given source node by calling
67the \ref Bfs::run() "run()" function.
68
69\code
70  bfs.run(s);
71\endcode
72
73This operation finds the shortest paths from \c s to all other nodes.
74If you are looking for an s-t path for a certain target node \c t,
75you can also call the \ref Bfs::run() "run()" function with two
76parameters. In this case, the BFS search will terminate once it has found
77the shortest path from \c s to \c t.
78
79\code
80  bfs.run(s,t);
81\endcode
82
83By default, the distances and the path information are stored in internal
84maps, which you can access with member functions like \ref lemon::Bfs::distMap
85"distMap()" and \ref lemon::Bfs::predMap() "predMap()" or more directly with
86other 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
89is finished, these query functions can be called.
90
91For an example, let us say we want to print the shortest path of those nodes
92that are at most in a certain distance \c max_dist.
93\code
94bfs.run(s);
95
96for (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
109The class interfaces of the algorithms also support a finer control on
110the execution. For example, we can specify more source nodes and we can
111even run the algorithm step-by-step.
112If you need such control on the execution, you have to use more functions
113instead 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
120Then you can add one or more source nodes to the queue with
121\ref Bfs::addSource() "addSource()". They will be processed, as they would
122be reached by the algorithm before. And yes, you can even add more sources
123during the execution.
124
125\code
126  bfs.addSource(s1);
127  bfs.addSource(s2);
128  ...
129\endcode
130
131Finally, the actual path computation of the algorithm can be performed with
132the \ref Bfs::start() "start()" function.
133
134\code
135  bfs.start(t);
136\endcode
137
138Instead of using \ref Bfs::start() "start()", you can even execute the
139algorithm step-by-step, so you can write your own loop to process the
140nodes one-by-one.
141For example, the following code will executes the algorithm in such a way,
142that it reaches all nodes in the digraph, namely the algorithm is started
143for 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
166Since the DFS algorithm is very similar to BFS with a few tiny differences,
167the \ref Dfs class can be used similarly to \ref Bfs.
168
169
170[SEC]sec_shortest_paths[SEC] Shortest Paths
171
172If you would like to solve some transportation problems in a network, then
173you will most likely want to find shortest paths between nodes of a graph.
174This is usually solved using Dijkstra's algorithm.
175The following code is a simple program using the LEMON \ref Dijkstra class
176through the function-type interface \ref dijkstra().
177It 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 
183In LEMON, the algorithms are implemented basically as classes, but
184for some of them, function-type interfaces are also available
185for the sake of convenience.
186For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra
187template class, but the \ref dijkstra() function is also defined,
188which can still be used quite flexibly due to named parameters.
189
190The 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
200The previous code is obviously longer than the original, but the
201execution can be controlled to a higher extent. While using the function-type
202interface, only one source can be added to the algorithm, the class
203interface makes it possible to specify several root nodes.
204Moreover, the algorithm can also be executed step-by-step. For instance,
205the 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
214LEMON provides several other algorithms for findign shortest paths in
215specific or more general cases. For example, \ref BellmanFord can be used
216instead of \ref Dijkstra when the graph contains an arc with negative cost.
217You may check the \ref shortest_path module of the reference manual for
218more details.
219
220
221[SEC]sec_max_flow[SEC] Maximum Flows
222
223See \ref Preflow.
224
225\todo Write this subsection.
226
227[TRAILER]
228*/
229}
Note: See TracBrowser for help on using the repository browser.