class. We use the implicit minimum time map as the length map of the

 class. We use the implicit minimum time map as the length map of the

 \c Dijkstra algorithm.

 \c Dijkstra algorithm.

 */

 */

 /**

 /**

 @defgroup paths Path Structures

 @defgroup paths Path Structures

 @ingroup datas

 @ingroup datas

 \brief %Path structures implemented in LEMON.

 \brief %Path structures implemented in LEMON.

 This group contains the path structures implemented in LEMON.

 This group contains the path structures implemented in LEMON.

 All of them have similar interfaces and they can be copied easily with

 All of them have similar interfaces and they can be copied easily with

 assignment operators and copy constructors. This makes it easy and

 assignment operators and copy constructors. This makes it easy and

 efficient to have e.g. the Dijkstra algorithm to store its result in

 efficient to have e.g. the Dijkstra algorithm to store its result in

 any kind of path structure.

 any kind of path structure.

 */

 */

 /**

 /**

 @defgroup auxdat Auxiliary Data Structures

 @defgroup auxdat Auxiliary Data Structures

 @ingroup datas

 @ingroup datas

 This group contains some data structures implemented in LEMON in

 This group contains some data structures implemented in LEMON in

 order to make it easier to implement combinatorial algorithms.

 order to make it easier to implement combinatorial algorithms.

 */

 */

 /**

 /**

 @defgroup algs Algorithms

 @defgroup algs Algorithms

 \brief This group contains the several algorithms

 \brief This group contains the several algorithms

 implemented in LEMON.

 implemented in LEMON.

 This group contains the several algorithms

 This group contains the several algorithms

 @defgroup search Graph Search

 @defgroup search Graph Search

 @ingroup algs

 @ingroup algs

 \brief Common graph search algorithms.

 \brief Common graph search algorithms.

 This group contains the common graph search algorithms, namely

 This group contains the common graph search algorithms, namely

 */

 */

 /**

 /**

 @defgroup shortest_path Shortest Path Algorithms

 @defgroup shortest_path Shortest Path Algorithms

 @ingroup algs

 @ingroup algs

 \brief Algorithms for finding shortest paths.

 \brief Algorithms for finding shortest paths.

  - \ref Dijkstra algorithm for finding shortest paths from a source node

  - \ref Dijkstra algorithm for finding shortest paths from a source node

    when all arc lengths are non-negative.

    when all arc lengths are non-negative.

  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths

  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths

    from a source node when arc lenghts can be either positive or negative,

    from a source node when arc lenghts can be either positive or negative,

  - \ref Suurballe A successive shortest path algorithm for finding

  - \ref Suurballe A successive shortest path algorithm for finding

    arc-disjoint paths between two nodes having minimum total length.

    arc-disjoint paths between two nodes having minimum total length.

 */

 */

 /**

 /**

 @defgroup max_flow Maximum Flow Algorithms

 @defgroup max_flow Maximum Flow Algorithms

 @ingroup algs

 @ingroup algs

 \brief Algorithms for finding maximum flows.

 \brief Algorithms for finding maximum flows.

 This group contains the algorithms for finding maximum flows and

 This group contains the algorithms for finding maximum flows and

 The \e maximum \e flow \e problem is to find a flow of maximum value between

 The \e maximum \e flow \e problem is to find a flow of maximum value between

 a single source and a single target. Formally, there is a \f$G=(V,A)\f$

 a single source and a single target. Formally, there is a \f$G=(V,A)\f$

 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and

 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and

 \f$s, t \in V\f$ source and target nodes.

 \f$s, t \in V\f$ source and target nodes.

 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)

 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)

     \quad \forall u\in V\setminus\{s,t\} \f]

     \quad \forall u\in V\setminus\{s,t\} \f]

 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]

 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]

 LEMON contains several algorithms for solving maximum flow problems:

 LEMON contains several algorithms for solving maximum flow problems:

 fastest method for computing a maximum flow. All implementations

 fastest method for computing a maximum flow. All implementations

 also provide functions to query the minimum cut, which is the dual

 also provide functions to query the minimum cut, which is the dual

 problem of maximum flow.

 problem of maximum flow.

 \ref Circulation is a preflow push-relabel algorithm implemented directly 

 \ref Circulation is a preflow push-relabel algorithm implemented directly 

 @ingroup algs

 @ingroup algs

 \brief Algorithms for finding minimum cost flows and circulations.

 \brief Algorithms for finding minimum cost flows and circulations.

 This group contains the algorithms for finding minimum cost flows and

 This group contains the algorithms for finding minimum cost flows and

 LEMON contains several algorithms for this problem.

 LEMON contains several algorithms for this problem.

  - \ref NetworkSimplex Primal Network Simplex algorithm with various

  - \ref NetworkSimplex Primal Network Simplex algorithm with various

  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on

  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on

  - \ref CapacityScaling Successive Shortest %Path algorithm with optional

  - \ref CapacityScaling Successive Shortest %Path algorithm with optional

 In general NetworkSimplex is the most efficient implementation,

 In general NetworkSimplex is the most efficient implementation,

 but in special cases other algorithms could be faster.

 but in special cases other algorithms could be faster.

 For example, if the total supply and/or capacities are rather small,

 For example, if the total supply and/or capacities are rather small,

 CapacityScaling is usually the fastest algorithm (without effective scaling).

 CapacityScaling is usually the fastest algorithm (without effective scaling).

 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a

 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a

 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum

 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum

 cut is the \f$X\f$ solution of the next optimization problem:

 cut is the \f$X\f$ solution of the next optimization problem:

 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}

 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}

 LEMON contains several algorithms related to minimum cut problems:

 LEMON contains several algorithms related to minimum cut problems:

 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut

 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut

   in directed graphs.

   in directed graphs.

 one, though the best known theoretical bound on its running time is

 one, though the best known theoretical bound on its running time is

 exponential.

 exponential.

 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space

 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space

 O(n<sup>2</sup>+e), but the latter one is typically faster due to the

 O(n<sup>2</sup>+e), but the latter one is typically faster due to the

 applied early termination scheme.

 applied early termination scheme.

 */

 */

 /**

 /**

 @defgroup matching Matching Algorithms

 @defgroup matching Matching Algorithms

 @ingroup algs

 @ingroup algs

 \image html bipartite_matching.png

 \image html bipartite_matching.png

 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth

 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth

 */

 */

 /**

 /**

 */

 */

 /**

 /**

 @defgroup auxalg Auxiliary Algorithms

 @defgroup auxalg Auxiliary Algorithms

 @ingroup algs

 @ingroup algs

 \brief Auxiliary algorithms implemented in LEMON.

 \brief Auxiliary algorithms implemented in LEMON.

 This group contains some algorithms implemented in LEMON

 This group contains some algorithms implemented in LEMON

 in order to make it easier to implement complex algorithms.

 in order to make it easier to implement complex algorithms.

 */

 */

 /**

 /**

 @defgroup gen_opt_group General Optimization Tools

 @defgroup gen_opt_group General Optimization Tools

 \brief This group contains some general optimization frameworks

 \brief This group contains some general optimization frameworks

 This group contains some general optimization frameworks

 This group contains some general optimization frameworks

 implemented in LEMON.

 implemented in LEMON.

 */

 */

 /**

 /**

 @ingroup gen_opt_group

 @ingroup gen_opt_group

 */

 */

 /**

 /**

 @defgroup lp_utils Tools for Lp and Mip Solvers

 @defgroup lp_utils Tools for Lp and Mip Solvers

 @ingroup lp_group

 @ingroup lp_group

 This group contains general \c EPS drawing methods and special

 This group contains general \c EPS drawing methods and special

 graph exporting tools.

 graph exporting tools.

 */

 */

 /**

 /**

 @ingroup io_group

 @ingroup io_group

 \brief Read and write files in DIMACS format

 \brief Read and write files in DIMACS format

 Tools to read a digraph from or write it to a file in DIMACS format data.

 Tools to read a digraph from or write it to a file in DIMACS format data.

 */

 */

 /**

 /**

 @defgroup graph_concepts Graph Structure Concepts

 @defgroup graph_concepts Graph Structure Concepts

 @ingroup concept

 @ingroup concept

 \brief Skeleton and concept checking classes for graph structures

 \brief Skeleton and concept checking classes for graph structures

 */

 */

 /**

 /**

 @defgroup map_concepts Map Concepts

 @defgroup map_concepts Map Concepts

 @ingroup concept

 @ingroup concept

 This group contains the skeletons and concept checking classes of maps.

 This group contains the skeletons and concept checking classes of maps.

 */

 */

 /**

 /**

 \anchor demoprograms

 \anchor demoprograms

 @defgroup demos Demo Programs

 @defgroup demos Demo Programs

 Some demo programs are listed here. Their full source codes can be found in

 Some demo programs are listed here. Their full source codes can be found in

 In order to compile them, use the <tt>make demo</tt> or the

 In order to compile them, use the <tt>make demo</tt> or the

 <tt>make check</tt> commands.

 <tt>make check</tt> commands.

 */

 */

 }

 }