Port preflow push max flow alg. from svn -r3516 (#176)
Namely,
- port the files
- apply the migrate script
- apply the unify script
- break the long lines in lemon/preflow.h
- convert the .dim test file to .lgf
- fix compilation problems
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_TEST_GRAPH_TEST_H
20 #define LEMON_TEST_GRAPH_TEST_H
24 #include <lemon/core.h>
25 #include <lemon/maps.h>
27 #include "test_tools.h"
32 void checkGraphNodeList(const Graph &G, int cnt)
34 typename Graph::NodeIt n(G);
35 for(int i=0;i<cnt;i++) {
36 check(n!=INVALID,"Wrong Node list linking.");
39 check(n==INVALID,"Wrong Node list linking.");
40 check(countNodes(G)==cnt,"Wrong Node number.");
44 void checkGraphArcList(const Graph &G, int cnt)
46 typename Graph::ArcIt e(G);
47 for(int i=0;i<cnt;i++) {
48 check(e!=INVALID,"Wrong Arc list linking.");
49 check(G.oppositeNode(G.source(e), e) == G.target(e),
50 "Wrong opposite node");
51 check(G.oppositeNode(G.target(e), e) == G.source(e),
52 "Wrong opposite node");
55 check(e==INVALID,"Wrong Arc list linking.");
56 check(countArcs(G)==cnt,"Wrong Arc number.");
60 void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt)
62 typename Graph::OutArcIt e(G,n);
63 for(int i=0;i<cnt;i++) {
64 check(e!=INVALID,"Wrong OutArc list linking.");
65 check(n==G.source(e),"Wrong OutArc list linking.");
66 check(n==G.baseNode(e),"Wrong OutArc list linking.");
67 check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
70 check(e==INVALID,"Wrong OutArc list linking.");
71 check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
75 void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt)
77 typename Graph::InArcIt e(G,n);
78 for(int i=0;i<cnt;i++) {
79 check(e!=INVALID,"Wrong InArc list linking.");
80 check(n==G.target(e),"Wrong InArc list linking.");
81 check(n==G.baseNode(e),"Wrong OutArc list linking.");
82 check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
85 check(e==INVALID,"Wrong InArc list linking.");
86 check(countInArcs(G,n)==cnt,"Wrong InArc number.");
90 void checkGraphEdgeList(const Graph &G, int cnt)
92 typename Graph::EdgeIt e(G);
93 for(int i=0;i<cnt;i++) {
94 check(e!=INVALID,"Wrong Edge list linking.");
95 check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
96 check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
99 check(e==INVALID,"Wrong Edge list linking.");
100 check(countEdges(G)==cnt,"Wrong Edge number.");
103 template<class Graph>
104 void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt)
106 typename Graph::IncEdgeIt e(G,n);
107 for(int i=0;i<cnt;i++) {
108 check(e!=INVALID,"Wrong IncEdge list linking.");
109 check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
110 check(n==G.baseNode(e),"Wrong OutArc list linking.");
111 check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
112 "Wrong OutArc list linking.");
115 check(e==INVALID,"Wrong IncEdge list linking.");
116 check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
119 template <class Graph>
120 void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
123 checkGraphIncEdgeList(G, n, cnt);
124 checkGraphOutArcList(G, n, cnt);
125 checkGraphInArcList(G, n, cnt);
128 template <class Graph>
129 void checkGraphConArcList(const Graph &G, int cnt) {
131 for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
132 for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
133 for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
134 check(G.source(a) == u, "Wrong iterator.");
135 check(G.target(a) == v, "Wrong iterator.");
140 check(cnt == i, "Wrong iterator.");
143 template <class Graph>
144 void checkGraphConEdgeList(const Graph &G, int cnt) {
146 for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
147 for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
148 for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
149 check((G.u(e) == u && G.v(e) == v) ||
150 (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
155 check(2 * cnt == i, "Wrong iterator.");
158 template <typename Graph>
159 void checkArcDirections(const Graph& G) {
160 for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
161 check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
162 check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
163 check(G.direct(a, G.direction(a)) == a, "Wrong direction");
167 template <typename Graph>
168 void checkNodeIds(const Graph& G) {
169 std::set<int> values;
170 for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
171 check(G.nodeFromId(G.id(n)) == n, "Wrong id");
172 check(values.find(G.id(n)) == values.end(), "Wrong id");
173 check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
174 values.insert(G.id(n));
178 template <typename Graph>
179 void checkArcIds(const Graph& G) {
180 std::set<int> values;
181 for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
182 check(G.arcFromId(G.id(a)) == a, "Wrong id");
183 check(values.find(G.id(a)) == values.end(), "Wrong id");
184 check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
185 values.insert(G.id(a));
189 template <typename Graph>
190 void checkEdgeIds(const Graph& G) {
191 std::set<int> values;
192 for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
193 check(G.edgeFromId(G.id(e)) == e, "Wrong id");
194 check(values.find(G.id(e)) == values.end(), "Wrong id");
195 check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
196 values.insert(G.id(e));
200 template <typename Graph>
201 void checkGraphNodeMap(const Graph& G) {
202 typedef typename Graph::Node Node;
203 typedef typename Graph::NodeIt NodeIt;
205 typedef typename Graph::template NodeMap<int> IntNodeMap;
206 IntNodeMap map(G, 42);
207 for (NodeIt it(G); it != INVALID; ++it) {
208 check(map[it] == 42, "Wrong map constructor.");
211 for (NodeIt it(G); it != INVALID; ++it) {
213 check(map[it] == 0, "Wrong operator[].");
215 check(map[it] == s, "Wrong set.");
219 for (NodeIt it(G); it != INVALID; ++it) {
222 check(s == 0, "Wrong sum.");
224 // map = constMap<Node>(12);
225 // for (NodeIt it(G); it != INVALID; ++it) {
226 // check(map[it] == 12, "Wrong operator[].");
230 template <typename Graph>
231 void checkGraphArcMap(const Graph& G) {
232 typedef typename Graph::Arc Arc;
233 typedef typename Graph::ArcIt ArcIt;
235 typedef typename Graph::template ArcMap<int> IntArcMap;
236 IntArcMap map(G, 42);
237 for (ArcIt it(G); it != INVALID; ++it) {
238 check(map[it] == 42, "Wrong map constructor.");
241 for (ArcIt it(G); it != INVALID; ++it) {
243 check(map[it] == 0, "Wrong operator[].");
245 check(map[it] == s, "Wrong set.");
249 for (ArcIt it(G); it != INVALID; ++it) {
252 check(s == 0, "Wrong sum.");
254 // map = constMap<Arc>(12);
255 // for (ArcIt it(G); it != INVALID; ++it) {
256 // check(map[it] == 12, "Wrong operator[].");
260 template <typename Graph>
261 void checkGraphEdgeMap(const Graph& G) {
262 typedef typename Graph::Edge Edge;
263 typedef typename Graph::EdgeIt EdgeIt;
265 typedef typename Graph::template EdgeMap<int> IntEdgeMap;
266 IntEdgeMap map(G, 42);
267 for (EdgeIt it(G); it != INVALID; ++it) {
268 check(map[it] == 42, "Wrong map constructor.");
271 for (EdgeIt it(G); it != INVALID; ++it) {
273 check(map[it] == 0, "Wrong operator[].");
275 check(map[it] == s, "Wrong set.");
279 for (EdgeIt it(G); it != INVALID; ++it) {
282 check(s == 0, "Wrong sum.");
284 // map = constMap<Edge>(12);
285 // for (EdgeIt it(G); it != INVALID; ++it) {
286 // check(map[it] == 12, "Wrong operator[].");