alpar@2391: /* -*- C++ -*-
alpar@2391:  *
alpar@2391:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2391:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@2391:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391:  *
alpar@2391:  * Permission to use, modify and distribute this software is granted
alpar@2391:  * provided that this copyright notice appears in all copies. For
alpar@2391:  * precise terms see the accompanying LICENSE file.
alpar@2391:  *
alpar@2391:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2391:  * express or implied, and with no claim as to its suitability for any
alpar@2391:  * purpose.
alpar@2391:  *
alpar@2391:  */
alpar@2391: 
alpar@2216: namespace lemon {
alpar@2196: /**
alpar@2196: \page algorithms Algorithms
alpar@2196: 
alpar@2216: \section algo_bfs_dfs Bfs/Dfs
alpar@2216: Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
alpar@2216: implementations of the well known algorithms. The algorithms are placed most cases in
alpar@2216: separated files named after the algorithm itself but lower case as all other header file names.
alpar@2216: For example the next Bfs class is in the \c lemon/bfs.h.
alpar@2216: 
alpar@2216: \subsection Bfs
alpar@2216: The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
alpar@2408: The class has two template parameters: \b GR and \b TR.<br>
alpar@2216: GR is the graph the algorithm runs on. It has \ref lemon::ListGraph "ListGraph" as default type.
alpar@2216: TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
alpar@2216: wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
alpar@2216: 
alpar@2216: To use the class, declare it!
alpar@2216: \code
alpar@2216: Bfs<ListUGraph>  bfs(gr);
alpar@2216: \endcode
alpar@2216: Note the lack of second template argument because of the default parameter.
alpar@2216: 
alpar@2216: It provides a simple but powerful interface to control the execution.
alpar@2216: \code
alpar@2216: int dist = bfs.run(s,t);
alpar@2216: \endcode
alpar@2216: It finds the shortest path from node \c s to node \c t and returns it, or zero
alpar@2216: if there is no path from \c s to \c t.<br>
alpar@2216: If you want the shortest path from a specified node to all other node, just write:
alpar@2216: \code
alpar@2216: bfs.run(s);
alpar@2216: \endcode
alpar@2216: Now the distances and path information are stored in maps which you can access with
alpar@2216: member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
alpar@2408: Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm
alpar@2216: is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
alpar@2216: "predNode()" can be called.
alpar@2216: 
alpar@2216: For an example let's say we want to print the shortest path of those nodes which
alpar@2216: are in a certain distance.
alpar@2216: \code
alpar@2216: bfs.run(s);
alpar@2216: 
alpar@2216: for( ListUGraph::NodeIt  n(gr); n != INVALID; ++n ) {
alpar@2216:   if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
alpar@2216:     std::cout << gr.id(n);
alpar@2216: 
alpar@2216:     Node  prev = bfs.prevNode(n);
alpar@2216:     while( prev != INVALID ) {
alpar@2216:       std::cout << "<-" << gr.id(prev);
alpar@2216:       prev = bfs.prevNode(n);
alpar@2216:     }
alpar@2216:     
alpar@2216:     std::cout << std::endl;
alpar@2216:   }
alpar@2216: }
alpar@2216: \endcode
alpar@2216: 
alpar@2216: \subsubsection bfs_adv_control Advanced control
alpar@2216: In the previous code we only used \c run(). Now we introduce the way you can directly
alpar@2216: control the execution of the algorithm.
alpar@2216: 
alpar@2216: First you have to initialize the variables with \ref lemon::Bfs::init "init()".
alpar@2216: \code
alpar@2216:   bfs.init();
alpar@2216: \endcode
alpar@2216: 
alpar@2216: Then you add one or more source nodes to the queue. They will be processed, as they would
alpar@2216: be reached by the algorithm before. And yes - you can add more sources during the execution.
alpar@2216: \code
alpar@2216:   bfs.addSource(node_1);
alpar@2216:   bfs.addSource(node_2);
alpar@2216:   ...
alpar@2216: \endcode
alpar@2216: 
alpar@2216: And finally you can start the process with \ref lemon::Bfs::start "start()", or
alpar@2216: you can write your own loop to process the nodes one-by-one.
alpar@2216: 
kpeter@2470: \todo Demo for Bfs advanced control.
alpar@2216: 
alpar@2216: \subsection Dfs
alpar@2216: Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
alpar@2216: to demonstrate Dfs's capabilities.
alpar@2216: 
alpar@2216: We will see a program, which solves the problem of <b>topological ordering</b>.
alpar@2216: We need to know in which order we should put on our clothes. The program will do the following:
alpar@2216: <ol>
alpar@2216: <li>We run the dfs algorithm to all nodes.
alpar@2216: <li>Put every node into a list when processed completely.
alpar@2216: <li>Write out the list in reverse order.
alpar@2216: </ol>
alpar@2216: 
alpar@2216: \dontinclude topological_ordering.cc
alpar@2216: First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
alpar@2216: will be done through it.
mqrelly@2281: \skip MyOrdererMap
alpar@2216: \until };
kpeter@2476: The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
alpar@2408: we need to do is insert the key - that is the node whose processing just finished - into the beginning
mqrelly@2281: of the list.<br>
mqrelly@2281: Although we implemented this needed helper class ourselves it was not necessary.
mqrelly@2281: The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
mqrelly@2281: what we needed. To be correct it's more general - and it's all in \c LEMON. But
mqrelly@2281: we wanted to show you, how easy is to add additional functionality.
alpar@2216: 
alpar@2216: First we declare the needed data structures: the graph and a map to store the nodes' label.
alpar@2216: \skip ListGraph
alpar@2216: \until label
alpar@2216: 
alpar@2216: Now we build a graph. But keep in mind that it must be DAG because cyclic graphs has no topological
alpar@2216: ordering.
alpar@2216: \skip belt
alpar@2216: \until trousers
alpar@2216: We label them...
alpar@2216: \skip label
alpar@2216: \until trousers
alpar@2216: Then add directed edges which represent the precedences between those items.
alpar@2216: \skip trousers, belt
alpar@2216: \until );
alpar@2216: 
alpar@2216: See how easy is to access the internal information of this algorithm trough maps.
alpar@2216: We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
alpar@2216: \skip Dfs
alpar@2216: \until run
alpar@2216: 
alpar@2216: And now comes the third part. Write out the list in reverse order. But the list was
alpar@2216: composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
alpar@2216: \skip std
alpar@2216: \until endl
alpar@2216: 
alpar@2216: The program is to be found in the \ref demo directory: \ref topological_ordering.cc
mqrelly@2281: 
kpeter@2470: \todo Check the linking of the demo file, the code samples are missing.
kpeter@2470: 
mqrelly@2281: More algorithms are described in the \ref algorithms2 "second part".
alpar@2196: */
alpar@2216: }