RhodeCode

	lemon/core.h \

	lemon/cplex.h \

	lemon/dfs.h \

	lemon/dijkstra.h \

	lemon/dim2.h \

	lemon/dimacs.h \

	lemon/edge_set.h \

	lemon/elevator.h \

	lemon/error.h \

	lemon/euler.h \

	lemon/full_graph.h \

	lemon/glpk.h \

	lemon/graph_to_eps.h \

	lemon/grid_graph.h \

	lemon/hypercube_graph.h \

	lemon/kruskal.h \

	lemon/hao_orlin.h \

	lemon/lgf_reader.h \

	lemon/lgf_writer.h \

	lemon/list_graph.h \

	lemon/lp.h \

	lemon/lp_base.h \

	lemon/lp_skeleton.h \

	lemon/list_graph.h \

  /// 

  /// The members \c minCutMap() and \c minCutValue() calculate

  /// the minimum cut and the minimum cut value between any two node

  /// in the digraph. You can also list (iterate on) the nodes and the

  /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.

  ///

  /// \tparam GR The undirected graph data structure the algorithm will run on

  /// \tparam CAP type of the EdgeMap describing the Edge capacities.

  /// it is typename GR::template EdgeMap<int> by default.

  template <typename GR,

	    typename CAP = typename GR::template EdgeMap<int>

            >

  public:

    /// The graph type

    typedef GR Graph;

    /// The type if the edge capacity map

    typedef CAP Capacity;

    /// The value type of capacities

    typedef typename Capacity::Value Value;

  private:

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

      if (_order) {

	delete _order;

      }

    }

  public:

    /// \brief Constructor

    ///

    /// Constructor

    /// \param graph The graph the algorithm will run on.

    /// \param capacity The capacity map.

      : _graph(graph), _capacity(capacity),

	_pred(0), _weight(0), _order(0) 

    {

      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();

    }

    /// \brief Destructor

    ///

    /// Destructor

      destroyStructures();

    }

    // \brief Initialize the internal data structures.

    //

    // This function initializes the internal data structures.

    //

    void init() {

      createStructures();

      _root = NodeIt(_graph);

      for (NodeIt n(_graph); n != INVALID; ++n) {

      }

      return value;

    }

    ///@}

    friend class MinCutNodeIt;

    /// Iterate on the nodes of a minimum cut

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

    ///

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

    /// \c t.

    /// \code

    /// gom.run();

    /// int sum=0;

    /// \endcode

    class MinCutNodeIt

    {

      bool _side;

      typename Graph::NodeIt _node_it;

      typename Graph::template NodeMap<bool> _cut;

    public:

      /// Constructor

      /// Constructor

      ///

                   ///  run() method

                   ///  before initializing this iterator

                   const Node& s, ///< Base node

                   const Node& t,

                   ///< The node you want to separate from Node s.

                   bool side=true

                   ///< If it is \c true (default) then the iterator lists

                   ///  the nodes of the component containing \c s,

                   ///  otherwise it lists the other component.

                   /// \note As the minimum cut is not always unique,

                   /// \code

                   /// MinCutNodeIt(gomory, s, t, true);

      {

        typename Graph::Node n=*this;

        ++(*this);

        return n;

      }

    };

    friend class MinCutEdgeIt;

    /// Iterate on the edges of a minimum cut

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

    ///

    /// 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 it is returned by

    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()

      {

        ++_arc_it;

        while(_node_it!=INVALID && _arc_it==INVALID)

          {

            for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}

            if(_node_it!=INVALID)

              _arc_it=typename Graph::OutArcIt(_graph,_node_it);

          }

      }

    public:

                   ///  run() method

                   ///  before initializing this iterator

                   const Node& s,  ///< Base node

                   const Node& t,

                   ///< The node you want to separate from Node s.

                   bool side=true

                   ///< If it is \c true (default) then the listed arcs

                   ///  will be oriented from the

                   ///  the nodes of the component containing \c s,

                   ///  otherwise they will be oriented in the opposite

                   ///  direction.

                   )

#include <iostream>

#include "test_tools.h"

#include <lemon/smart_graph.h>

#include <lemon/lgf_reader.h>

#include <cstdlib>

using namespace std;

using namespace lemon;

typedef SmartGraph Graph;

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  return sum;

}

int main() {

  Graph graph;

  IntEdgeMap capacity(graph);

  std::istringstream input(test_lgf);

  GraphReader<Graph>(graph, input).

    edgeMap("capacity", capacity).run();

  ght.init();

  ght.run();

  for (NodeIt u(graph); u != INVALID; ++u) {

    for (NodeIt v(graph); v != u; ++v) {

      Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);

      pf.runMinCut();

      BoolNodeMap cm(graph);

      ght.minCutMap(u, v, cm);

      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");

      check(cm[u] != cm[v], "Wrong cut 3");

      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");

      int sum=0;

        sum+=capacity[a]; 

      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");

      sum=0;

        sum++;

        sum++;

      check(sum == countNodes(graph), "Problem with MinCutNodeIt");

    }

  }

  return 0;

}