RhodeCode

INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})

LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)

SET(TESTS

  bfs_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

  maps_test

  max_matching_test

  random_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 += \

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

	test/graph_copy_test \

	test/graph_test \

	test/graph_utils_test \

	test/heap_test \

	test/kruskal_test \

        test/maps_test \

	test/max_matching_test \

        test/path_test \

        test/preflow_test \

        test/suurballe_test \

        test/test_tools_fail \

        test/test_tools_pass \

        test/time_measure_test \

	test/unionfind_test

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_adaptor_test_SOURCES = test/graph_adaptor_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_maps_test_SOURCES = test/maps_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_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-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.

 *

 */

#include "test_tools.h"

#include <lemon/smart_graph.h>

#include <lemon/preflow.h>

#include <lemon/concepts/digraph.h>

#include <lemon/concepts/maps.h>

#include <lemon/lgf_reader.h>

#include <lemon/elevator.h>

using namespace lemon;

void checkPreflowCompile()

{

  typedef int VType;

  typedef concepts::Digraph Digraph;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  typedef concepts::ReadMap<Arc,VType> CapMap;

  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;

  typedef concepts::WriteMap<Node,bool> CutMap;

  typedef Elevator<Digraph, Digraph::Node> Elev;

  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;

  Digraph g;

  Node n;

  Arc e;

  CapMap cap;

  FlowMap flow;

  CutMap cut;

  Preflow<Digraph, CapMap>

    ::SetFlowMap<FlowMap>

    ::SetElevator<Elev>

    ::SetStandardElevator<LinkedElev>

    ::Create preflow_test(g,cap,n,n);

  preflow_test.capacityMap(cap);

  flow = preflow_test.flowMap();

  preflow_test.flowMap(flow);

  preflow_test.source(n);

  preflow_test.target(n);

  preflow_test.init();

  preflow_test.init(cap);

  preflow_test.startFirstPhase();

  preflow_test.startSecondPhase();

  preflow_test.run();

  preflow_test.runMinCut();

  preflow_test.flowValue();

  preflow_test.minCut(n);

  preflow_test.minCutMap(cut);

  preflow_test.flow(e);

}

int cutValue (const SmartDigraph& g,

              const SmartDigraph::NodeMap<bool>& cut,

              const SmartDigraph::ArcMap<int>& cap) {

  int c=0;

  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {

    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];

  }

  return c;

}

bool checkFlow(const SmartDigraph& g,

               const SmartDigraph::ArcMap<int>& flow,

               const SmartDigraph::ArcMap<int>& cap,

               SmartDigraph::Node s, SmartDigraph::Node t) {

  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {

    if (flow[e] < 0 || flow[e] > cap[e]) return false;

  }

  for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {

    if (n == s || n == t) continue;

    int sum = 0;

    for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {

      sum += flow[e];

    }

    for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {

      sum -= flow[e];

    }

    if (sum != 0) return false;

  }

  return true;

}

int main() {

  typedef SmartDigraph Digraph;

  typedef Digraph::Node Node;

  typedef Digraph::NodeIt NodeIt;

  typedef Digraph::ArcIt ArcIt;

  typedef Digraph::ArcMap<int> CapMap;

  typedef Digraph::ArcMap<int> FlowMap;

  typedef Digraph::NodeMap<bool> CutMap;

  typedef Preflow<Digraph, CapMap> PType;

  Digraph g;

  Node s, t;

  CapMap cap(g);

    arcMap("capacity", cap).

    node("source",s).

    node("target",t).

    run();

  PType preflow_test(g, cap, s, t);

  preflow_test.run();

  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),

        "The flow is not feasible.");

  CutMap min_cut(g);

  preflow_test.minCutMap(min_cut);

  int min_cut_value=cutValue(g,min_cut,cap);

  check(preflow_test.flowValue() == min_cut_value,

        "The max flow value is not equal to the three min cut values.");

  FlowMap flow(g);

  for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];

  int flow_value=preflow_test.flowValue();

  for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];

  preflow_test.init(flow);

  preflow_test.startFirstPhase();

  CutMap min_cut1(g);

  preflow_test.minCutMap(min_cut1);

  min_cut_value=cutValue(g,min_cut1,cap);

  check(preflow_test.flowValue() == min_cut_value &&

        min_cut_value == 2*flow_value,

        "The max flow value or the min cut value is wrong.");

  preflow_test.startSecondPhase();

  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),

        "The flow is not feasible.");

  CutMap min_cut2(g);

  preflow_test.minCutMap(min_cut2);

  min_cut_value=cutValue(g,min_cut2,cap);

  check(preflow_test.flowValue() == min_cut_value &&

        min_cut_value == 2*flow_value,

        "The max flow value or the three min cut values were not doubled");

  preflow_test.flowMap(flow);

  NodeIt tmp1(g,s);

  ++tmp1;

  if ( tmp1 != INVALID ) s=tmp1;

  NodeIt tmp2(g,t);

  ++tmp2;

  if ( tmp2 != INVALID ) t=tmp2;

  preflow_test.source(s);

  preflow_test.target(t);

  preflow_test.run();

  CutMap min_cut3(g);

  preflow_test.minCutMap(min_cut3);

  min_cut_value=cutValue(g,min_cut3,cap);

  check(preflow_test.flowValue() == min_cut_value,

        "The max flow value or the three min cut values are incorrect.");

  return 0;

}

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

 *

 */

