COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/gomory_hu_test.cc @ 997:4f55bac7e625

Last change on this file since 997:4f55bac7e625 was 983:8b2d4e5d96e4, checked in by Alpar Juttner <alpar@…>, 11 years ago

Merge #294 to branches >=1.2

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-2010
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  ::lemon::ignore_unused_variable_warning(v,d);
72
73  GomoryHu<Graph, CapMap> gh_test(g, cap);
74  const GomoryHu<Graph, CapMap>&
75    const_gh_test = gh_test;
76
77  gh_test.run();
78
79  n = const_gh_test.predNode(n);
80  v = const_gh_test.predValue(n);
81  d = const_gh_test.rootDist(n);
82  v = const_gh_test.minCutValue(n, n);
83  v = const_gh_test.minCutMap(n, n, cut);
84}
85
86GRAPH_TYPEDEFS(Graph);
87typedef Graph::EdgeMap<int> IntEdgeMap;
88typedef Graph::NodeMap<bool> BoolNodeMap;
89
90int cutValue(const Graph& graph, const BoolNodeMap& cut,
91             const IntEdgeMap& capacity) {
92
93  int sum = 0;
94  for (EdgeIt e(graph); e != INVALID; ++e) {
95    Node s = graph.u(e);
96    Node t = graph.v(e);
97
98    if (cut[s] != cut[t]) {
99      sum += capacity[e];
100    }
101  }
102  return sum;
103}
104
105
106int main() {
107  Graph graph;
108  IntEdgeMap capacity(graph);
109
110  std::istringstream input(test_lgf);
111  GraphReader<Graph>(graph, input).
112    edgeMap("capacity", capacity).run();
113
114  GomoryHu<Graph> ght(graph, capacity);
115  ght.run();
116
117  for (NodeIt u(graph); u != INVALID; ++u) {
118    for (NodeIt v(graph); v != u; ++v) {
119      Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
120      pf.runMinCut();
121      BoolNodeMap cm(graph);
122      ght.minCutMap(u, v, cm);
123      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
124      check(cm[u] != cm[v], "Wrong cut 2");
125      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
126
127      int sum=0;
128      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
129        sum+=capacity[a];
130      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
131
132      sum=0;
133      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
134        sum++;
135      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
136        sum++;
137      check(sum == countNodes(graph), "Problem with MinCutNodeIt");
138    }
139  }
140
141  return 0;
142}
Note: See TracBrowser for help on using the repository browser.