kpeter@46: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@46:  *
kpeter@46:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@46:  *
kpeter@46:  * Copyright (C) 2003-2010
kpeter@46:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@46:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@46:  *
kpeter@46:  * Permission to use, modify and distribute this software is granted
kpeter@46:  * provided that this copyright notice appears in all copies. For
kpeter@46:  * precise terms see the accompanying LICENSE file.
kpeter@46:  *
kpeter@46:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@46:  * express or implied, and with no claim as to its suitability for any
kpeter@46:  * purpose.
kpeter@46:  *
kpeter@46:  */
kpeter@46: 
kpeter@46: namespace lemon {
kpeter@46: /**
kpeter@46: [PAGE]sec_algorithms[PAGE] Algorithms
kpeter@46: 
kpeter@46: \todo This page is under construction.
kpeter@58: \todo This section should be revised and extended.
kpeter@57: 
kpeter@46: In addition to the graph structures, the most important parts of LEMON are
kpeter@49: the various algorithms related to graph theory and combinatorial optimization.
kpeter@57: The library provides quite flexible and efficient implementations
kpeter@58: for well-known fundamental algorithms, such as \ref Bfs
kpeter@58: "breadth-first search (BFS)", \ref Dfs "depth-first search (DFS)",
kpeter@58: \ref Dijkstra "Dijkstra algorithm", \ref kruskal "Kruskal algorithm"
kpeter@58: and methods for discovering \ref graph_properties "graph properties" like
kpeter@58: connectivity, bipartiteness or Euler property, as well as more complex
kpeter@58: optimization algorithms for finding \ref max_flow "maximum flows",
kpeter@58: \ref min_cut "minimum cuts", \ref matching "matchings",
kpeter@58: \ref min_cost_flow_algs "minimum cost flows" etc.
kpeter@46: 
kpeter@46: In this section, we present only some of the most fundamental algorithms.
kpeter@46: For a complete overview, see the \ref algs module of the reference manual.
kpeter@46: 
kpeter@46: [SEC]sec_graph_search[SEC] Graph Search
kpeter@46: 
kpeter@58: The common graph search algorithms, namely \ref Bfs "breadth-first search (BFS)"
kpeter@58: and \ref Dfs "depth-first search (DFS)" are implemented in highly adaptable and
kpeter@58: efficient algorithm classes \ref Bfs and \ref Dfs. In LEMON, 
kpeter@58: the algorithms are typically placed in separated files, which are named after
kpeter@58: the algorithm itself but with lower case like all other header files.
kpeter@58: For example, we have to include <tt>bfs.h</tt> for using \ref Bfs.
kpeter@46: 
kpeter@58: \code
kpeter@58:    #include <lemon/bfs.h>
kpeter@58: \endcode
kpeter@49: 
kpeter@58: Basically, all algorithms are implemented in template classes.
kpeter@58: The template parameters typically specify the used graph type (for more
kpeter@58: information, see \ref sec_graph_structures) and the required map types.
kpeter@58: For example, an instance of the \ref BFs class can be created like this.
kpeter@49: 
kpeter@49: \code
kpeter@58:   ListDigraph g;
kpeter@58:   Bfs<ListDigraph> bfs(g);
kpeter@49: \endcode
kpeter@49: 
kpeter@58: This class provides a simple but powerful interface to control the execution
kpeter@58: of the algorithm and to obtain all the results.
kpeter@58: You can execute the algorithm from a given source node by calling
kpeter@58: the \ref Bfs::run() "run()" function.
kpeter@58: 
kpeter@49: \code
kpeter@58:   bfs.run(s);
kpeter@49: \endcode
kpeter@58: 
kpeter@58: This operation finds the shortest paths from \c s to all other nodes.
kpeter@58: If you are looking for an s-t path for a certain target node \c t,
kpeter@58: you can also call the \ref Bfs::run() "run()" function with two
kpeter@58: parameters. In this case, the BFS search will terminate once it has found
kpeter@58: the shortest path from \c s to \c t. 
kpeter@58: 
kpeter@49: \code
kpeter@58:   bfs.run(s,t);
kpeter@49: \endcode
kpeter@49: 
kpeter@58: By default, the distances and the path information are stored in internal
kpeter@58: maps, which you can access with member functions like \ref lemon::Bfs::distMap
kpeter@58: "distMap()" and \ref lemon::Bfs::predMap() "predMap()" or more directly with
kpeter@58: other member functions like \ref lemon::Bfs::dist() "dist()",
kpeter@58: \ref lemon::Bfs::path() "path()", \ref lemon::Bfs::predNode() "predNode()",
kpeter@58: \ref lemon::Bfs::predArc() "predArc()". Once the execution of the algorithm
kpeter@58: is finished, these query functions can be called.
kpeter@58: 
kpeter@58: For an example, let us say we want to print the shortest path of those nodes
kpeter@58: that are at most in a certain distance \c max_dist.
kpeter@49: \code
kpeter@49: bfs.run(s);
kpeter@49: 
kpeter@58: for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
kpeter@58:   if (bfs.reached(n) && bfs.dist(n) <= max_dist) {
kpeter@49:     std::cout << gr.id(n);
kpeter@58:     Node prev = bfs.prevNode(n);
kpeter@58:     while (prev != INVALID) {
kpeter@49:       std::cout << "<-" << gr.id(prev);
kpeter@49:       prev = bfs.prevNode(n);
kpeter@58:     }    
kpeter@49:     std::cout << std::endl;
kpeter@49:   }
kpeter@49: }
kpeter@49: \endcode
kpeter@49: 
kpeter@58: The class interfaces of the algorithms also support a finer control on
kpeter@58: the execution. For example, we can specify more source nodes and we can
kpeter@58: even run the algorithm step-by-step.
kpeter@58: If you need such control on the execution, you have to use more functions
kpeter@58: instead of \ref Bfs::run() "run()". First, you have to call \ref Bfs::init()
kpeter@58: "init()" to initialize the internal data structures.
kpeter@49: 
kpeter@49: \code
kpeter@49:   bfs.init();
kpeter@49: \endcode
kpeter@49: 
kpeter@58: Then you can add one or more source nodes to the queue with
kpeter@58: \ref Bfs::addSource() "addSource()". They will be processed, as they would
kpeter@58: be reached by the algorithm before. And yes, you can even add more sources
kpeter@58: during the execution.
kpeter@58: 
kpeter@49: \code
kpeter@58:   bfs.addSource(s1);
kpeter@58:   bfs.addSource(s2);
kpeter@49:   ...
kpeter@49: \endcode
kpeter@49: 
kpeter@58: Finally, the actual path computation of the algorithm can be performed with
kpeter@58: the \ref Bfs::start() "start()" function.
kpeter@49: 
kpeter@58: \code
kpeter@58:   bfs.start(t);
kpeter@58: \endcode
kpeter@49: 
kpeter@58: Instead of using \ref Bfs::start() "start()", you can even execute the
kpeter@58: algorithm step-by-step, so you can write your own loop to process the
kpeter@58: nodes one-by-one.
kpeter@58: For example, the following code will executes the algorithm in such a way,
kpeter@58: that it reaches all nodes in the digraph, namely the algorithm is started
kpeter@58: for each node that is not visited before.
kpeter@49: 
kpeter@58: \code
kpeter@58:   bfs.init();
kpeter@58:   for (NodeIt n(g); n != INVALID; ++n) {
kpeter@58:     if (!bfs.reached(n)) {
kpeter@58:       bfs.addSource(n);
kpeter@58:       bfs.start();
kpeter@58:     }
kpeter@58:   }
kpeter@58: \endcode
kpeter@49: 
kpeter@58: <tt>bfs.start()</tt> is only a shortcut of the following code.
kpeter@49: 
kpeter@58: \code
kpeter@58:   while (!bfs.emptyQueue()) {
kpeter@58:     bfs.processNextNode();
kpeter@58:   }
kpeter@58: \endcode
kpeter@49: 
kpeter@58: \todo Write about function-type interfaces
kpeter@49: 
kpeter@49: 
kpeter@58: Since the DFS algorithm is very similar to BFS with a few tiny differences,
kpeter@58: the \ref Dfs class can be used similarly to \ref Bfs.
kpeter@49: 
kpeter@49: 
kpeter@46: [SEC]sec_shortest_paths[SEC] Shortest Paths
kpeter@46: 
kpeter@58: If you would like to solve some transportation problems in a network, then
kpeter@58: you will most likely want to find shortest paths between nodes of a graph.
kpeter@58: This is usually solved using Dijkstra's algorithm. 
kpeter@58: The following code is a simple program using the LEMON \ref Dijkstra class
kpeter@58: through the function-type interface \ref dijkstra().
kpeter@58: It calculates the shortest path between node \c s and \c t in a digraph \c g.
kpeter@46: 
kpeter@58: \code
kpeter@58:   dijkstra(g, length).distMap(dist).run(s,t);
kpeter@58: \endcode
kpeter@49:  
kpeter@49: In LEMON, the algorithms are implemented basically as classes, but
kpeter@49: for some of them, function-type interfaces are also available
kpeter@49: for the sake of convenience.
kpeter@49: For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra
kpeter@49: template class, but the \ref dijkstra() function is also defined,
kpeter@49: which can still be used quite flexibly due to named parameters.
kpeter@49: 
kpeter@58: The above sample code could also use the class interface as follows.
kpeter@49: 
kpeter@49: \code
kpeter@50:   Dijkstra<ListDigraph> dijkstra(g, length);
kpeter@49:   dijkstra.distMap(dist);
kpeter@49:   dijsktra.init();
kpeter@58:   dijkstra.addSource(s);
kpeter@49:   dijkstra.start();
kpeter@49: \endcode
kpeter@49: 
kpeter@49: The previous code is obviously longer than the original, but the
kpeter@49: execution can be controlled to a higher extent. While using the function-type
kpeter@49: interface, only one source can be added to the algorithm, the class
kpeter@49: interface makes it possible to specify several root nodes.
kpeter@49: Moreover, the algorithm can also be executed step-by-step. For instance,
kpeter@49: the following code can be used instead of \ref dijkstra.start().
kpeter@49: 
kpeter@49: \code
kpeter@49:   while (!dijkstra.emptyQueue()) {
kpeter@49:     ListDigraph::Node n = dijkstra.processNextNode();
kpeter@49:     cout << g.id(n) << ' ' << dijkstra.dist(g) << endl;
kpeter@49:   }
kpeter@49: \endcode
kpeter@49: 
kpeter@58: LEMON provides several other algorithms for findign shortest paths in
kpeter@58: specific or more general cases. For example, \ref BellmanFord can be used
kpeter@58: instead of \ref Dijkstra when the graph contains an arc with negative cost.
kpeter@58: You may check the \ref shortest_path module of the reference manual for
kpeter@58: more details.
kpeter@58: 
kpeter@49: 
kpeter@46: [SEC]sec_max_flow[SEC] Maximum Flows
kpeter@46: 
kpeter@46: See \ref Preflow.
kpeter@46: 
kpeter@58: \todo Write this subsection.
kpeter@58: 
kpeter@46: [TRAILER]
kpeter@46: */
kpeter@46: }