COIN-OR::LEMON - Graph Library

source: lemon/test/gomory_hu_test.cc @ 1236:756022ac1674

Last change on this file since 1236:756022ac1674 was 1171:7e368d9b67f7, checked in by Alpar Juttner <alpar@…>, 11 years ago

Avoid GCC 4.7 compiler warnings (#453)

File size: 2.7 KB
Line 
1#include <iostream>
2
3#include "test_tools.h"
4#include <lemon/smart_graph.h>
5#include <lemon/concepts/graph.h>
6#include <lemon/concepts/maps.h>
7#include <lemon/lgf_reader.h>
8#include <lemon/gomory_hu.h>
9#include <cstdlib>
10
11using namespace std;
12using namespace lemon;
13
14typedef SmartGraph Graph;
15
16char test_lgf[] =
17  "@nodes\n"
18  "label\n"
19  "0\n"
20  "1\n"
21  "2\n"
22  "3\n"
23  "4\n"
24  "@arcs\n"
25  "     label capacity\n"
26  "0 1  0     1\n"
27  "1 2  1     1\n"
28  "2 3  2     1\n"
29  "0 3  4     5\n"
30  "0 3  5     10\n"
31  "0 3  6     7\n"
32  "4 2  7     1\n"
33  "@attributes\n"
34  "source 0\n"
35  "target 3\n";
36 
37void checkGomoryHuCompile()
38{
39  typedef int Value;
40  typedef concepts::Graph Graph;
41
42  typedef Graph::Node Node;
43  typedef Graph::Edge Edge;
44  typedef concepts::ReadMap<Edge, Value> CapMap;
45  typedef concepts::ReadWriteMap<Node, bool> CutMap;
46
47  Graph g;
48  Node n;
49  CapMap cap;
50  CutMap cut;
51  Value v;
52  int d;
53  ignore_unused_variable_warning(v,d);
54
55  GomoryHu<Graph, CapMap> gh_test(g, cap);
56  const GomoryHu<Graph, CapMap>&
57    const_gh_test = gh_test;
58
59  gh_test.run();
60
61  n = const_gh_test.predNode(n);
62  v = const_gh_test.predValue(n);
63  d = const_gh_test.rootDist(n);
64  v = const_gh_test.minCutValue(n, n);
65  v = const_gh_test.minCutMap(n, n, cut);
66}
67
68GRAPH_TYPEDEFS(Graph);
69typedef Graph::EdgeMap<int> IntEdgeMap;
70typedef Graph::NodeMap<bool> BoolNodeMap;
71
72int cutValue(const Graph& graph, const BoolNodeMap& cut,
73             const IntEdgeMap& capacity) {
74
75  int sum = 0;
76  for (EdgeIt e(graph); e != INVALID; ++e) {
77    Node s = graph.u(e);
78    Node t = graph.v(e);
79
80    if (cut[s] != cut[t]) {
81      sum += capacity[e];
82    }
83  }
84  return sum;
85}
86
87
88int main() {
89  Graph graph;
90  IntEdgeMap capacity(graph);
91
92  std::istringstream input(test_lgf);
93  GraphReader<Graph>(graph, input).
94    edgeMap("capacity", capacity).run();
95
96  GomoryHu<Graph> ght(graph, capacity);
97  ght.run();
98
99  for (NodeIt u(graph); u != INVALID; ++u) {
100    for (NodeIt v(graph); v != u; ++v) {
101      Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
102      pf.runMinCut();
103      BoolNodeMap cm(graph);
104      ght.minCutMap(u, v, cm);
105      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
106      check(cm[u] != cm[v], "Wrong cut 2");
107      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
108
109      int sum=0;
110      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
111        sum+=capacity[a];
112      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
113
114      sum=0;
115      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
116        sum++;
117      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
118        sum++;
119      check(sum == countNodes(graph), "Problem with MinCutNodeIt");
120    }
121  }
122 
123  return 0;
124}
Note: See TracBrowser for help on using the repository browser.