RhodeCode

    ///

    /// Constructor of the adaptor.

    Orienter(Graph& graph, DirectionMap& direction) {

      setGraph(graph);

      setDirectionMap(direction);

    }

    /// \brief Reverses the given arc

    ///

    /// This function reverses the given arc.

    /// It is done by simply negate the assigned value of \c a

    /// in the direction map.

    void reverseArc(const Arc& a) {

      Parent::reverseArc(a);

    }

  };

  /// \brief Returns a read-only Orienter adaptor

  ///

  /// This function just returns a read-only \ref Orienter adaptor.

  /// \ingroup graph_adaptors

  /// \relates Orienter

  template<typename GR, typename DM>

  Orienter<const GR, DM>

  orienter(const GR& graph, DM& direction_map) {

    return Orienter<const GR, DM>(graph, direction_map);

  }

  template<typename GR, typename DM>

  Orienter<const GR, const DM>

  orienter(const GR& graph, const DM& direction_map) {

    return Orienter<const GR, const DM>(graph, direction_map);

  }

  namespace _adaptor_bits {

    template<typename Digraph,

             typename CapacityMap,

             typename FlowMap,

             typename Tolerance>

    class ResForwardFilter {

    public:

      typedef typename Digraph::Arc Key;

      typedef bool Value;

    private:

      const CapacityMap* _capacity;

      const FlowMap* _flow;

      Tolerance _tolerance;

    public:

      ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,

                       const Tolerance& tolerance = Tolerance())

        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }

      bool operator[](const typename Digraph::Arc& a) const {

        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);

      }

    };

    template<typename Digraph,

             typename CapacityMap,

             typename FlowMap,

             typename Tolerance>

    class ResBackwardFilter {

    public:

      typedef typename Digraph::Arc Key;

      typedef bool Value;

    private:

      const CapacityMap* _capacity;

      const FlowMap* _flow;

      Tolerance _tolerance;

    public:

      ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,

                        const Tolerance& tolerance = Tolerance())

        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }

      bool operator[](const typename Digraph::Arc& a) const {

        return _tolerance.positive((*_flow)[a]);

      }

    };

  }

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for composing the residual digraph for directed

  /// flow and circulation problems.

  ///

  /// This adaptor implements a digraph structure with node set \f$ V \f$

  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,

  /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and

  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so

  /// called residual digraph.

  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,

  /// multiplicities are counted, i.e. the adaptor has exactly

  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel

  /// arcs).

  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.

  ///

  /// \tparam GR The type of the adapted digraph.

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

  /// It is implicitly \c const.

  /// \tparam CM The type of the capacity map.

  /// It must be an arc map of some numerical type, which defines

  /// the capacities in the flow problem. It is implicitly \c const.

  /// The default type is

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

  /// \tparam FM The type of the flow map.

  /// It must be an arc map of some numerical type, which defines

  /// the flow values in the flow problem. The default type is \c CM.

  /// \tparam TL The tolerance type for handling inexact computation.

  /// The default tolerance type depends on the value type of the

  /// capacity map.

  ///

  /// \note This adaptor is implemented using Undirector and FilterArcs

  /// adaptors.

  ///

  /// \note The \c Node type of this adaptor and the adapted digraph are

  /// convertible to each other, moreover the \c Arc type of the adaptor

  /// is convertible to the \c Arc type of the adapted digraph.

#ifdef DOXYGEN

  template<typename GR, typename CM, typename FM, typename TL>

#else

  template<typename GR,

           typename CM = typename GR::template ArcMap<int>,

           typename FM = CM,

           typename TL = Tolerance<typename CM::Value> >

    public FilterArcs<

      Undirector<const GR>,

      typename Undirector<const GR>::template CombinedArcMap<

        _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,

        _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >

