20 /** |
20 /** |
21 [PAGE]sec_algorithms[PAGE] Algorithms |
21 [PAGE]sec_algorithms[PAGE] Algorithms |
22 |
22 |
23 \todo This page is under construction. |
23 \todo This page is under construction. |
24 |
24 |
|
25 \todo The following contents are mainly ported from the LEMON 0.x tutorial, |
|
26 thus they have to be thoroughly revised and reworked. |
|
27 |
|
28 \warning Currently, this section may contain old or faulty contents. |
|
29 |
25 In addition to the graph structures, the most important parts of LEMON are |
30 In addition to the graph structures, the most important parts of LEMON are |
26 the various algorithms related to graph theory and combinatorial optimization. |
31 the various algorithms related to graph theory and combinatorial optimization. |
27 The library probvides quite flexible and efficient implementations |
32 The library provides quite flexible and efficient implementations |
28 for well-known fundamental algorithms, such as breadth-first |
33 for well-known fundamental algorithms, such as breadth-first |
29 search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm |
34 search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm |
30 and methods for discovering graph properties like connectivity, bipartiteness |
35 and methods for discovering graph properties like connectivity, bipartiteness |
31 or Euler property, as well as more complex optimization algorithms for finding |
36 or Euler property, as well as more complex optimization algorithms for finding |
32 maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint |
37 maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint |
35 In this section, we present only some of the most fundamental algorithms. |
40 In this section, we present only some of the most fundamental algorithms. |
36 For a complete overview, see the \ref algs module of the reference manual. |
41 For a complete overview, see the \ref algs module of the reference manual. |
37 |
42 |
38 [SEC]sec_graph_search[SEC] Graph Search |
43 [SEC]sec_graph_search[SEC] Graph Search |
39 |
44 |
40 \todo The following contents are ported from the LEMON 0.x tutorial, |
|
41 thus they have to thouroughly revised, reorganized and reworked. |
|
42 |
|
43 See \ref Bfs, \ref Dfs and \ref graph_properties. |
45 See \ref Bfs, \ref Dfs and \ref graph_properties. |
44 |
46 |
45 Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient |
47 Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient |
46 implementations of the well known algorithms. The algorithms are placed most cases in |
48 implementations of the well known algorithms. The algorithms are placed most cases in |
47 separated files named after the algorithm itself but lower case as all other header file names. |
49 separated files named after the algorithm itself but lower case as all other header file names. |
48 For example the next Bfs class is in the \c lemon/bfs.h. |
50 For example the next Bfs class is in the \c lemon/bfs.h. |
49 |
51 |
50 The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function. |
52 The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function. |
51 The class has two template parameters: \b GR and \b TR.<br> |
53 The class has two template parameters: \b GR and \b TR.<br> |
52 GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type. |
54 GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type. |
53 TR is a Traits class commonly used to easy the parametrization of templates. In most cases you |
55 TR is a Traits class commonly used to easy the parameterization of templates. In most cases you |
54 wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>". |
56 wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>". |
55 |
57 |
56 To use the class, declare it! |
58 To use the class, declare it! |
57 \code |
59 \code |
58 Bfs<ListGraph> bfs(gr); |
60 Bfs<ListGraph> bfs(gr); |