RhodeCode

namespace lemon {

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 concepts::ReadMap "read-only maps".

This group describes the common graph search algorithms, namely

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

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

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

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

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

following optimization problem.

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

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

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

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

- \ref EdmondsKarp Edmonds-Karp algorithm.

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

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

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

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

fastest method for computing a maximum flow. All implementations

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

problem of the maximum flow.

The \e minimum \e cost \e flow \e problem is to find a feasible flow of

minimum total cost from a set of supply nodes to a set of demand nodes

in a network with capacity constraints and arc costs.

Formally, let \f$G=(V,A)\f$ be a digraph,

\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and

upper bounds for the flow values on the arcs,

\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow

on the arcs, and

\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values

of the nodes.

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

the following optimization problem.

\f[ \min\sum_{a\in A} f(a) cost(a) \f]

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

    supply(v) \qquad \forall v\in V \f]

\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]

LEMON contains several algorithms for solving minimum cost flow problems:

 - \ref CycleCanceling Cycle-canceling algorithms.

 - \ref CapacityScaling Successive shortest path algorithm with optional

   capacity scaling.

 - \ref CostScaling Push-relabel and augment-relabel algorithms based on

   cost scaling.

 - \ref NetworkSimplex Primal network simplex algorithm with various

   pivot strategies.

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

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

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

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

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

  in directed graphs.

- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for

  calculating minimum cut in undirected graphs.

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

  all-pairs minimum cut in undirected graphs.

see the \ref max_flow "maximum flow problem".

can be finding maximum cardinality, maximum weight or minimum cost

The matching algorithms implemented in LEMON:

- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm

  for calculating maximum cardinality matching in bipartite graphs.

- \ref PrBipartiteMatching Push-relabel algorithm

  for calculating maximum cardinality matching in bipartite graphs.

- \ref MaxWeightedBipartiteMatching

  Successive shortest path algorithm for calculating maximum weighted

  matching and maximum weighted bipartite matching in bipartite graphs.

- \ref MinCostMaxBipartiteMatching

  Successive shortest path algorithm for calculating minimum cost maximum

  matching in bipartite graphs.

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

  maximum cardinality matching in general graphs.

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

  maximum weighted matching in general graphs.

- \ref MaxWeightedPerfectMatching

  Edmond's blossom shrinking algorithm for calculating maximum weighted

  perfect matching in general graphs.

tree in a graph.

@defgroup demos Demo Programs

@defgroup tools Standalone Utility Applications

}