COIN-OR::LEMON - Graph Library

source: lemon/test/gomory_hu_test.cc @ 1126:a30455cd0107

1.1 r1.1.4
Last change on this file since 1126:a30455cd0107 was 1081:f1398882a928, checked in by Alpar Juttner <alpar@…>, 13 years ago

Unify sources

File size: 3.3 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2011
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <iostream>
20
21#include "test_tools.h"
22#include <lemon/smart_graph.h>
23#include <lemon/concepts/graph.h>
24#include <lemon/concepts/maps.h>
25#include <lemon/lgf_reader.h>
26#include <lemon/gomory_hu.h>
27#include <cstdlib>
28
29using namespace std;
30using namespace lemon;
31
32typedef SmartGraph Graph;
33
34char test_lgf[] =
35  "@nodes\n"
36  "label\n"
37  "0\n"
38  "1\n"
39  "2\n"
40  "3\n"
41  "4\n"
42  "@arcs\n"
43  "     label capacity\n"
44  "0 1  0     1\n"
45  "1 2  1     1\n"
46  "2 3  2     1\n"
47  "0 3  4     5\n"
48  "0 3  5     10\n"
49  "0 3  6     7\n"
50  "4 2  7     1\n"
51  "@attributes\n"
52  "source 0\n"
53  "target 3\n";
54
55void checkGomoryHuCompile()
56{
57  typedef int Value;
58  typedef concepts::Graph Graph;
59
60  typedef Graph::Node Node;
61  typedef Graph::Edge Edge;
62  typedef concepts::ReadMap<Edge, Value> CapMap;
63  typedef concepts::ReadWriteMap<Node, bool> CutMap;
64
65  Graph g;
66  Node n;
67  CapMap cap;
68  CutMap cut;
69  Value v;
70  int d;
71
72  GomoryHu<Graph, CapMap> gh_test(g, cap);
73  const GomoryHu<Graph, CapMap>&
74    const_gh_test = gh_test;
75
76  gh_test.run();
77
78  n = const_gh_test.predNode(n);
79  v = const_gh_test.predValue(n);
80  d = const_gh_test.rootDist(n);
81  v = const_gh_test.minCutValue(n, n);
82  v = const_gh_test.minCutMap(n, n, cut);
83}
84
85GRAPH_TYPEDEFS(Graph);
86typedef Graph::EdgeMap<int> IntEdgeMap;
87typedef Graph::NodeMap<bool> BoolNodeMap;
88
89int cutValue(const Graph& graph, const BoolNodeMap& cut,
90             const IntEdgeMap& capacity) {
91
92  int sum = 0;
93  for (EdgeIt e(graph); e != INVALID; ++e) {
94    Node s = graph.u(e);
95    Node t = graph.v(e);
96
97    if (cut[s] != cut[t]) {
98      sum += capacity[e];
99    }
100  }
101  return sum;
102}
103
104
105int main() {
106  Graph graph;
107  IntEdgeMap capacity(graph);
108
109  std::istringstream input(test_lgf);
110  GraphReader<Graph>(graph, input).
111    edgeMap("capacity", capacity).run();
112
113  GomoryHu<Graph> ght(graph, capacity);
114  ght.run();
115
116  for (NodeIt u(graph); u != INVALID; ++u) {
117    for (NodeIt v(graph); v != u; ++v) {
118      Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
119      pf.runMinCut();
120      BoolNodeMap cm(graph);
121      ght.minCutMap(u, v, cm);
122      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
123      check(cm[u] != cm[v], "Wrong cut 2");
124      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
125
126      int sum=0;
127      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
128        sum+=capacity[a];
129      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
130
131      sum=0;
132      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
133        sum++;
134      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
135        sum++;
136      check(sum == countNodes(graph), "Problem with MinCutNodeIt");
137    }
138  }
139
140  return 0;
141}
Note: See TracBrowser for help on using the repository browser.