doc/algorithms.dox
author alpar
Tue, 31 Oct 2006 08:39:01 +0000
changeset 2279 2c3fee01d3ed
parent 2196 09af6d2b683b
child 2281 55b15666560f
permissions -rw-r--r--
Update scripts
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
}