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