RhodeCode

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

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.

*/

/**

@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

        delete _dist;

        local_dist=false;

      }

      _dist = &m;

      return *this;

    }

  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.

    ///

    ///Initializes the internal data structures.

    void init()

    {

      create_maps();

      _queue.resize(countNodes(*G));

        delete _reached;

        local_reached = false;

      }

      _reached = &m;

      return *this;

    }

  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.

    ///

    /// Initializes the internal data structures.

    void init() {

      create_maps();

      _list.resize(countNodes(*_digraph));

      _list_front = _list_back = -1;

    /// nodes. 

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

    typedef SM SupplyMap;

    /// \brief The type of the flow and supply values.

    typedef typename SupplyMap::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 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.

    static FlowMap* createFlowMap(const Digraph& digraph) {

      return new FlowMap(digraph);

    }

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

    /// \param max_level The maximum level of the elevator.

    static Elevator* createElevator(const Digraph& digraph, int max_level) {

      return new Elevator(digraph, max_level);

    }

    /// \brief The tolerance used by the algorithm

      return *this;

    }

    /// \brief Returns a const reference to the tolerance.

    ///

    /// Returns a const reference to the tolerance.

    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.

    /// Initializes the internal data structures and sets all flow values

    /// to the lower bound.

    void init()

    {

      LEMON_DEBUG(checkBoundMaps(),

        "Upper bounds must be greater or equal to the lower bounds");

        delete _dist;

        local_dist=false;

      }

      _dist = &m;

      return *this;

    }

  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.

    ///@{

    ///\brief Initializes the internal data structures.

    ///

    ///Initializes the internal data structures.

    void init()

    {

      create_maps();

        delete _reached;

        local_reached=false;

      }

      _reached = &m;

      return *this;

    }

  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.

    /// @{

    /// \brief Initializes the internal data structures.

    ///

    /// Initializes the internal data structures.

    void init() {

      create_maps();

      _stack.resize(countNodes(*_digraph));

    void finalizeNodeData(Node v,Value dst)

    {

      _processed->set(v,true);

      _dist->set(v, dst);

    }

  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.

    ///

    ///Initializes the internal data structures.

    void init()

    {

      create_maps();

      _heap->clear();

    friend class MinCutNodeIt;

    /// Iterate on the nodes of a minimum cut

    /// This iterator class lists the nodes of a minimum cut found by

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

    public:

      /// Constructor

      /// Constructor.

      ///

      MinCutNodeIt(GomoryHu const &gomory,

    friend class MinCutEdgeIt;

    /// Iterate on the edges of a minimum cut

    /// This iterator class lists the edges of a minimum cut found by

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

    {

      bool _side;

      const Graph &_graph;

      typename Graph::NodeIt _node_it;

      typename Graph::OutArcIt _arc_it;

      typename Graph::template NodeMap<bool> _cut;

      void step()

    MinCostArborescence& predMap(PredMap& m) {

      if (local_pred) {

        delete _pred;

      }

      local_pred = false;

      _pred = &m;

      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.

    ///@{

    /// \brief Initializes the internal data structures.

    ///

    /// Initializes the internal data structures.

    ///

    void init() {

      createStructures();

    ///

    /// The type of the map that stores the arc capacities.

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

    typedef CAP CapacityMap;

    /// \brief The type of the flow values.

    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.

    static FlowMap* createFlowMap(const Digraph& digraph) {

      return new FlowMap(digraph);

    }

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

    /// \param max_level The maximum level of the elevator.

    static Elevator* createElevator(const Digraph& digraph, int max_level) {

      return new Elevator(digraph, max_level);

    }

    /// \brief The tolerance used by the algorithm

    }

    /// \brief Returns a const reference to the tolerance.

    ///

    /// Returns a const reference to the tolerance.

    const Tolerance& tolerance() const {

      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.

    ///

    /// Initializes the internal data structures and sets the initial

    /// flow to zero on each arc.

    void init() {

      createStructures();

      _phase = true;