Files @ r544:ccd2d3a3001e

Location: LEMON/LEMON-main/test/gomory_hu_test.cc

Load file history 
r544:ccd2d3a3001e
2.0 KiB
text/x-c++src
Show annotation Show as raw Download as raw
gravatar
alpar (Alpar Juttner)
Cut iterators for GomoryHuTree + doc cleanup + bug fixes (#66)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>



#include "test_tools.h"

#include <lemon/smart_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/gomory_hu_tree.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();



  GomoryHuTree<Graph> ght(graph, capacity);

  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;

      for(GomoryHuTree<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)

        sum+=capacity[a]; 

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



      sum=0;

      for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)

        sum++;

      for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)

        sum++;

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

      

    }

  }

  

  return 0;

}