1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2009 |
5 * Copyright (C) 2003-2011 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
81 v = const_ho_test.minCutValue(); |
81 v = const_ho_test.minCutValue(); |
82 v = const_ho_test.minCutMap(cut); |
82 v = const_ho_test.minCutMap(cut); |
83 } |
83 } |
84 |
84 |
85 template <typename Graph, typename CapMap, typename CutMap> |
85 template <typename Graph, typename CapMap, typename CutMap> |
86 typename CapMap::Value |
86 typename CapMap::Value |
87 cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) |
87 cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) |
88 { |
88 { |
89 typename CapMap::Value sum = 0; |
89 typename CapMap::Value sum = 0; |
90 for (typename Graph::ArcIt a(graph); a != INVALID; ++a) { |
90 for (typename Graph::ArcIt a(graph); a != INVALID; ++a) { |
91 if (cut[graph.source(a)] && !cut[graph.target(a)]) |
91 if (cut[graph.source(a)] && !cut[graph.target(a)]) |
108 |
108 |
109 { |
109 { |
110 HaoOrlin<SmartDigraph> ho(graph, cap1); |
110 HaoOrlin<SmartDigraph> ho(graph, cap1); |
111 ho.run(); |
111 ho.run(); |
112 ho.minCutMap(cut); |
112 ho.minCutMap(cut); |
113 |
113 |
114 check(ho.minCutValue() == 1, "Wrong cut value"); |
114 check(ho.minCutValue() == 1, "Wrong cut value"); |
115 check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); |
115 check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); |
116 } |
116 } |
117 { |
117 { |
118 HaoOrlin<SmartDigraph> ho(graph, cap2); |
118 HaoOrlin<SmartDigraph> ho(graph, cap2); |
124 } |
124 } |
125 { |
125 { |
126 HaoOrlin<SmartDigraph> ho(graph, cap3); |
126 HaoOrlin<SmartDigraph> ho(graph, cap3); |
127 ho.run(); |
127 ho.run(); |
128 ho.minCutMap(cut); |
128 ho.minCutMap(cut); |
129 |
129 |
130 check(ho.minCutValue() == 1, "Wrong cut value"); |
130 check(ho.minCutValue() == 1, "Wrong cut value"); |
131 check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); |
131 check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); |
132 } |
132 } |
133 |
133 |
134 typedef Undirector<SmartDigraph> UGraph; |
134 typedef Undirector<SmartDigraph> UGraph; |
135 UGraph ugraph(graph); |
135 UGraph ugraph(graph); |
136 |
136 |
137 { |
137 { |
138 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1); |
138 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1); |
139 ho.run(); |
139 ho.run(); |
140 ho.minCutMap(cut); |
140 ho.minCutMap(cut); |
141 |
141 |
142 check(ho.minCutValue() == 2, "Wrong cut value"); |
142 check(ho.minCutValue() == 2, "Wrong cut value"); |
143 check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); |
143 check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); |
144 } |
144 } |
145 { |
145 { |
146 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2); |
146 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2); |
147 ho.run(); |
147 ho.run(); |
148 ho.minCutMap(cut); |
148 ho.minCutMap(cut); |
149 |
149 |
150 check(ho.minCutValue() == 5, "Wrong cut value"); |
150 check(ho.minCutValue() == 5, "Wrong cut value"); |
151 check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); |
151 check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); |
152 } |
152 } |
153 { |
153 { |
154 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3); |
154 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3); |
155 ho.run(); |
155 ho.run(); |
156 ho.minCutMap(cut); |
156 ho.minCutMap(cut); |
157 |
157 |
158 check(ho.minCutValue() == 5, "Wrong cut value"); |
158 check(ho.minCutValue() == 5, "Wrong cut value"); |
159 check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); |
159 check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); |
160 } |
160 } |
161 |
161 |
162 return 0; |
162 return 0; |