source: lemon-0.x/doc/algorithms.dox @ 2399:ccf2a1fa1821

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

namespace lemon {
/**
\page algorithms Algorithms

\section algo_bfs_dfs Bfs/Dfs
Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
implementations of the well known algorithms. The algorithms are placed most cases in
separated files named after the algorithm itself but lower case as all other header file names.
For example the next Bfs class is in the \c lemon/bfs.h.

\subsection Bfs
The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
The class has two template parameters: \b GR and \TR.<br>
GR is the graph the algorithm runs on. It has \ref lemon::ListGraph "ListGraph" as default type.
TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".

To use the class, declare it!
\code
Bfs<ListUGraph>  bfs(gr);
\endcode
Note the lack of second template argument because of the default parameter.

It provides a simple but powerful interface to control the execution.
\code
int dist = bfs.run(s,t);
\endcode
It finds the shortest path from node \c s to node \c t and returns it, or zero
if there is no path from \c s to \c t.<br>
If you want the shortest path from a specified node to all other node, just write:
\code
bfs.run(s);
\endcode
Now the distances and path information are stored in maps which you can access with
member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
Or more directly whit other member functions like \c predNode(). Once the algorithm
is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
"predNode()" can be called.

For an example let's say we want to print the shortest path of those nodes which
are in a certain distance.
\code
bfs.run(s);

for( ListUGraph::NodeIt  n(gr); n != INVALID; ++n ) {
  if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
    std::cout << gr.id(n);

    Node  prev = bfs.prevNode(n);
    while( prev != INVALID ) {
      std::cout << "<-" << gr.id(prev);
      prev = bfs.prevNode(n);
    }
    
    std::cout << std::endl;
  }
}
\endcode

\subsubsection bfs_adv_control Advanced control
In the previous code we only used \c run(). Now we introduce the way you can directly
control the execution of the algorithm.

First you have to initialize the variables with \ref lemon::Bfs::init "init()".
\code
  bfs.init();
\endcode

Then you add one or more source nodes to the queue. They will be processed, as they would
be reached by the algorithm before. And yes - you can add more sources during the execution.
\code
  bfs.addSource(node_1);
  bfs.addSource(node_2);
  ...
\endcode

And finally you can start the process with \ref lemon::Bfs::start "start()", or
you can write your own loop to process the nodes one-by-one.

\todo demo for bfs advanced control

\subsection Dfs
Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
to demonstrate Dfs's capabilities.

We will see a program, which solves the problem of <b>topological ordering</b>.
We need to know in which order we should put on our clothes. The program will do the following:
<ol>
<li>We run the dfs algorithm to all nodes.
<li>Put every node into a list when processed completely.
<li>Write out the list in reverse order.
</ol>

\dontinclude topological_ordering.cc
First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
will be done through it.
\skip MyOrdererMap
\until };
The class meets the \ref lemon::WriteMap "WriteMap" concept. In it's \c set() method the only thing
we need to do is insert the key - that is the node who's processing just finished - into the beginning
of the list.<br>
Although we implemented this needed helper class ourselves it was not necessary.
The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
what we needed. To be correct it's more general - and it's all in \c LEMON. But
we wanted to show you, how easy is to add additional functionality.

First we declare the needed data structures: the graph and a map to store the nodes' label.
\skip ListGraph
\until label

Now we build a graph. But keep in mind that it must be DAG because cyclic graphs has no topological
ordering.
\skip belt
\until trousers
We label them...
\skip label
\until trousers
Then add directed edges which represent the precedences between those items.
\skip trousers, belt
\until );

See how easy is to access the internal information of this algorithm trough maps.
We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
\skip Dfs
\until run

And now comes the third part. Write out the list in reverse order. But the list was
composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
\skip std
\until endl

The program is to be found in the \ref demo directory: \ref topological_ordering.cc

More algorithms are described in the \ref algorithms2 "second part".
*/
}