1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/gomory_hu_test.cc	Thu Nov 05 15:50:01 2009 +0100
     1.3 @@ -0,0 +1,123 @@
     1.4 +#include <iostream>
     1.5 +
     1.6 +#include "test_tools.h"
     1.7 +#include <lemon/smart_graph.h>
     1.8 +#include <lemon/concepts/graph.h>
     1.9 +#include <lemon/concepts/maps.h>
    1.10 +#include <lemon/lgf_reader.h>
    1.11 +#include <lemon/gomory_hu.h>
    1.12 +#include <cstdlib>
    1.13 +
    1.14 +using namespace std;
    1.15 +using namespace lemon;
    1.16 +
    1.17 +typedef SmartGraph Graph;
    1.18 +
    1.19 +char test_lgf[] =
    1.20 +  "@nodes\n"
    1.21 +  "label\n"
    1.22 +  "0\n"
    1.23 +  "1\n"
    1.24 +  "2\n"
    1.25 +  "3\n"
    1.26 +  "4\n"
    1.27 +  "@arcs\n"
    1.28 +  "     label capacity\n"
    1.29 +  "0 1  0     1\n"
    1.30 +  "1 2  1     1\n"
    1.31 +  "2 3  2     1\n"
    1.32 +  "0 3  4     5\n"
    1.33 +  "0 3  5     10\n"
    1.34 +  "0 3  6     7\n"
    1.35 +  "4 2  7     1\n"
    1.36 +  "@attributes\n"
    1.37 +  "source 0\n"
    1.38 +  "target 3\n";
    1.39 +  
    1.40 +void checkGomoryHuCompile()
    1.41 +{
    1.42 +  typedef int Value;
    1.43 +  typedef concepts::Graph Graph;
    1.44 +
    1.45 +  typedef Graph::Node Node;
    1.46 +  typedef Graph::Edge Edge;
    1.47 +  typedef concepts::ReadMap<Edge, Value> CapMap;
    1.48 +  typedef concepts::ReadWriteMap<Node, bool> CutMap;
    1.49 +
    1.50 +  Graph g;
    1.51 +  Node n;
    1.52 +  CapMap cap;
    1.53 +  CutMap cut;
    1.54 +  Value v;
    1.55 +  int d;
    1.56 +
    1.57 +  GomoryHu<Graph, CapMap> gh_test(g, cap);
    1.58 +  const GomoryHu<Graph, CapMap>&
    1.59 +    const_gh_test = gh_test;
    1.60 +
    1.61 +  gh_test.run();
    1.62 +
    1.63 +  n = const_gh_test.predNode(n);
    1.64 +  v = const_gh_test.predValue(n);
    1.65 +  d = const_gh_test.rootDist(n);
    1.66 +  v = const_gh_test.minCutValue(n, n);
    1.67 +  v = const_gh_test.minCutMap(n, n, cut);
    1.68 +}
    1.69 +
    1.70 +GRAPH_TYPEDEFS(Graph);
    1.71 +typedef Graph::EdgeMap<int> IntEdgeMap;
    1.72 +typedef Graph::NodeMap<bool> BoolNodeMap;
    1.73 +
    1.74 +int cutValue(const Graph& graph, const BoolNodeMap& cut,
    1.75 +	     const IntEdgeMap& capacity) {
    1.76 +
    1.77 +  int sum = 0;
    1.78 +  for (EdgeIt e(graph); e != INVALID; ++e) {
    1.79 +    Node s = graph.u(e);
    1.80 +    Node t = graph.v(e);
    1.81 +
    1.82 +    if (cut[s] != cut[t]) {
    1.83 +      sum += capacity[e];
    1.84 +    }
    1.85 +  }
    1.86 +  return sum;
    1.87 +}
    1.88 +
    1.89 +
    1.90 +int main() {
    1.91 +  Graph graph;
    1.92 +  IntEdgeMap capacity(graph);
    1.93 +
    1.94 +  std::istringstream input(test_lgf);
    1.95 +  GraphReader<Graph>(graph, input).
    1.96 +    edgeMap("capacity", capacity).run();
    1.97 +
    1.98 +  GomoryHu<Graph> ght(graph, capacity);
    1.99 +  ght.run();
   1.100 +
   1.101 +  for (NodeIt u(graph); u != INVALID; ++u) {
   1.102 +    for (NodeIt v(graph); v != u; ++v) {
   1.103 +      Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
   1.104 +      pf.runMinCut();
   1.105 +      BoolNodeMap cm(graph);
   1.106 +      ght.minCutMap(u, v, cm);
   1.107 +      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
   1.108 +      check(cm[u] != cm[v], "Wrong cut 2");
   1.109 +      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
   1.110 +
   1.111 +      int sum=0;
   1.112 +      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
   1.113 +        sum+=capacity[a]; 
   1.114 +      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
   1.115 +
   1.116 +      sum=0;
   1.117 +      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
   1.118 +        sum++;
   1.119 +      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
   1.120 +        sum++;
   1.121 +      check(sum == countNodes(graph), "Problem with MinCutNodeIt");
   1.122 +    }
   1.123 +  }
   1.124 +  
   1.125 +  return 0;
   1.126 +}