RhodeCode

EXTRA_DIST += \

	lemon/lemon.pc.in \

	lemon/CMakeLists.txt

pkgconfig_DATA += lemon/lemon.pc

lib_LTLIBRARIES += lemon/libemon.la

lemon_libemon_la_SOURCES = \

	lemon/arg_parser.cc \

	lemon/base.cc \

	lemon/color.cc \

	lemon/lp_base.cc \

	lemon/lp_skeleton.cc \

        lemon/random.cc \

	lemon/bits/windows.cc

lemon_libemon_la_CXXFLAGS = \

	$(GLPK_CFLAGS) \

	$(CPLEX_CFLAGS) \

	$(SOPLEX_CXXFLAGS) \

	$(CLP_CXXFLAGS)

lemon_libemon_la_LDFLAGS = \

	$(GLPK_LIBS) \

	$(CPLEX_LIBS) \

	$(SOPLEX_LIBS) \

	$(CLP_LIBS)

if HAVE_GLPK

lemon_libemon_la_SOURCES += lemon/glpk.cc

endif

if HAVE_CPLEX

lemon_libemon_la_SOURCES += lemon/cplex.cc

endif

if HAVE_SOPLEX

lemon_libemon_la_SOURCES += lemon/soplex.cc

endif

if HAVE_CLP

lemon_libemon_la_SOURCES += lemon/clp.cc

endif

lemon_HEADERS += \

	lemon/adaptors.h \

	lemon/arg_parser.h \

	lemon/assert.h \

	lemon/bfs.h \

	lemon/bin_heap.h \

	lemon/circulation.h \

	lemon/clp.h \

	lemon/color.h \

	lemon/concept_check.h \

	lemon/connectivity.h \

	lemon/counter.h \

	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 \

	lemon/maps.h \

	lemon/math.h \

	lemon/max_matching.h \

	lemon/min_cost_arborescence.h \

	lemon/nauty_reader.h \

	lemon/path.h \

	lemon/preflow.h \

	lemon/radix_sort.h \

	lemon/random.h \

	lemon/smart_graph.h \

	lemon/soplex.h \

	lemon/suurballe.h \

	lemon/time_measure.h \

	lemon/tolerance.h \

	lemon/unionfind.h \

	lemon/bits/windows.h

bits_HEADERS += \

	lemon/bits/alteration_notifier.h \

	lemon/bits/array_map.h \

	lemon/bits/base_extender.h \

	lemon/bits/bezier.h \

	lemon/bits/default_map.h \

	lemon/bits/edge_set_extender.h \

	lemon/bits/enable_if.h \

	lemon/bits/graph_adaptor_extender.h \

	lemon/bits/graph_extender.h \

	lemon/bits/map_extender.h \

	lemon/bits/path_dump.h \

	lemon/bits/solver_bits.h \

	lemon/bits/traits.h \

	lemon/bits/variant.h \

	lemon/bits/vector_map.h

concept_HEADERS += \

	lemon/concepts/digraph.h \

	lemon/concepts/graph.h \

	lemon/concepts/graph_components.h \

	lemon/concepts/heap.h \

	lemon/concepts/maps.h \

	lemon/concepts/path.h

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

#define LEMON_GOMORY_HU_TREE_H

#include <limits>

#include <lemon/core.h>

#include <lemon/preflow.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

/// \ingroup min_cut

/// \file 

/// \brief Gomory-Hu cut tree in graphs.

namespace lemon {

  /// \ingroup min_cut

  ///

  /// \brief Gomory-Hu cut tree algorithm

  ///

  /// The Gomory-Hu tree is a tree on the node set of the graph, but it

  /// may contain edges which are not in the original digraph. It has the

  /// property that the minimum capacity edge of the path between two nodes 

  /// in this tree has the same weight as the minimum cut in the digraph

  /// between these nodes. Moreover the components obtained by removing

  /// this edge from the tree determine the corresponding minimum cut.

  ///

  /// Therefore once this tree is computed, the minimum cut between any pair

  /// of nodes can easily be obtained.

  /// 

  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with

  /// the \ref Preflow algorithm), therefore the algorithm has

  /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a

  /// rooted Gomory-Hu tree, its structure and the weights can be obtained

  /// by \c predNode(), \c predValue() and \c rootDist().

  /// 

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

    const Graph& _graph;

    const Capacity& _capacity;

    Node _root;

    typename Graph::template NodeMap<Node>* _pred;

    typename Graph::template NodeMap<Value>* _weight;

    typename Graph::template NodeMap<int>* _order;

