|
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 |
1 #include <iostream> |
19 #include <iostream> |
2 |
20 |
3 #include "test_tools.h" |
21 #include "test_tools.h" |
4 #include <lemon/smart_graph.h> |
22 #include <lemon/smart_graph.h> |
5 #include <lemon/concepts/graph.h> |
23 #include <lemon/concepts/graph.h> |
67 GRAPH_TYPEDEFS(Graph); |
85 GRAPH_TYPEDEFS(Graph); |
68 typedef Graph::EdgeMap<int> IntEdgeMap; |
86 typedef Graph::EdgeMap<int> IntEdgeMap; |
69 typedef Graph::NodeMap<bool> BoolNodeMap; |
87 typedef Graph::NodeMap<bool> BoolNodeMap; |
70 |
88 |
71 int cutValue(const Graph& graph, const BoolNodeMap& cut, |
89 int cutValue(const Graph& graph, const BoolNodeMap& cut, |
72 const IntEdgeMap& capacity) { |
90 const IntEdgeMap& capacity) { |
73 |
91 |
74 int sum = 0; |
92 int sum = 0; |
75 for (EdgeIt e(graph); e != INVALID; ++e) { |
93 for (EdgeIt e(graph); e != INVALID; ++e) { |
76 Node s = graph.u(e); |
94 Node s = graph.u(e); |
77 Node t = graph.v(e); |
95 Node t = graph.v(e); |
105 check(cm[u] != cm[v], "Wrong cut 2"); |
123 check(cm[u] != cm[v], "Wrong cut 2"); |
106 check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3"); |
124 check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3"); |
107 |
125 |
108 int sum=0; |
126 int sum=0; |
109 for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) |
127 for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) |
110 sum+=capacity[a]; |
128 sum+=capacity[a]; |
111 check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); |
129 check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); |
112 |
130 |
113 sum=0; |
131 sum=0; |
114 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n) |
132 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n) |
115 sum++; |
133 sum++; |
116 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n) |
134 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n) |
117 sum++; |
135 sum++; |
118 check(sum == countNodes(graph), "Problem with MinCutNodeIt"); |
136 check(sum == countNodes(graph), "Problem with MinCutNodeIt"); |
119 } |
137 } |
120 } |
138 } |
121 |
139 |
122 return 0; |
140 return 0; |
123 } |
141 } |