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@46: 
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@49: The library probvides quite flexible and efficient implementations
kpeter@49: for well-known fundamental algorithms, such as breadth-first
kpeter@49: search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm
kpeter@49: and methods for discovering graph properties like connectivity, bipartiteness
kpeter@49: or Euler property, as well as more complex optimization algorithms for finding
kpeter@49: maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint
kpeter@49: paths.
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@49: \todo The following contents are ported from the LEMON 0.x tutorial,
kpeter@49: thus they have to thouroughly revised, reorganized and reworked.
kpeter@49: 
kpeter@46: See \ref Bfs, \ref Dfs and \ref graph_properties.
kpeter@46: 
kpeter@49: Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
kpeter@49: implementations of the well known algorithms. The algorithms are placed most cases in
kpeter@49: separated files named after the algorithm itself but lower case as all other header file names.
kpeter@49: For example the next Bfs class is in the \c lemon/bfs.h.
kpeter@49: 
kpeter@49: The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
kpeter@49: The class has two template parameters: \b GR and \b TR.<br>
kpeter@49: GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type.
kpeter@49: TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
kpeter@49: wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
kpeter@49: 
kpeter@49: To use the class, declare it!
kpeter@49: \code
kpeter@49: Bfs<ListGraph>  bfs(gr);
kpeter@49: \endcode
kpeter@49: Note the lack of second template argument because of the default parameter.
kpeter@49: 
kpeter@49: It provides a simple but powerful interface to control the execution.
kpeter@49: \code
kpeter@49: int dist = bfs.run(s,t);
kpeter@49: \endcode
kpeter@49: It finds the shortest path from node \c s to node \c t and returns it, or zero
kpeter@49: if there is no path from \c s to \c t.<br>
kpeter@49: If you want the shortest path from a specified node to all other node, just write:
kpeter@49: \code
kpeter@49: bfs.run(s);
kpeter@49: \endcode
kpeter@49: Now the distances and path information are stored in maps which you can access with
kpeter@49: member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
kpeter@49: Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm
kpeter@49: is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
kpeter@49: "predNode()" can be called.
kpeter@49: 
kpeter@49: For an example let's say we want to print the shortest path of those nodes which
kpeter@49: are in a certain distance.
kpeter@49: \code
kpeter@49: bfs.run(s);
kpeter@49: 
kpeter@49: for( ListGraph::NodeIt  n(gr); n != INVALID; ++n ) {
kpeter@49:   if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
kpeter@49:     std::cout << gr.id(n);
kpeter@49: 
kpeter@49:     Node  prev = bfs.prevNode(n);
kpeter@49:     while( prev != INVALID ) {
kpeter@49:       std::cout << "<-" << gr.id(prev);
kpeter@49:       prev = bfs.prevNode(n);
kpeter@49:     }
kpeter@49:     
kpeter@49:     std::cout << std::endl;
kpeter@49:   }
kpeter@49: }
kpeter@49: \endcode
kpeter@49: 
kpeter@49: In the previous code we only used \c run(). Now we introduce the way you can directly
kpeter@49: control the execution of the algorithm.
kpeter@49: 
kpeter@49: First you have to initialize the variables with \ref lemon::Bfs::init "init()".
kpeter@49: \code
kpeter@49:   bfs.init();
kpeter@49: \endcode
kpeter@49: 
kpeter@49: Then you add one or more source nodes to the queue. They will be processed, as they would
kpeter@49: be reached by the algorithm before. And yes - you can add more sources during the execution.
kpeter@49: \code
kpeter@49:   bfs.addSource(node_1);
kpeter@49:   bfs.addSource(node_2);
kpeter@49:   ...
kpeter@49: \endcode
kpeter@49: 
kpeter@49: And finally you can start the process with \ref lemon::Bfs::start "start()", or
kpeter@49: you can write your own loop to process the nodes one-by-one.
kpeter@49: 
kpeter@49: 
kpeter@49: Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
kpeter@49: to demonstrate Dfs's capabilities.
kpeter@49: 
kpeter@49: We will see a program, which solves the problem of <b>topological ordering</b>.
kpeter@49: We need to know in which order we should put on our clothes. The program will do the following:
kpeter@49: <ol>
kpeter@49: <li>We run the dfs algorithm to all nodes.
kpeter@49: <li>Put every node into a list when processed completely.
kpeter@49: <li>Write out the list in reverse order.
kpeter@49: </ol>
kpeter@49: 
kpeter@49: \dontinclude topological_ordering.cc
kpeter@49: First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
kpeter@49: will be done through it.
kpeter@49: \skip MyOrdererMap
kpeter@49: \until };
kpeter@49: The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
kpeter@49: we need to do is insert the key - that is the node whose processing just finished - into the beginning
kpeter@49: of the list.<br>
kpeter@49: Although we implemented this needed helper class ourselves it was not necessary.
kpeter@49: The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
kpeter@49: what we needed. To be correct it's more general - and it's all in \c LEMON. But
kpeter@49: we wanted to show you, how easy is to add additional functionality.
kpeter@49: 
kpeter@49: First we declare the needed data structures: the digraph and a map to store the nodes' label.
kpeter@49: \skip ListDigraph
kpeter@49: \until label
kpeter@49: 
kpeter@49: Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
kpeter@49: ordering.
kpeter@49: \skip belt
kpeter@49: \until trousers
kpeter@49: We label them...
kpeter@49: \skip label
kpeter@49: \until trousers
kpeter@49: Then add arcs which represent the precedences between those items.
kpeter@49: \skip trousers, belt
kpeter@49: \until );
kpeter@49: 
kpeter@49: See how easy is to access the internal information of this algorithm trough maps.
kpeter@49: We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
kpeter@49: \skip Dfs
kpeter@49: \until run
kpeter@49: 
kpeter@49: And now comes the third part. Write out the list in reverse order. But the list was
kpeter@49: composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
kpeter@49: \skip std
kpeter@49: \until endl
kpeter@49: 
kpeter@49: The program is to be found in the \ref demo directory: \ref topological_ordering.cc
kpeter@49: 
kpeter@49: \todo Check the linking of the demo file, the code samples are missing.
kpeter@49: 
kpeter@49: More algorithms are described in the \ref algorithms2 "second part".
kpeter@49: 
kpeter@49: 
kpeter@46: [SEC]sec_shortest_paths[SEC] Shortest Paths
kpeter@46: 
kpeter@46: See \ref Dijkstra and \ref BellmanFord.
kpeter@46: 
kpeter@49: 
kpeter@49: If you want to solve some transportation problems in a network then you
kpeter@49: will want to find shortest paths between nodes of a graph. This is
kpeter@49: usually solved using Dijkstra's algorithm. A utility that solves this is
kpeter@49: the LEMON Dijkstra class. The following code is a simple program using
kpeter@49: the LEMON Dijkstra class: it calculates the shortest path between node s
kpeter@49: and t in a graph g. We omit the part reading the graph g and the length
kpeter@49: map len.
kpeter@49: 
kpeter@49: <hr>
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@49: The original 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@49:   dijkstra.addSource(u);
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@49: 
kpeter@46: [SEC]sec_max_flow[SEC] Maximum Flows
kpeter@46: 
kpeter@46: See \ref Preflow.
kpeter@46: 
kpeter@46: [TRAILER]
kpeter@46: */
kpeter@46: }