    void createStructures() {

      if (!_pred) {

	_pred = new typename Graph::template NodeMap<Node>(_graph);

      }

      if (!_weight) {

	_weight = new typename Graph::template NodeMap<Value>(_graph);

      }

      if (!_order) {

	_order = new typename Graph::template NodeMap<int>(_graph);

      }

    }

    void destroyStructures() {

      if (_pred) {

	delete _pred;

      }

      if (_weight) {

	delete _weight;

      }

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

	_pred->set(n, _root);

	_order->set(n, -1);

      }

      _pred->set(_root, INVALID);

      _weight->set(_root, std::numeric_limits<Value>::max()); 

    }

    // \brief Start the algorithm

    //

    // This function starts the algorithm.

    //

    // \pre \ref init() must be called before using this function.

    //

    void start() {

      Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);

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

	if (n == _root) continue;

	Node pn = (*_pred)[n];

	fa.source(n);

	fa.target(pn);

	fa.runMinCut();

	_weight->set(n, fa.flowValue());

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

	  if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {

	    _pred->set(nn, n);

	  }

	}

	if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {

	  _pred->set(n, (*_pred)[pn]);

	  _pred->set(pn, n);

	  _weight->set(n, (*_weight)[pn]);

	  _weight->set(pn, fa.flowValue());	

	}

      }

      _order->set(_root, 0);

      int index = 1;

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

	std::vector<Node> st;

	Node nn = n;

	while ((*_order)[nn] == -1) {

	  st.push_back(nn);

	  nn = (*_pred)[nn];

	}

	while (!st.empty()) {

	  _order->set(st.back(), index++);

	  st.pop_back();

	}

      }

    }

    ///\name Execution Control

    ///@{

    /// \brief Run the Gomory-Hu algorithm.

    ///

    /// This function runs the Gomory-Hu algorithm.

    void run() {

      init();

      start();

    }

    /// @}

    ///\name Query Functions

    ///The results of the algorithm can be obtained using these

    ///functions.\n

    ///The \ref run() "run()" should be called before using them.\n

    ///See also MinCutNodeIt and MinCutEdgeIt

    ///@{

    /// \brief Return the predecessor node in the Gomory-Hu tree.

    ///

    /// This function returns the predecessor node in the Gomory-Hu tree.

    /// If the node is

    /// the root of the Gomory-Hu tree, then it returns \c INVALID.

    Node predNode(const Node& node) {

      return (*_pred)[node];

    }

    /// \brief Return the distance from the root node in the Gomory-Hu tree.

    ///

    /// This function returns the distance of \c node from the root node

    /// in the Gomory-Hu tree.

    int rootDist(const Node& node) {

      return (*_order)[node];

    }

    /// \brief Return the weight of the predecessor edge in the

    /// Gomory-Hu tree.

    ///

    /// This function returns the weight of the predecessor edge in the

    /// Gomory-Hu tree.  If the node is the root, the result is undefined.

    Value predValue(const Node& node) {

      return (*_weight)[node];

    }

    /// \brief Return the minimum cut value between two nodes

    ///

    /// This function returns the minimum cut value between two nodes. The

    /// algorithm finds the nearest common ancestor in the Gomory-Hu

    /// tree and calculates the minimum weight arc on the paths to

    /// the ancestor.

    Value minCutValue(const Node& s, const Node& t) const {

      Node sn = s, tn = t;

      Value value = std::numeric_limits<Value>::max();

      while (sn != tn) {

	if ((*_order)[sn] < (*_order)[tn]) {

	  if ((*_weight)[tn] <= value) value = (*_weight)[tn];

	  tn = (*_pred)[tn];

	} else {

	  if ((*_weight)[sn] <= value) value = (*_weight)[sn];

	  sn = (*_pred)[sn];

	}

      }

      return value;

    }

    /// \brief Return the minimum cut between two nodes

    ///

    /// This function returns the minimum cut between the nodes \c s and \c t

    /// the \r cutMap parameter by setting the nodes in the component of

    /// \c \s to true and the other nodes to false.

    ///

    /// The \c cutMap should be \ref concepts::ReadWriteMap

    /// "ReadWriteMap".

    ///

    /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt

    template <typename CutMap>

    Value minCutMap(const Node& s, ///< Base node

                    const Node& t,

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

                    CutMap& cutMap

                    ///< The cut will be return in this map.

                    /// It must be a \c bool \ref concepts::ReadWriteMap

                    /// "ReadWriteMap" on the graph nodes.

                    ) const {

      Node sn = s, tn = t;

      bool s_root=false;

      Node rn = INVALID;

      Value value = std::numeric_limits<Value>::max();

      while (sn != tn) {

	if ((*_order)[sn] < (*_order)[tn]) {

	  if ((*_weight)[tn] <= value) {

	    rn = tn;

            s_root = false;

	    value = (*_weight)[tn];

	  }

	  tn = (*_pred)[tn];

	} else {

	  if ((*_weight)[sn] <= value) {

	    rn = sn;

            s_root = true;

	    value = (*_weight)[sn];

	  }

	  sn = (*_pred)[sn];

	}

      }

      typename Graph::template NodeMap<bool> reached(_graph, false);

      reached.set(_root, true);

      cutMap.set(_root, !s_root);

      reached.set(rn, true);

      cutMap.set(rn, s_root);

      std::vector<Node> st;

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

	st.clear();

        Node nn = n;

	while (!reached[nn]) {

	  st.push_back(nn);

	  nn = (*_pred)[nn];

	}

	while (!st.empty()) {

	  cutMap.set(st.back(), cutMap[nn]);

	  st.pop_back();

	}

      }

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

                   /// \endcode

                   /// and

                   /// \code

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

                   /// \endcode

                   /// does not necessarily give the same set of nodes.

                   /// However it is ensured that

                   /// \code

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

                   /// \endcode

                   /// and

                   /// \code

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

                   /// \endcode

                   /// together list each node exactly once.

                   )

        : _side(side), _cut(gomory._graph)

      {

        gomory.minCutMap(s,t,_cut);

        for(_node_it=typename Graph::NodeIt(gomory._graph);

            _node_it!=INVALID && _cut[_node_it]!=_side;

            ++_node_it) {}

      }

      /// Conversion to Node

      /// Conversion to Node

      ///

      operator typename Graph::Node() const

      {

        return _node_it;

      }

      bool operator==(Invalid) { return _node_it==INVALID; }

      bool operator!=(Invalid) { return _node_it!=INVALID; }

      /// Next node

      /// Next node

      ///

      MinCutNodeIt &operator++()

      {

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

        return *this;

      }

      /// Postfix incrementation

      /// Postfix incrementation

      ///

      /// \warning This incrementation

      /// returns a \c Node, not a \ref MinCutNodeIt, as one may

      /// expect.

      typename Graph::Node operator++(int)

      {

        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.

                   )

        : _graph(gomory._graph), _cut(_graph)

      {

        gomory.minCutMap(s,t,_cut);

        if(!side)

          for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)

            _cut[n]=!_cut[n];

        for(_node_it=typename Graph::NodeIt(_graph);

            _node_it!=INVALID && !_cut[_node_it];

            ++_node_it) {}

        _arc_it = _node_it!=INVALID ?

          typename Graph::OutArcIt(_graph,_node_it) : INVALID;

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

          }

        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();

      }

      /// Conversion to Arc

      /// Conversion to Arc

      ///

      operator typename Graph::Arc() const

      {

        return _arc_it;

      }

      /// Conversion to Edge

      /// Conversion to Edge

      ///

      operator typename Graph::Edge() const

      {

        return _arc_it;

      }

      bool operator==(Invalid) { return _node_it==INVALID; }

      bool operator!=(Invalid) { return _node_it!=INVALID; }

      /// Next edge

      /// Next edge

      ///

      MinCutEdgeIt &operator++()

      {

        step();

        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();

        return *this;

      }

      /// Postfix incrementation

      /// Postfix incrementation

      ///

      /// \warning This incrementation

      /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may

      /// expect.

      typename Graph::Arc operator++(int)

      {

        typename Graph::Arc e=*this;

        ++(*this);

        return e;

      }

    };

  };

}

#endif

#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"

  "2\n"

  "3\n"

  "4\n"

  "@arcs\n"

  "     label capacity\n"

  "0 1  0     1\n"

  "1 2  1     1\n"

  "2 3  2     1\n"

  "0 3  4     5\n"

  "0 3  5     10\n"

  "0 3  6     7\n"

  "4 2  7     1\n"

  "@attributes\n"

  "source 0\n"

  "target 3\n";

GRAPH_TYPEDEFS(Graph);

typedef Graph::EdgeMap<int> IntEdgeMap;

typedef Graph::NodeMap<bool> BoolNodeMap;

int cutValue(const Graph& graph, const BoolNodeMap& cut,

	     const IntEdgeMap& capacity) {

  int sum = 0;

  for (EdgeIt e(graph); e != INVALID; ++e) {

    Node s = graph.u(e);

    Node t = graph.v(e);

    if (cut[s] != cut[t]) {

      sum += capacity[e];

    }

  }

  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;

}