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