RhodeCode

LEMON contains several algorithms for this problem.

 - \ref NetworkSimplex Primal Network Simplex algorithm with various

   pivot strategies.

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

   cost scaling.

 - \ref CapacityScaling Successive Shortest %Path algorithm with optional

   capacity scaling.

 - \ref CancelAndTighten The Cancel and Tighten algorithm.

 - \ref CycleCanceling Cycle-Canceling algorithms.

In general NetworkSimplex is the most efficient implementation,

but in special cases other algorithms could be faster.

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

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

*/

/**

@defgroup min_cut Minimum Cut Algorithms

@ingroup algs

\brief Algorithms for finding minimum cut in graphs.

This group contains the algorithms for finding minimum cut in graphs.

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

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

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

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

LEMON contains several algorithms related to minimum cut problems:

- \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 GomoryHu "Gomory-Hu tree computation" for calculating

  all-pairs minimum cut in undirected graphs.

If you want to find minimum cut just between two distinict nodes,

see the \ref max_flow "maximum flow problem".

*/

/**

@defgroup graph_properties Connectivity and Other Graph Properties

@ingroup algs

\brief Algorithms for discovering the graph properties

This group contains the algorithms for discovering the graph properties

like connectivity, bipartiteness, euler property, simplicity etc.

\image html edge_biconnected_components.png

\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth

*/

/**

@defgroup planar Planarity Embedding and Drawing

@ingroup algs

\brief Algorithms for planarity checking, embedding and drawing

This group contains the algorithms for planarity checking,

embedding and drawing.

\image html planar.png

\image latex planar.eps "Plane graph" width=\textwidth

*/

