COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/algorithms.dox @ 2216:1e45cdeea3cc

Last change on this file since 2216:1e45cdeea3cc was 2216:1e45cdeea3cc, checked in by Alpar Juttner, 18 years ago

The recent progresses on the tutorial due to Mark.

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