RhodeCode

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

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

@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.

*/

/**

@defgroup planar Planarity Embedding and Drawing

@ingroup algs

\brief Algorithms for planarity checking, embedding and drawing

  public:

    ///\name Execution Control

    ///The simplest way to execute the BFS algorithm is to use one of the

    ///member functions called \ref run(Node) "run()".\n

    ///\ref addSource(). Finally the actual path computation can be

    ///performed with one of the \ref start() functions.

    ///@{

    ///\brief Initializes the internal data structures.

  public:

    /// \name Execution Control

    /// The simplest way to execute the BFS algorithm is to use one of the

    /// member functions called \ref run(Node) "run()".\n

    /// \ref addSource(). Finally the actual path computation can be

    /// performed with one of the \ref start() functions.

    /// @{

    /// \brief Initializes the internal data structures.

    /// \brief The type of the map that stores the flow values.

    ///

    /// The type of the map that stores the flow values.

    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"

    /// concept.

    typedef typename Digraph::template ArcMap<Value> FlowMap;

    /// \brief Instantiates a FlowMap.

    ///

    /// This function instantiates a \ref FlowMap.

    /// \param digraph The digraph for which we would like to define

    /// the flow map.

    }

    /// \brief The elevator type used by the algorithm.

    ///

    /// The elevator type used by the algorithm.

    ///

    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;

    /// \brief Instantiates an Elevator.

    ///

    /// This function instantiates an \ref Elevator.

    /// \param digraph The digraph for which we would like to define

    /// the elevator.

    const Tolerance& tolerance() const {

      return tolerance;

    }

    /// \name Execution Control

    /// The simplest way to execute the algorithm is to call \ref run().\n

    /// the \ref start() function.

    ///@{

    /// Initializes the internal data structures.

  public:

    ///\name Execution Control

    ///The simplest way to execute the DFS algorithm is to use one of the

    ///member functions called \ref run(Node) "run()".\n

    ///and perform the actual computation with \ref start().

    ///This procedure can be repeated if there are nodes that have not

    ///been reached.

    ///@{

  public:

    /// \name Execution Control

    /// The simplest way to execute the DFS algorithm is to use one of the

    /// member functions called \ref run(Node) "run()".\n

    /// and perform the actual computation with \ref start().

    /// This procedure can be repeated if there are nodes that have not

    /// been reached.

    /// @{

  public:

    ///\name Execution Control

    ///The simplest way to execute the %Dijkstra algorithm is to use

    ///one of the member functions called \ref run(Node) "run()".\n

    ///\ref addSource(). Finally the actual path computation can be

    ///performed with one of the \ref start() functions.

    ///@{

    ///\brief Initializes the internal data structures.

    /// GomoryHu. Before using it, you must allocate a GomoryHu class

    /// and call its \ref GomoryHu::run() "run()" method.

    ///

    /// This example counts the nodes in the minimum cut separating \c s from

    /// \c t.

    /// \code

    /// gom.run();

    /// int cnt=0;

    /// \endcode

    class MinCutNodeIt

    {

      bool _side;

      typename Graph::NodeIt _node_it;

      typename Graph::template NodeMap<bool> _cut;

    /// GomoryHu. Before using it, you must allocate a GomoryHu class

    /// and call its \ref GomoryHu::run() "run()" method.

    ///

    /// This example computes the value of the minimum cut separating \c s from

    /// \c t.

    /// \code

    /// gom.run();

    /// int value=0;

    ///   value+=capacities[e];

    /// \endcode

    /// The result will be the same as the value returned by

    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".

    class MinCutEdgeIt

    {

      return *this;

    }

    /// \name Execution Control

    /// The simplest way to execute the algorithm is to use

    /// one of the member functions called \c run(...). \n

    /// source nodes with \ref addSource().

    /// Finally \ref start() will perform the arborescence

    /// computation.

    ///@{

    typedef typename CapacityMap::Value Value;

    /// \brief The type of the map that stores the flow values.

    ///

    /// The type of the map that stores the flow values.

    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    typedef typename Digraph::template ArcMap<Value> FlowMap;

    /// \brief Instantiates a FlowMap.

    ///

    /// This function instantiates a \ref FlowMap.

    /// \param digraph The digraph for which we would like to define

    /// the flow map.

    }

    /// \brief The elevator type used by Preflow algorithm.

    ///

    /// The elevator type used by Preflow algorithm.

    ///

    /// \brief Instantiates an Elevator.

    ///

    /// This function instantiates an \ref Elevator.

    /// \param digraph The digraph for which we would like to define

    /// the elevator.

      return tolerance;

    }

    /// \name Execution Control

    /// The simplest way to execute the preflow algorithm is to use

    /// \ref run() or \ref runMinCut().\n

    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().

    ///@{

    /// \brief Initializes the internal data structures.

    ///