COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/gomory_hu_test.cc @ 543:924887566bf2

Last change on this file since 543:924887566bf2 was 543:924887566bf2, checked in by Janos Tapolcai <tapolcai@…>, 11 years ago

Porting Gomory-Hu algorithm (#66)

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