#endif

  {

  public:

    /// The type of the underlying digraph.

    typedef GR Digraph;

    /// The type of the capacity map.

    typedef CM CapacityMap;

    /// The type of the flow map.

    typedef FM FlowMap;

    /// The tolerance type.

    typedef TL Tolerance;

    typedef typename CapacityMap::Value Value;

  protected:

    typedef Undirector<const Digraph> Undirected;

    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,

                                            FlowMap, Tolerance> ForwardFilter;

    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,

                                             FlowMap, Tolerance> BackwardFilter;

    typedef typename Undirected::

      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;

    typedef FilterArcs<Undirected, ArcFilter> Parent;

    const CapacityMap* _capacity;

    FlowMap* _flow;

    Undirected _graph;

    ForwardFilter _forward_filter;

    BackwardFilter _backward_filter;

    ArcFilter _arc_filter;

  public:

    /// \brief Constructor

    ///

    /// Constructor of the residual digraph adaptor. The parameters are the

    /// digraph, the capacity map, the flow map, and a tolerance object.

      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),

        _forward_filter(capacity, flow, tolerance),

        _backward_filter(capacity, flow, tolerance),

        _arc_filter(_forward_filter, _backward_filter)

    {

      Parent::setDigraph(_graph);

      Parent::setArcFilterMap(_arc_filter);

    }

    typedef typename Parent::Arc Arc;

    /// \brief Returns the residual capacity of the given arc.

    ///

    /// Returns the residual capacity of the given arc.

    Value residualCapacity(const Arc& a) const {

      if (Undirected::direction(a)) {

        return (*_capacity)[a] - (*_flow)[a];

      } else {

        return (*_flow)[a];

      }

    }

    /// \brief Augments on the given arc in the residual digraph.

    ///

    /// Augments on the given arc in the residual digraph. It increases

    /// or decreases the flow value on the original arc according to the

    /// direction of the residual arc.

    void augment(const Arc& a, const Value& v) const {

      if (Undirected::direction(a)) {

        _flow->set(a, (*_flow)[a] + v);

      } else {

        _flow->set(a, (*_flow)[a] - v);

      }

    }

    /// \brief Returns \c true if the given residual arc is a forward arc.

    ///

    /// Returns \c true if the given residual arc has the same orientation

    /// as the original arc, i.e. it is a so called forward arc.

    static bool forward(const Arc& a) {

      return Undirected::direction(a);

    }

    /// \brief Returns \c true if the given residual arc is a backward arc.

    ///

    /// Returns \c true if the given residual arc has the opposite orientation

    /// than the original arc, i.e. it is a so called backward arc.

    static bool backward(const Arc& a) {

      return !Undirected::direction(a);

    }

    /// \brief Returns the forward oriented residual arc.

    ///

    /// Returns the forward oriented residual arc related to the given

    /// arc of the underlying digraph.

    static Arc forward(const typename Digraph::Arc& a) {

      return Undirected::direct(a, true);

    }

    /// \brief Returns the backward oriented residual arc.

    ///

    /// Returns the backward oriented residual arc related to the given

    /// arc of the underlying digraph.

    static Arc backward(const typename Digraph::Arc& a) {

      return Undirected::direct(a, false);

    }

    /// \brief Residual capacity map.

    ///

    /// This map adaptor class can be used for obtaining the residual

    /// capacities as an arc map of the residual digraph.

    /// Its value type is inherited from the capacity map.

    class ResidualCapacity {

    protected:

      const Adaptor* _adaptor;

    public:

      /// The key type of the map

      typedef Arc Key;

      /// The value type of the map

      typedef typename CapacityMap::Value Value;

      /// Constructor

      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}

      /// Returns the value associated with the given residual arc

      Value operator[](const Arc& a) const {

        return _adaptor->residualCapacity(a);

      }

    };

    /// \brief Returns a residual capacity map

    ///

    /// This function just returns a residual capacity map.

    ResidualCapacity residualCapacity() const {

      return ResidualCapacity(*this);

    }

  };

  /// \brief Returns a (read-only) Residual adaptor

  ///

  /// This function just returns a (read-only) \ref Residual adaptor.

  /// \ingroup graph_adaptors

  /// \relates Residual

  template<typename GR, typename CM, typename FM>

  }

  template <typename _Digraph>

  class SplitNodesBase {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase<const _Digraph> Parent;

    typedef SplitNodesBase Adaptor;

    typedef typename Digraph::Node DigraphNode;

    typedef typename Digraph::Arc DigraphArc;

    class Node;

    class Arc;

  private:

    template <typename T> class NodeMapBase;

    template <typename T> class ArcMapBase;

  public:

    class Node : public DigraphNode {

      friend class SplitNodesBase;

      template <typename T> friend class NodeMapBase;

    private:

      bool _in;

      Node(DigraphNode node, bool in)

        : DigraphNode(node), _in(in) {}

    public:

      Node() {}

      Node(Invalid) : DigraphNode(INVALID), _in(true) {}

      bool operator==(const Node& node) const {

        return DigraphNode::operator==(node) && _in == node._in;

      }

      bool operator!=(const Node& node) const {

        return !(*this == node);

      }

      bool operator<(const Node& node) const {

        return DigraphNode::operator<(node) ||

          (DigraphNode::operator==(node) && _in < node._in);

      }

    };

    class Arc {

      friend class SplitNodesBase;

      template <typename T> friend class ArcMapBase;

    private:

      typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;

      explicit Arc(const DigraphArc& arc) : _item(arc) {}

      explicit Arc(const DigraphNode& node) : _item(node) {}

      ArcImpl _item;

    public:

      Arc() {}

      Arc(Invalid) : _item(DigraphArc(INVALID)) {}

      bool operator==(const Arc& arc) const {

        if (_item.firstState()) {

          if (arc._item.firstState()) {

            return _item.first() == arc._item.first();

          }

        } else {

          if (arc._item.secondState()) {

            return _item.second() == arc._item.second();

          }

        }

        return false;

      }

      bool operator!=(const Arc& arc) const {

        return !(*this == arc);

      }

      bool operator<(const Arc& arc) const {

        if (_item.firstState()) {

          if (arc._item.firstState()) {

            return _item.first() < arc._item.first();

          }

          return false;

        } else {

          if (arc._item.secondState()) {

            return _item.second() < arc._item.second();

          }

          return true;

        }

INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})

LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)

