values to the nodes and arcs of graphs.

 values to the nodes and arcs/edges of graphs.

 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,

 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".

 Most of them are \ref lemon::concepts::ReadMap "read-only maps".

 Most of them are \ref concepts::ReadMap "read-only maps".

 This group describes the common graph search algorithms like

 This group describes the common graph search algorithms, namely

 Breadth-First Search (BFS) and Depth-First Search (DFS).

 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).

 This group describes the algorithms for finding shortest paths in graphs.

 This group describes the algorithms for finding shortest paths in digraphs.

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

    when all arc lengths are non-negative.

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

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

    but the digraph should not contain directed cycles with negative total

    length.

  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms

    for solving the \e all-pairs \e shortest \e paths \e problem when arc

    lenghts can be either positive or negative, but the digraph should

    not contain directed cycles with negative total length.

  - \ref Suurballe A successive shortest path algorithm for finding

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

 The maximum flow problem is to find a flow between a single source and

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

 a single target that is maximum. 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$

 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity

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

 function and given \f$s, t \in V\f$ source and target node. The

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

 maximum flow is the \f$f_a\f$ solution of the next optimization problem:

 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the

 following optimization problem.

 \f[ 0 \le f_a \le c_a \f]

 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}

 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]

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

 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)

 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]

     \qquad \forall v\in V\setminus\{s,t\} \f]

 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]

 - \ref lemon::EdmondsKarp "Edmonds-Karp"

 - \ref EdmondsKarp Edmonds-Karp algorithm.

 - \ref lemon::Preflow "Goldberg's Preflow algorithm"

 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.

 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"

 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.

 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"

 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.

 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the

 In most cases the \ref Preflow "Preflow" algorithm provides the

 fastest method to compute the maximum flow. All impelementations

 fastest method for computing a maximum flow. All implementations

 provides functions to query the minimum cut, which is the dual linear

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

 programming problem of the maximum flow.

 problem of the maximum flow.

 The minimum cut problem is to find a non-empty and non-complete

 The \e minimum \e cut \e problem is to find a non-empty and non-complete

 \f$X\f$ subset of the vertices with minimum overall capacity on

 \f$X\f$ subset of the nodes with minimum overall capacity on

 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an

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

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

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

 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]

     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]

 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut

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

   in directed graphs

   in directed graphs.

 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to

 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for

   calculate minimum cut in undirected graphs

   calculating minimum cut in undirected graphs.

 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all

 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating

   pairs minimum cut in undirected graphs

   all-pairs minimum cut in undirected graphs.

 please see the \ref max_flow "Maximum Flow page".

 see the \ref max_flow "maximum flow problem".

 can be the finding maximum cardinality, maximum weight or minimum cost

 can be finding maximum cardinality, maximum weight or minimum cost

 LEMON contains the next algorithms:

 The matching algorithms implemented in LEMON:

 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp

 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm

   augmenting path algorithm for calculate maximum cardinality matching in

   for calculating maximum cardinality matching in bipartite graphs.

   bipartite graphs

 - \ref PrBipartiteMatching Push-relabel algorithm

 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel

   for calculating maximum cardinality matching in bipartite graphs.

   algorithm for calculate maximum cardinality matching in bipartite graphs

 - \ref MaxWeightedBipartiteMatching

 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"

   Successive shortest path algorithm for calculating maximum weighted

   Successive shortest path algorithm for calculate maximum weighted matching

   matching and maximum weighted bipartite matching in bipartite graphs.

   and maximum weighted bipartite matching in bipartite graph

 - \ref MinCostMaxBipartiteMatching

 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"

   Successive shortest path algorithm for calculating minimum cost maximum

   Successive shortest path algorithm for calculate minimum cost maximum

   matching in bipartite graphs.

   matching in bipartite graph

 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating

 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm

   maximum cardinality matching in general graphs.

   for calculate maximum cardinality matching in general graph

 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating

 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom

   maximum weighted matching in general graphs.

   shrinking algorithm for calculate maximum weighted matching in general

 - \ref MaxWeightedPerfectMatching

   graph

   Edmond's blossom shrinking algorithm for calculating maximum weighted

 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"

   perfect matching in general graphs.

   Edmond's blossom shrinking algorithm for calculate maximum weighted

   perfect matching in general graph

 tree in a graph

 tree in a graph.

 @defgroup demos Demo programs

 @defgroup demos Demo Programs

 @defgroup tools Standalone utility applications

 @defgroup tools Standalone Utility Applications