\todo This section should be revised and extended.

 \todo The following contents are mainly ported from the LEMON 0.x tutorial,

 thus they have to be thoroughly revised and reworked.

 \warning Currently, this section may contain old or faulty contents.

 for well-known fundamental algorithms, such as breadth-first

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

 search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm

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

 and methods for discovering graph properties like connectivity, bipartiteness

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

 or Euler property, as well as more complex optimization algorithms for finding

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

 maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint

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

 paths.

 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.

 See \ref Bfs, \ref Dfs and \ref graph_properties.

 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

 Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient

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

 implementations of the well known algorithms. The algorithms are placed most cases in

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

 separated files named after the algorithm itself but lower case as all other header file names.

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

 For example the next Bfs class is in the \c lemon/bfs.h.

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

 The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.

 \code

 The class has two template parameters: \b GR and \b TR.<br>

    #include <lemon/bfs.h>

 GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type.

 \endcode

 TR is a Traits class commonly used to easy the parameterization of templates. In most cases you

 wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".

 Basically, all algorithms are implemented in template classes.

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

 To use the class, declare it!

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

 \code

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

 Bfs<ListGraph>  bfs(gr);

 \endcode

 \code

 Note the lack of second template argument because of the default parameter.

   ListDigraph g;

   Bfs<ListDigraph> bfs(g);

 It provides a simple but powerful interface to control the execution.

 \endcode

 \code

 int dist = bfs.run(s,t);

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

 \endcode

 of the algorithm and to obtain all the results.

 It finds the shortest path from node \c s to node \c t and returns it, or zero

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

 if there is no path from \c s to \c t.<br>

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

 If you want the shortest path from a specified node to all other node, just write:

 \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.

 \endcode

 Now the distances and path information are stored in maps which you can access with

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

 member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>

   if (bfs.reached(n) && bfs.dist(n) <= max_dist) {

 Or more directly with other member functions like \ref lemon::Bfs::predNode "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( ListGraph::NodeIt  n(gr); n != INVALID; ++n ) {

   if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {

     Node prev = bfs.prevNode(n);

     Node  prev = bfs.prevNode(n);

     while (prev != INVALID) {

     while( prev != INVALID ) {

   }

     std::cout << std::endl;

 \endcode

   }

 }

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

 \endcode

 \code

 In the previous code we only used \c run(). Now we introduce the way you can directly

   while (!bfs.emptyQueue()) {

 control the execution of the algorithm.

     bfs.processNextNode();

   }

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

 \endcode

 \code

   bfs.init();

 \todo Write about function-type interfaces

 \endcode

 Then you add one or more source nodes to the queue. They will be processed, as they would

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

 be reached by the algorithm before. And yes - you can add more sources during the execution.

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

 \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.

 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 concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing

 we need to do is insert the key - that is the node whose 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 digraph and a map to store the nodes' label.

 \skip ListDigraph

 \until label

 Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological

 ordering.

 \skip belt

 \until trousers

 We label them...

 \skip label

 \until trousers

 Then add arcs 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

 \todo Check the linking of the demo file, the code samples are missing.

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

 See \ref Dijkstra and \ref BellmanFord.

 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. 

 If you want to solve some transportation problems in a network then you

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

 will want to find shortest paths between nodes of a graph. This is

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

 usually solved using Dijkstra's algorithm. A utility that solves this is

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

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

 the LEMON Dijkstra class: it calculates the shortest path between node s

 \code

 and t in a graph g. We omit the part reading the graph g and the length

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

 map len.

 \endcode

 <hr>

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

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

   dijkstra.addSource(u);

   dijkstra.addSource(s);