/**

@defgroup matching Matching Algorithms

@ingroup algs

\brief Algorithms for finding matchings in graphs and bipartite graphs.

This group contains the algorithms for calculating

matchings in graphs and bipartite graphs. The general matching problem is

finding a subset of the edges for which each node has at most one incident

edge.

There are several different algorithms for calculate matchings in

graphs.  The matching problems in bipartite graphs are generally

easier than in general graphs. The goal of the matching optimization

can be finding maximum cardinality, maximum weight or minimum cost

matching. The search can be constrained to find perfect or

maximum cardinality matching.

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.

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_HARTMANN_ORLIN_H

#define LEMON_HARTMANN_ORLIN_H

///

/// \file

/// \brief Hartmann-Orlin's algorithm for finding a minimum mean cycle.

#include <vector>

#include <limits>

#include <lemon/core.h>

#include <lemon/path.h>

#include <lemon/tolerance.h>

#include <lemon/connectivity.h>

namespace lemon {

  /// \brief Default traits class of HartmannOrlin algorithm.

  ///

  /// Default traits class of HartmannOrlin algorithm.

  /// \tparam GR The type of the digraph.

  /// \tparam LEN The type of the length map.

  /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.

#ifdef DOXYGEN

  template <typename GR, typename LEN>

#else

  template <typename GR, typename LEN,

    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>

#endif

  struct HartmannOrlinDefaultTraits

  {

    /// The type of the digraph

    typedef GR Digraph;

    /// The type of the length map

    typedef LEN LengthMap;

    /// The type of the arc lengths

    typedef typename LengthMap::Value Value;

    /// \brief The large value type used for internal computations

    ///

    /// The large value type used for internal computations.

    /// It is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    /// \c Value must be convertible to \c LargeValue.

    typedef double LargeValue;

    /// The tolerance type used for internal computations

    typedef lemon::Tolerance<LargeValue> Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addBack() function.

    typedef lemon::Path<Digraph> Path;

  };

  // Default traits class for integer value types

  template <typename GR, typename LEN>

  struct HartmannOrlinDefaultTraits<GR, LEN, true>

  {

    typedef GR Digraph;

    typedef LEN LengthMap;

    typedef typename LengthMap::Value Value;

#ifdef LEMON_HAVE_LONG_LONG

    typedef long long LargeValue;

#else

    typedef long LargeValue;

#endif

    typedef lemon::Tolerance<LargeValue> Tolerance;

    typedef lemon::Path<Digraph> Path;

  };

  /// @{

  /// \brief Implementation of the Hartmann-Orlin algorithm for finding

  /// a minimum mean cycle.

  ///

  /// This class implements the Hartmann-Orlin algorithm for finding

  /// a directed cycle of minimum mean length (cost) in a digraph.

  /// it applies an efficient early termination scheme.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam LEN The type of the length map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int>,

             typename TR = HartmannOrlinDefaultTraits<GR, LEN> >

#endif

  class HartmannOrlin

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the length map

    typedef typename TR::LengthMap LengthMap;

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",

    /// it is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",

    /// it is \ref lemon::Path "Path<Digraph>".

    typedef typename TR::Path Path;

    /// The \ref HartmannOrlinDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    // Data sturcture for path data

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_HOWARD_H

#define LEMON_HOWARD_H

///

/// \file

/// \brief Howard's algorithm for finding a minimum mean cycle.

#include <vector>

#include <limits>

#include <lemon/core.h>

#include <lemon/path.h>

#include <lemon/tolerance.h>

#include <lemon/connectivity.h>

namespace lemon {

  /// \brief Default traits class of Howard class.

  ///

  /// Default traits class of Howard class.

  /// \tparam GR The type of the digraph.

  /// \tparam LEN The type of the length map.

  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

#ifdef DOXYGEN

  template <typename GR, typename LEN>

#else

  template <typename GR, typename LEN,

    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>

#endif

  struct HowardDefaultTraits

  {

    /// The type of the digraph

    typedef GR Digraph;

    /// The type of the length map

    typedef LEN LengthMap;

    /// The type of the arc lengths

    typedef typename LengthMap::Value Value;

    /// \brief The large value type used for internal computations

    ///

    /// The large value type used for internal computations.

    /// It is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    /// \c Value must be convertible to \c LargeValue.

    typedef double LargeValue;

    /// The tolerance type used for internal computations

    typedef lemon::Tolerance<LargeValue> Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addBack() function.

    typedef lemon::Path<Digraph> Path;

  };

  // Default traits class for integer value types

  template <typename GR, typename LEN>

  struct HowardDefaultTraits<GR, LEN, true>

  {

    typedef GR Digraph;

    typedef LEN LengthMap;

    typedef typename LengthMap::Value Value;

#ifdef LEMON_HAVE_LONG_LONG

    typedef long long LargeValue;

#else

    typedef long LargeValue;

#endif

    typedef lemon::Tolerance<LargeValue> Tolerance;

    typedef lemon::Path<Digraph> Path;

  };

  /// @{

  /// \brief Implementation of Howard's algorithm for finding a minimum

  /// mean cycle.

  ///

  /// This class implements Howard's policy iteration algorithm for finding

  /// a directed cycle of minimum mean length (cost) in a digraph.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam LEN The type of the length map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int>,

             typename TR = HowardDefaultTraits<GR, LEN> >

#endif

  class Howard

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the length map

    typedef typename TR::LengthMap LengthMap;

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// Using the \ref HowardDefaultTraits "default traits class",

    /// it is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// Using the \ref HowardDefaultTraits "default traits class",

    /// it is \ref lemon::Path "Path<Digraph>".

    typedef typename TR::Path Path;

    /// The \ref HowardDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    // The digraph the algorithm runs on

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_KARP_H

#define LEMON_KARP_H

///

/// \file

/// \brief Karp's algorithm for finding a minimum mean cycle.

#include <vector>

#include <limits>

#include <lemon/core.h>

#include <lemon/path.h>

#include <lemon/tolerance.h>

#include <lemon/connectivity.h>

namespace lemon {

  /// \brief Default traits class of Karp algorithm.

  ///

  /// Default traits class of Karp algorithm.

  /// \tparam GR The type of the digraph.

  /// \tparam LEN The type of the length map.

  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

#ifdef DOXYGEN

  template <typename GR, typename LEN>

#else

  template <typename GR, typename LEN,

    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>

#endif

  struct KarpDefaultTraits

  {

    /// The type of the digraph

    typedef GR Digraph;

    /// The type of the length map

    typedef LEN LengthMap;

    /// The type of the arc lengths

    typedef typename LengthMap::Value Value;

    /// \brief The large value type used for internal computations

    ///

    /// The large value type used for internal computations.

    /// It is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    /// \c Value must be convertible to \c LargeValue.

    typedef double LargeValue;

    /// The tolerance type used for internal computations

    typedef lemon::Tolerance<LargeValue> Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addBack() function.

    typedef lemon::Path<Digraph> Path;

  };

  // Default traits class for integer value types

  template <typename GR, typename LEN>

  struct KarpDefaultTraits<GR, LEN, true>

  {

    typedef GR Digraph;

    typedef LEN LengthMap;

    typedef typename LengthMap::Value Value;

#ifdef LEMON_HAVE_LONG_LONG

    typedef long long LargeValue;

#else

    typedef long LargeValue;

#endif

    typedef lemon::Tolerance<LargeValue> Tolerance;

    typedef lemon::Path<Digraph> Path;

  };

  /// @{

  /// \brief Implementation of Karp's algorithm for finding a minimum

  /// mean cycle.

  ///

  /// This class implements Karp's algorithm for finding a directed

  /// cycle of minimum mean length (cost) in a digraph.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam LEN The type of the length map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int>,

             typename TR = KarpDefaultTraits<GR, LEN> >

#endif

  class Karp

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the length map

    typedef typename TR::LengthMap LengthMap;

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// Using the \ref KarpDefaultTraits "default traits class",

    /// it is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// Using the \ref KarpDefaultTraits "default traits class",

    /// it is \ref lemon::Path "Path<Digraph>".

    typedef typename TR::Path Path;

    /// The \ref KarpDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    // Data sturcture for path data