/* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  * Copyright (C) 2003-2010

  * 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]sec_algorithms[PAGE] Algorithms

 \todo This page is under construction.

 \todo This section should be revised and extended.

 In addition to the graph structures, the most important parts of LEMON are

 the various algorithms related to graph theory and combinatorial optimization.

 The library provides quite flexible and efficient implementations

 for well-known fundamental algorithms, such as \ref Bfs

 "breadth-first search (BFS)", \ref Dfs "depth-first search (DFS)",

 \ref Dijkstra "Dijkstra algorithm", \ref kruskal "Kruskal algorithm"

 and methods for discovering \ref graph_properties "graph properties" like

 connectivity, bipartiteness or Euler property, as well as more complex

 optimization algorithms for finding \ref max_flow "maximum flows",

 \ref min_cut "minimum cuts", \ref matching "matchings",

 \ref min_cost_flow_algs "minimum cost flows" etc.

 In this section, we present only some of the most fundamental algorithms.

 For a complete overview, see the \ref algs module of the reference manual.

 [SEC]sec_graph_search[SEC] Graph Search

 The common graph search algorithms, namely \ref Bfs "breadth-first search (BFS)"

 and \ref Dfs "depth-first search (DFS)" are implemented in highly adaptable and

 efficient algorithm classes \ref Bfs and \ref Dfs. In LEMON, 

 the algorithms are typically placed in separated files, which are named after

 the algorithm itself but with lower case like all other header files.

 For example, we have to include <tt>bfs.h</tt> for using \ref Bfs.

 \code

    #include <lemon/bfs.h>

 \endcode

 Basically, all algorithms are implemented in template classes.

 The template parameters typically specify the used graph type (for more

 information, see \ref sec_graph_structures) and the required map types.

 For example, an instance of the \ref BFs class can be created like this.

 \code

   ListDigraph g;

   Bfs<ListDigraph> bfs(g);

 \endcode

 This class provides a simple but powerful interface to control the execution

 of the algorithm and to obtain all the results.

 You can execute the algorithm from a given source node by calling

 the \ref Bfs::run() "run()" function.

 \code

   bfs.run(s);

 \endcode

 This operation finds the shortest paths from \c s to all other nodes.

 If you are looking for an s-t path for a certain target node \c t,

 you can also call the \ref Bfs::run() "run()" function with two

 parameters. In this case, the BFS search will terminate once it has found

 the shortest path from \c s to \c t. 

 \code

   bfs.run(s,t);

 \endcode

 By default, the distances and the path information are stored in internal

 maps, which you can access with member functions like \ref lemon::Bfs::distMap

 "distMap()" and \ref lemon::Bfs::predMap() "predMap()" or more directly with

 other member functions like \ref lemon::Bfs::dist() "dist()",

 \ref lemon::Bfs::path() "path()", \ref lemon::Bfs::predNode() "predNode()",

 \ref lemon::Bfs::predArc() "predArc()". Once the execution of the algorithm

 is finished, these query functions can be called.

 For an example, let us say we want to print the shortest path of those nodes

 that are at most in a certain distance \c max_dist.

 \code

 bfs.run(s);

 for (ListGraph::NodeIt n(g); 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

 The class interfaces of the algorithms also support a finer control on

 the execution. For example, we can specify more source nodes and we can

 even run the algorithm step-by-step.

 If you need such control on the execution, you have to use more functions

 instead of \ref Bfs::run() "run()". First, you have to call \ref Bfs::init()

 "init()" to initialize the internal data structures.

 \code

   bfs.init();

 \endcode

 Then you can add one or more source nodes to the queue with

 \ref Bfs::addSource() "addSource()". They will be processed, as they would

 be reached by the algorithm before. And yes, you can even add more sources

 during the execution.

 \code

   bfs.addSource(s1);

   bfs.addSource(s2);

   ...

 \endcode

 Finally, the actual path computation of the algorithm can be performed with

 the \ref Bfs::start() "start()" function.

 \code

   bfs.start(t);

 \endcode

 Instead of using \ref Bfs::start() "start()", you can even execute the

 algorithm step-by-step, so you can write your own loop to process the

 nodes one-by-one.

 For example, the following code will executes the algorithm in such a way,

 that it reaches all nodes in the digraph, namely the algorithm is started

 for each node that is not visited before.

 \code

   bfs.init();

   for (NodeIt n(g); n != INVALID; ++n) {

     if (!bfs.reached(n)) {

       bfs.addSource(n);

       bfs.start();

     }

   }

 \endcode

 <tt>bfs.start()</tt> is only a shortcut of the following code.

 \code

   while (!bfs.emptyQueue()) {

     bfs.processNextNode();

   }

 \endcode

 \todo Write about function-type interfaces

 Since the DFS algorithm is very similar to BFS with a few tiny differences,

 the \ref Dfs class can be used similarly to \ref Bfs.

 [SEC]sec_shortest_paths[SEC] Shortest Paths

 If you would like to solve some transportation problems in a network, then

 you will most likely want to find shortest paths between nodes of a graph.

 This is usually solved using Dijkstra's algorithm. 

 The following code is a simple program using the LEMON \ref Dijkstra class

 through the function-type interface \ref dijkstra().

 It calculates the shortest path between node \c s and \c t in a digraph \c g.

 \code

   dijkstra(g, length).distMap(dist).run(s,t);

 \endcode

 In LEMON, the algorithms are implemented basically as classes, but

 for some of them, function-type interfaces are also available

 for the sake of convenience.

 For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra

 template class, but the \ref dijkstra() function is also defined,

 which can still be used quite flexibly due to named parameters.

 The above sample code could also use the class interface as follows.

 \code

   Dijkstra<ListDigraph> dijkstra(g, length);

   dijkstra.distMap(dist);

   dijsktra.init();

   dijkstra.addSource(s);

   dijkstra.start();

 \endcode

 The previous code is obviously longer than the original, but the

 execution can be controlled to a higher extent. While using the function-type

 interface, only one source can be added to the algorithm, the class

 interface makes it possible to specify several root nodes.

 Moreover, the algorithm can also be executed step-by-step. For instance,

 the following code can be used instead of \ref dijkstra.start().

 \code

   while (!dijkstra.emptyQueue()) {

     ListDigraph::Node n = dijkstra.processNextNode();

     cout << g.id(n) << ' ' << dijkstra.dist(g) << endl;

   }

 \endcode

 LEMON provides several other algorithms for findign shortest paths in

 specific or more general cases. For example, \ref BellmanFord can be used

 instead of \ref Dijkstra when the graph contains an arc with negative cost.

 You may check the \ref shortest_path module of the reference manual for

 more details.

 [SEC]sec_max_flow[SEC] Maximum Flows

 See \ref Preflow.

 \todo Write this subsection.

 [TRAILER]

 */

 }