#include <iostream>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/path.h>

#include <lemon/suurballe.h>

#include "test_tools.h"

using namespace lemon;

// Check the feasibility of the flow

template <typename Digraph, typename FlowMap>

bool checkFlow( const Digraph& gr, const FlowMap& flow, 

                typename Digraph::Node s, typename Digraph::Node t,

                int value )

{

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  for (ArcIt e(gr); e != INVALID; ++e)

    if (!(flow[e] == 0 || flow[e] == 1)) return false;

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

    int sum = 0;

    for (OutArcIt e(gr, n); e != INVALID; ++e)

      sum += flow[e];

    for (InArcIt e(gr, n); e != INVALID; ++e)

      sum -= flow[e];

    if (n == s && sum != value) return false;

    if (n == t && sum != -value) return false;

    if (n != s && n != t && sum != 0) return false;

  }

  return true;

}

// Check the optimalitiy of the flow

template < typename Digraph, typename CostMap, 

           typename FlowMap, typename PotentialMap >

bool checkOptimality( const Digraph& gr, const CostMap& cost,

                      const FlowMap& flow, const PotentialMap& pi )

{

  // Check the "Complementary Slackness" optimality condition

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  bool opt = true;

  for (ArcIt e(gr); e != INVALID; ++e) {

    typename CostMap::Value red_cost =

      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];

    opt = (flow[e] == 0 && red_cost >= 0) ||

          (flow[e] == 1 && red_cost <= 0);

    if (!opt) break;

  }

  return opt;

}

// Check a path

template <typename Digraph, typename Path>

bool checkPath( const Digraph& gr, const Path& path,

                typename Digraph::Node s, typename Digraph::Node t)

{

  // Check the "Complementary Slackness" optimality condition

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  Node n = s;

  for (int i = 0; i < path.length(); ++i) {

    if (gr.source(path.nth(i)) != n) return false;

    n = gr.target(path.nth(i));

  }

  return n == t;

}

int main()

{

  DIGRAPH_TYPEDEFS(ListDigraph);

  // Read the test digraph

  ListDigraph digraph;

  ListDigraph::ArcMap<int> length(digraph);

  Node source, target;

  DigraphReader<ListDigraph>(digraph, input).

    arcMap("cost", length).

    node("source", source).

    node("target", target).

    run();

  // Find 2 paths

  {

    Suurballe<ListDigraph> suurballe(digraph, length, source, target);

    check(suurballe.run(2) == 2, "Wrong number of paths");

    check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),

          "The flow is not feasible");

    check(suurballe.totalLength() == 510, "The flow is not optimal");

    check(checkOptimality(digraph, length, suurballe.flowMap(), 

                          suurballe.potentialMap()),

          "Wrong potentials");

    for (int i = 0; i < suurballe.pathNum(); ++i)

      check(checkPath(digraph, suurballe.path(i), source, target),

            "Wrong path");

  }

  // Find 3 paths

  {

    Suurballe<ListDigraph> suurballe(digraph, length, source, target);

    check(suurballe.run(3) == 3, "Wrong number of paths");

    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),

          "The flow is not feasible");

    check(suurballe.totalLength() == 1040, "The flow is not optimal");

    check(checkOptimality(digraph, length, suurballe.flowMap(), 

                          suurballe.potentialMap()),

          "Wrong potentials");

    for (int i = 0; i < suurballe.pathNum(); ++i)

      check(checkPath(digraph, suurballe.path(i), source, target),

            "Wrong path");

  }

  // Find 5 paths (only 3 can be found)

  {

    Suurballe<ListDigraph> suurballe(digraph, length, source, target);

    check(suurballe.run(5) == 3, "Wrong number of paths");

    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),

          "The flow is not feasible");

    check(suurballe.totalLength() == 1040, "The flow is not optimal");

    check(checkOptimality(digraph, length, suurballe.flowMap(), 

                          suurballe.potentialMap()),

          "Wrong potentials");

    for (int i = 0; i < suurballe.pathNum(); ++i)

      check(checkPath(digraph, suurballe.path(i), source, target),

            "Wrong path");

  }

  return 0;

}