RhodeCode

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:

This group contains the algorithms for discovering the graph properties

like connectivity, bipartiteness, euler property, simplicity etc.

*/

/**

    ///\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.

    /// \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.

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

    ///

    ///

    /// The elevator type used by the algorithm.

    ///

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

    /// \brief Instantiates an Elevator.

    ///

    /// \name Execution Control

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

    /// the \ref start() function.

    ///@{

    ///\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.

    /// \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.

    ///\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.

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

    /// \c t.

    /// \code

    /// gom.run();

    /// int cnt=0;

    /// \endcode

    class MinCutNodeIt

    {

    /// 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

    /// \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.

    ///

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

    ///

    ///

    /// The elevator type used by Preflow algorithm.

    ///

    /// \brief Instantiates an Elevator.

    ///

    /// \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().

    ///@{