COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/gomory_hu_test.cc @ 545:e72bacfea6b7

Last change on this file since 545:e72bacfea6b7 was 545:e72bacfea6b7, checked in by Alpar Juttner <alpar@…>, 11 years ago

Remane GomoryHuTree? to GomoryHu? (#66)

File size: 2.0 KB
Line 
1#include <iostream>
2
3#include "test_tools.h"
4#include <lemon/smart_graph.h>
5#include <lemon/lgf_reader.h>
6#include <lemon/gomory_hu.h>
7#include <cstdlib>
8
9using namespace std;
10using namespace lemon;
11
12typedef SmartGraph Graph;
13
14char test_lgf[] =
15  "@nodes\n"
16  "label\n"
17  "0\n"
18  "1\n"
19  "2\n"
20  "3\n"
21  "4\n"
22  "@arcs\n"
23  "     label capacity\n"
24  "0 1  0     1\n"
25  "1 2  1     1\n"
26  "2 3  2     1\n"
27  "0 3  4     5\n"
28  "0 3  5     10\n"
29  "0 3  6     7\n"
30  "4 2  7     1\n"
31  "@attributes\n"
32  "source 0\n"
33  "target 3\n";
34 
35GRAPH_TYPEDEFS(Graph);
36typedef Graph::EdgeMap<int> IntEdgeMap;
37typedef Graph::NodeMap<bool> BoolNodeMap;
38
39int cutValue(const Graph& graph, const BoolNodeMap& cut,
40             const IntEdgeMap& capacity) {
41
42  int sum = 0;
43  for (EdgeIt e(graph); e != INVALID; ++e) {
44    Node s = graph.u(e);
45    Node t = graph.v(e);
46
47    if (cut[s] != cut[t]) {
48      sum += capacity[e];
49    }
50  }
51  return sum;
52}
53
54
55int main() {
56  Graph graph;
57  IntEdgeMap capacity(graph);
58
59  std::istringstream input(test_lgf);
60  GraphReader<Graph>(graph, input).
61    edgeMap("capacity", capacity).run();
62
63  GomoryHu<Graph> ght(graph, capacity);
64  ght.init();
65  ght.run();
66
67  for (NodeIt u(graph); u != INVALID; ++u) {
68    for (NodeIt v(graph); v != u; ++v) {
69      Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
70      pf.runMinCut();
71      BoolNodeMap cm(graph);
72      ght.minCutMap(u, v, cm);
73      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
74      check(cm[u] != cm[v], "Wrong cut 3");
75      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
76
77      int sum=0;
78      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
79        sum+=capacity[a];
80      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
81
82      sum=0;
83      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
84        sum++;
85      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
86        sum++;
87      check(sum == countNodes(graph), "Problem with MinCutNodeIt");
88     
89    }
90  }
91 
92  return 0;
93}
Note: See TracBrowser for help on using the repository browser.