SET(TESTS

  bfs_test

  circulation_test

  counter_test

  dfs_test

  digraph_test

  dijkstra_test

  dim_test

  error_test

  graph_copy_test

  graph_test

  graph_utils_test

  hao_orlin_test

  heap_test

  kruskal_test

  lp_test

  mip_test

  maps_test

  max_matching_test

  radix_sort_test

  path_test

  preflow_test

  random_test

  suurballe_test

  time_measure_test

  unionfind_test)

FOREACH(TEST_NAME ${TESTS})

  ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)

  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)

  ADD_TEST(${TEST_NAME} ${TEST_NAME})

ENDFOREACH(TEST_NAME)

EXTRA_DIST += \

	test/CMakeLists.txt

noinst_HEADERS += \

	test/graph_test.h \

	test/test_tools.h

check_PROGRAMS += \

	test/bfs_test \

	test/circulation_test \

	test/counter_test \

	test/dfs_test \

	test/digraph_test \

	test/dijkstra_test \

	test/dim_test \

	test/error_test \

	test/graph_copy_test \

	test/graph_test \

	test/graph_utils_test \

	test/hao_orlin_test \

	test/heap_test \

	test/kruskal_test \

	test/maps_test \

	test/max_matching_test \

	test/path_test \

	test/preflow_test \

	test/radix_sort_test \

	test/random_test \

	test/suurballe_test \

	test/test_tools_fail \

	test/test_tools_pass \

	test/time_measure_test \

	test/unionfind_test

if HAVE_LP

check_PROGRAMS += test/lp_test

endif HAVE_LP

if HAVE_MIP

check_PROGRAMS += test/mip_test

