COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/algorithms.dox @ 2470:46818ce27a60

Last change on this file since 2470:46818ce27a60 was 2470:46818ce27a60, checked in by Peter Kovacs, 12 years ago

Small bug fixes.

File size: 5.7 KB
RevLine 
[2391]1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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
[2216]19namespace lemon {
[2196]20/**
21\page algorithms Algorithms
22
[2216]23\section algo_bfs_dfs Bfs/Dfs
24Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
25implementations of the well known algorithms. The algorithms are placed most cases in
26separated files named after the algorithm itself but lower case as all other header file names.
27For example the next Bfs class is in the \c lemon/bfs.h.
28
29\subsection Bfs
30The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
[2408]31The class has two template parameters: \b GR and \b TR.<br>
[2216]32GR is the graph the algorithm runs on. It has \ref lemon::ListGraph "ListGraph" as default type.
33TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
34wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
35
36To use the class, declare it!
37\code
38Bfs<ListUGraph>  bfs(gr);
39\endcode
40Note the lack of second template argument because of the default parameter.
41
42It provides a simple but powerful interface to control the execution.
43\code
44int dist = bfs.run(s,t);
45\endcode
46It finds the shortest path from node \c s to node \c t and returns it, or zero
47if there is no path from \c s to \c t.<br>
48If you want the shortest path from a specified node to all other node, just write:
49\code
50bfs.run(s);
51\endcode
52Now the distances and path information are stored in maps which you can access with
53member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
[2408]54Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm
[2216]55is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
56"predNode()" can be called.
57
58For an example let's say we want to print the shortest path of those nodes which
59are in a certain distance.
60\code
61bfs.run(s);
62
63for( ListUGraph::NodeIt  n(gr); n != INVALID; ++n ) {
64  if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
65    std::cout << gr.id(n);
66
67    Node  prev = bfs.prevNode(n);
68    while( prev != INVALID ) {
69      std::cout << "<-" << gr.id(prev);
70      prev = bfs.prevNode(n);
71    }
72   
73    std::cout << std::endl;
74  }
75}
76\endcode
77
78\subsubsection bfs_adv_control Advanced control
79In the previous code we only used \c run(). Now we introduce the way you can directly
80control the execution of the algorithm.
81
82First you have to initialize the variables with \ref lemon::Bfs::init "init()".
83\code
84  bfs.init();
85\endcode
86
87Then you add one or more source nodes to the queue. They will be processed, as they would
88be reached by the algorithm before. And yes - you can add more sources during the execution.
89\code
90  bfs.addSource(node_1);
91  bfs.addSource(node_2);
92  ...
93\endcode
94
95And finally you can start the process with \ref lemon::Bfs::start "start()", or
96you can write your own loop to process the nodes one-by-one.
97
[2470]98\todo Demo for Bfs advanced control.
[2216]99
100\subsection Dfs
101Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
102to demonstrate Dfs's capabilities.
103
104We will see a program, which solves the problem of <b>topological ordering</b>.
105We need to know in which order we should put on our clothes. The program will do the following:
106<ol>
107<li>We run the dfs algorithm to all nodes.
108<li>Put every node into a list when processed completely.
109<li>Write out the list in reverse order.
110</ol>
111
112\dontinclude topological_ordering.cc
113First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
114will be done through it.
[2281]115\skip MyOrdererMap
[2216]116\until };
117The class meets the \ref lemon::WriteMap "WriteMap" concept. In it's \c set() method the only thing
[2408]118we need to do is insert the key - that is the node whose processing just finished - into the beginning
[2281]119of the list.<br>
120Although we implemented this needed helper class ourselves it was not necessary.
121The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
122what we needed. To be correct it's more general - and it's all in \c LEMON. But
123we wanted to show you, how easy is to add additional functionality.
[2216]124
125First we declare the needed data structures: the graph and a map to store the nodes' label.
126\skip ListGraph
127\until label
128
129Now we build a graph. But keep in mind that it must be DAG because cyclic graphs has no topological
130ordering.
131\skip belt
132\until trousers
133We label them...
134\skip label
135\until trousers
136Then add directed edges which represent the precedences between those items.
137\skip trousers, belt
138\until );
139
140See how easy is to access the internal information of this algorithm trough maps.
141We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
142\skip Dfs
143\until run
144
145And now comes the third part. Write out the list in reverse order. But the list was
146composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
147\skip std
148\until endl
149
150The program is to be found in the \ref demo directory: \ref topological_ordering.cc
[2281]151
[2470]152\todo Check the linking of the demo file, the code samples are missing.
153
[2281]154More algorithms are described in the \ref algorithms2 "second part".
[2196]155*/
[2216]156}
Note: See TracBrowser for help on using the repository browser.