Index: algorithms.dox =================================================================== --- algorithms.dox (revision 57) +++ algorithms.dox (revision 58) @@ -22,19 +22,17 @@ \todo This page is under construction. - -\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. +\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 breadth-first -search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm -and methods for discovering graph properties like connectivity, bipartiteness -or Euler property, as well as more complex optimization algorithms for finding -maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint -paths. +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. @@ -43,149 +41,143 @@ [SEC]sec_graph_search[SEC] Graph Search -See \ref Bfs, \ref Dfs and \ref graph_properties. - -Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient -implementations of the well known algorithms. The algorithms are placed most cases in -separated files named after the algorithm itself but lower case as all other header file names. -For example the next Bfs class is in the \c lemon/bfs.h. - -The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function. -The class has two template parameters: \b GR and \b TR.
-GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type. -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". - -To use the class, declare it! -\code -Bfs bfs(gr); -\endcode -Note the lack of second template argument because of the default parameter. - -It provides a simple but powerful interface to control the execution. -\code -int dist = bfs.run(s,t); -\endcode -It finds the shortest path from node \c s to node \c t and returns it, or zero -if there is no path from \c s to \c t.
-If you want the shortest path from a specified node to all other node, just write: +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 bfs.h for using \ref Bfs. + +\code + #include +\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 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); -\endcode -Now the distances and path information are stored in maps which you can access with -member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".