endif HAVE_MIP

TESTS += $(check_PROGRAMS)

XFAIL_TESTS += test/test_tools_fail$(EXEEXT)

test_bfs_test_SOURCES = test/bfs_test.cc

test_circulation_test_SOURCES = test/circulation_test.cc

test_counter_test_SOURCES = test/counter_test.cc

test_dfs_test_SOURCES = test/dfs_test.cc

test_digraph_test_SOURCES = test/digraph_test.cc

test_dijkstra_test_SOURCES = test/dijkstra_test.cc

test_dim_test_SOURCES = test/dim_test.cc

test_error_test_SOURCES = test/error_test.cc

test_graph_copy_test_SOURCES = test/graph_copy_test.cc

test_graph_test_SOURCES = test/graph_test.cc

test_graph_utils_test_SOURCES = test/graph_utils_test.cc

test_heap_test_SOURCES = test/heap_test.cc

test_kruskal_test_SOURCES = test/kruskal_test.cc

test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc

test_lp_test_SOURCES = test/lp_test.cc

test_maps_test_SOURCES = test/maps_test.cc

test_mip_test_SOURCES = test/mip_test.cc

test_max_matching_test_SOURCES = test/max_matching_test.cc

test_path_test_SOURCES = test/path_test.cc

test_preflow_test_SOURCES = test/preflow_test.cc

test_radix_sort_test_SOURCES = test/radix_sort_test.cc

test_suurballe_test_SOURCES = test/suurballe_test.cc

test_random_test_SOURCES = test/random_test.cc

test_test_tools_fail_SOURCES = test/test_tools_fail.cc

test_test_tools_pass_SOURCES = test/test_tools_pass.cc

test_time_measure_test_SOURCES = test/time_measure_test.cc

test_unionfind_test_SOURCES = test/unionfind_test.cc

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

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

 *

 */

#include <lemon/bfs.h>

#include <lemon/path.h>

using namespace lemon;

void checkReverseDigraph() {

  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();

  typedef ListDigraph Digraph;

  typedef ReverseDigraph<Digraph> Adaptor;

  Digraph digraph;

  Adaptor adaptor(digraph);

  Digraph::Node n1 = digraph.addNode();

  Digraph::Node n2 = digraph.addNode();

  Digraph::Node n3 = digraph.addNode();

  Digraph::Arc a1 = digraph.addArc(n1, n2);

  Digraph::Arc a2 = digraph.addArc(n1, n3);

  Digraph::Arc a3 = digraph.addArc(n2, n3);

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 3);

  checkGraphConArcList(adaptor, 3);

  checkGraphOutArcList(adaptor, n1, 0);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 2);

  checkGraphInArcList(adaptor, n1, 2);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 0);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

    check(adaptor.source(a) == digraph.target(a), "Wrong reverse");

    check(adaptor.target(a) == digraph.source(a), "Wrong reverse");

  }

}

void checkSubDigraph() {

  typedef ListDigraph Digraph;

  typedef Digraph::NodeMap<bool> NodeFilter;

  typedef Digraph::ArcMap<bool> ArcFilter;

  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;

  Digraph digraph;

  NodeFilter node_filter(digraph);

  ArcFilter arc_filter(digraph);

  Adaptor adaptor(digraph, node_filter, arc_filter);

  Digraph::Node n1 = digraph.addNode();

  Digraph::Node n2 = digraph.addNode();

  Digraph::Arc a1 = digraph.addArc(n1, n2);

  Digraph::Arc a2 = digraph.addArc(n1, n3);

  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 3);

  checkGraphConArcList(adaptor, 3);

  checkGraphOutArcList(adaptor, n1, 2);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 0);

  checkGraphInArcList(adaptor, n1, 0);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 2);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 2);

  checkGraphConArcList(adaptor, 2);

  checkGraphOutArcList(adaptor, n1, 1);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 0);

  checkGraphInArcList(adaptor, n1, 0);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 1);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);