COIN-OR::LEMON - Graph Library

source: lemon-tutorial/algorithms.dox @ 57:18404ec968ca

Last change on this file since 57:18404ec968ca was 57:18404ec968ca, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Various small fixes

File size: 8.3 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
25\todo The following contents are mainly ported from the LEMON 0.x tutorial,
26thus they have to be thoroughly revised and reworked.
27
28\warning Currently, this section may contain old or faulty contents.
29
30In addition to the graph structures, the most important parts of LEMON are
31the various algorithms related to graph theory and combinatorial optimization.
32The library provides quite flexible and efficient implementations
33for well-known fundamental algorithms, such as breadth-first
34search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm
35and methods for discovering graph properties like connectivity, bipartiteness
36or Euler property, as well as more complex optimization algorithms for finding
37maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint
38paths.
39
40In this section, we present only some of the most fundamental algorithms.
41For a complete overview, see the \ref algs module of the reference manual.
42
43[SEC]sec_graph_search[SEC] Graph Search
44
45See \ref Bfs, \ref Dfs and \ref graph_properties.
46
47Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
48implementations of the well known algorithms. The algorithms are placed most cases in
49separated files named after the algorithm itself but lower case as all other header file names.
50For example the next Bfs class is in the \c lemon/bfs.h.
51
52The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
53The class has two template parameters: \b GR and \b TR.<br>
54GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type.
55TR is a Traits class commonly used to easy the parameterization of templates. In most cases you
56wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
57
58To use the class, declare it!
59\code
60Bfs<ListGraph>  bfs(gr);
61\endcode
62Note the lack of second template argument because of the default parameter.
63
64It provides a simple but powerful interface to control the execution.
65\code
66int dist = bfs.run(s,t);
67\endcode
68It finds the shortest path from node \c s to node \c t and returns it, or zero
69if there is no path from \c s to \c t.<br>
70If you want the shortest path from a specified node to all other node, just write:
71\code
72bfs.run(s);
73\endcode
74Now the distances and path information are stored in maps which you can access with
75member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
76Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm
77is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
78"predNode()" can be called.
79
80For an example let's say we want to print the shortest path of those nodes which
81are in a certain distance.
82\code
83bfs.run(s);
84
85for( ListGraph::NodeIt  n(gr); n != INVALID; ++n ) {
86  if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
87    std::cout << gr.id(n);
88
89    Node  prev = bfs.prevNode(n);
90    while( prev != INVALID ) {
91      std::cout << "<-" << gr.id(prev);
92      prev = bfs.prevNode(n);
93    }
94   
95    std::cout << std::endl;
96  }
97}
98\endcode
99
100In the previous code we only used \c run(). Now we introduce the way you can directly
101control the execution of the algorithm.
102
103First you have to initialize the variables with \ref lemon::Bfs::init "init()".
104\code
105  bfs.init();
106\endcode
107
108Then you add one or more source nodes to the queue. They will be processed, as they would
109be reached by the algorithm before. And yes - you can add more sources during the execution.
110\code
111  bfs.addSource(node_1);
112  bfs.addSource(node_2);
113  ...
114\endcode
115
116And finally you can start the process with \ref lemon::Bfs::start "start()", or
117you can write your own loop to process the nodes one-by-one.
118
119
120Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
121to demonstrate Dfs's capabilities.
122
123We will see a program, which solves the problem of <b>topological ordering</b>.
124We need to know in which order we should put on our clothes. The program will do the following:
125<ol>
126<li>We run the dfs algorithm to all nodes.
127<li>Put every node into a list when processed completely.
128<li>Write out the list in reverse order.
129</ol>
130
131\dontinclude topological_ordering.cc
132First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
133will be done through it.
134\skip MyOrdererMap
135\until };
136The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
137we need to do is insert the key - that is the node whose processing just finished - into the beginning
138of the list.<br>
139Although we implemented this needed helper class ourselves it was not necessary.
140The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
141what we needed. To be correct it's more general - and it's all in \c LEMON. But
142we wanted to show you, how easy is to add additional functionality.
143
144First we declare the needed data structures: the digraph and a map to store the nodes' label.
145\skip ListDigraph
146\until label
147
148Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
149ordering.
150\skip belt
151\until trousers
152We label them...
153\skip label
154\until trousers
155Then add arcs which represent the precedences between those items.
156\skip trousers, belt
157\until );
158
159See how easy is to access the internal information of this algorithm trough maps.
160We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
161\skip Dfs
162\until run
163
164And now comes the third part. Write out the list in reverse order. But the list was
165composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
166\skip std
167\until endl
168
169The program is to be found in the \ref demo directory: \ref topological_ordering.cc
170
171\todo Check the linking of the demo file, the code samples are missing.
172
173More algorithms are described in the \ref algorithms2 "second part".
174
175
176[SEC]sec_shortest_paths[SEC] Shortest Paths
177
178See \ref Dijkstra and \ref BellmanFord.
179
180
181If you want to solve some transportation problems in a network then you
182will want to find shortest paths between nodes of a graph. This is
183usually solved using Dijkstra's algorithm. A utility that solves this is
184the LEMON Dijkstra class. The following code is a simple program using
185the LEMON Dijkstra class: it calculates the shortest path between node s
186and t in a graph g. We omit the part reading the graph g and the length
187map len.
188
189<hr>
190 
191In LEMON, the algorithms are implemented basically as classes, but
192for some of them, function-type interfaces are also available
193for the sake of convenience.
194For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra
195template class, but the \ref dijkstra() function is also defined,
196which can still be used quite flexibly due to named parameters.
197
198The original sample code could also use the class interface as follows.
199
200\code
201  Dijkstra<ListDigraph> dijkstra(g, length);
202  dijkstra.distMap(dist);
203  dijsktra.init();
204  dijkstra.addSource(u);
205  dijkstra.start();
206\endcode
207
208The previous code is obviously longer than the original, but the
209execution can be controlled to a higher extent. While using the function-type
210interface, only one source can be added to the algorithm, the class
211interface makes it possible to specify several root nodes.
212Moreover, the algorithm can also be executed step-by-step. For instance,
213the following code can be used instead of \ref dijkstra.start().
214
215\code
216  while (!dijkstra.emptyQueue()) {
217    ListDigraph::Node n = dijkstra.processNextNode();
218    cout << g.id(n) << ' ' << dijkstra.dist(g) << endl;
219  }
220\endcode
221
222
223[SEC]sec_max_flow[SEC] Maximum Flows
224
225See \ref Preflow.
226
227[TRAILER]
228*/
229}
Note: See TracBrowser for help on using the repository browser.