- void checkBackInsertablePath() {
-
- // Create and check empty path
- P p;
- const P& cp = p;
- check(cp.empty(), "The path is not empty");
- check(cp.length() == 0, "The path is not empty");
-// check(cp.front() == INVALID, "Wrong front()");
-// check(cp.back() == INVALID, "Wrong back()");
- typename P::ArcIt ai(cp);
- check(ai == INVALID, "Wrong ArcIt");
- check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()");
- check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()");
- check(checkPath(cgr, cp), "Wrong checkPath()");
- PathNodeIt ni(cgr, cp);
- check(ni == INVALID, "Wrong PathNodeIt");
-
- // Check single-arc path
- p.addBack(a1);
- check(!cp.empty(), "Wrong empty()");
- check(cp.length() == 1, "Wrong length");
- check(cp.front() == a1, "Wrong front()");
- check(cp.back() == a1, "Wrong back()");
- check(cp.nth(0) == a1, "Wrong nth()");
- ai = cp.nthIt(0);
- check((tmp_a = ai) == a1, "Wrong nthIt()");
- check(++ai == INVALID, "Wrong nthIt()");
- typename P::ArcIt ai2(cp);
- check((tmp_a = ai2) == a1, "Wrong ArcIt");
- check(++ai2 == INVALID, "Wrong ArcIt");
- check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
- check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
- check(checkPath(cgr, cp), "Wrong checkPath()");
- PathNodeIt
ni2(cgr, cp);
- check((tmp_n = ni2) == n1, "Wrong PathNodeIt");
- check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt");
- check(++ni2 == INVALID, "Wrong PathNodeIt");
-
- // Check adding more arcs
- p.addBack(a2);
- p.addBack(a3);
- check(!cp.empty(), "Wrong empty()");
- check(cp.length() == 3, "Wrong length");
- check(cp.front() == a1, "Wrong front()");
- check(cp.back() == a3, "Wrong back()");
- check(cp.nth(0) == a1, "Wrong nth()");
- check(cp.nth(1) == a2, "Wrong nth()");
- check(cp.nth(2) == a3, "Wrong nth()");
- typename P::ArcIt ai3(cp);
- check((tmp_a = ai3) == a1, "Wrong ArcIt");
- check((tmp_a = ++ai3) == a2, "Wrong nthIt()");
- check((tmp_a = ++ai3) == a3, "Wrong nthIt()");
- check(++ai3 == INVALID, "Wrong nthIt()");
- ai = cp.nthIt(0);
- check((tmp_a = ai) == a1, "Wrong nthIt()");
- check((tmp_a = ++ai) == a2, "Wrong nthIt()");
- ai = cp.nthIt(2);
- check((tmp_a = ai) == a3, "Wrong nthIt()");
- check(++ai == INVALID, "Wrong nthIt()");
- check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
- check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()");
- check(checkPath(cgr, cp), "Wrong checkPath()");
- PathNodeIt
ni3(cgr, cp);
- check((tmp_n = ni3) == n1, "Wrong PathNodeIt");
- check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt");
- check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt");
- check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt");
- check(++ni3 == INVALID, "Wrong PathNodeIt");
-
- // Check arc removal and addition
- p.eraseBack();
- p.eraseBack();
- p.addBack(a2);
- check(!cp.empty(), "Wrong empty()");
- check(cp.length() == 2, "Wrong length");
- check(cp.front() == a1, "Wrong front()");
- check(cp.back() == a2, "Wrong back()");
- check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
- check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
- check(checkPath(cgr, cp), "Wrong checkPath()");
-
- // Check clear()
- p.clear();
- check(cp.empty(), "The path is not empty");
- check(cp.length() == 0, "The path is not empty");
-
- // Check inconsistent path
- p.addBack(a4);
- p.addBack(a2);
- p.addBack(a1);
- check(!cp.empty(), "Wrong empty()");
- check(cp.length() == 3, "Wrong length");
- check(cp.front() == a4, "Wrong front()");
- check(cp.back() == a1, "Wrong back()");
- check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
- check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
- check(!checkPath(cgr, cp), "Wrong checkPath()");
- }
-
- template
- void checkBackAndFrontInsertablePath() {
-
- // Include back insertable test cases
- checkBackInsertablePath();
-
- // Check front and back insertion
- P p;
- const P& cp = p;
- p.addFront(a4);
- p.addBack(a1);
- p.addFront(a3);
- check(!cp.empty(), "Wrong empty()");
- check(cp.length() == 3, "Wrong length");
- check(cp.front() == a3, "Wrong front()");
- check(cp.back() == a1, "Wrong back()");
- check(cp.nth(0) == a3, "Wrong nth()");
- check(cp.nth(1) == a4, "Wrong nth()");
- check(cp.nth(2) == a1, "Wrong nth()");
- typename P::ArcIt ai(cp);
- check((tmp_a = ai) == a3, "Wrong ArcIt");
- check((tmp_a = ++ai) == a4, "Wrong nthIt()");
- check((tmp_a = ++ai) == a1, "Wrong nthIt()");
- check(++ai == INVALID, "Wrong nthIt()");
- ai = cp.nthIt(0);
- check((tmp_a = ai) == a3, "Wrong nthIt()");
- check((tmp_a = ++ai) == a4, "Wrong nthIt()");
- ai = cp.nthIt(2);
- check((tmp_a = ai) == a1, "Wrong nthIt()");
- check(++ai == INVALID, "Wrong nthIt()");
- check(pathSource(cgr, cp) == n3, "Wrong pathSource()");
- check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
- check(checkPath(cgr, cp), "Wrong checkPath()");
-
- // Check eraseFront()
- p.eraseFront();
- p.addBack(a2);
- check(!cp.empty(), "Wrong empty()");
- check(cp.length() == 3, "Wrong length");
- check(cp.front() == a4, "Wrong front()");
- check(cp.back() == a2, "Wrong back()");
- check(cp.nth(0) == a4, "Wrong nth()");
- check(cp.nth(1) == a1, "Wrong nth()");
- check(cp.nth(2) == a2, "Wrong nth()");
- typename P::ArcIt ai2(cp);
- check((tmp_a = ai2) == a4, "Wrong ArcIt");
- check((tmp_a = ++ai2) == a1, "Wrong nthIt()");
- check((tmp_a = ++ai2) == a2, "Wrong nthIt()");
- check(++ai2 == INVALID, "Wrong nthIt()");
- ai = cp.nthIt(0);
- check((tmp_a = ai) == a4, "Wrong nthIt()");
- check((tmp_a = ++ai) == a1, "Wrong nthIt()");
- ai = cp.nthIt(2);
- check((tmp_a = ai) == a2, "Wrong nthIt()");
- check(++ai == INVALID, "Wrong nthIt()");
- check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
- check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
- check(checkPath(cgr, cp), "Wrong checkPath()");
- }
-
- void checkListPathSplitAndSplice() {
-
- // Build a path with spliceFront() and spliceBack()
- ListPath p1, p2, p3, p4;
- p1.addBack(a3);
- p1.addFront(a2);
- p2.addBack(a1);
- p1.spliceFront(p2);
- p3.addFront(a4);
- p1.spliceBack(p3);
- check(p1.length() == 4, "Wrong length");
- check(p1.front() == a1, "Wrong front()");
- check(p1.back() == a4, "Wrong back()");
- ListPath::ArcIt ai(p1);
- check((tmp_a = ai) == a1, "Wrong ArcIt");
- check((tmp_a = ++ai) == a2, "Wrong nthIt()");
- check((tmp_a = ++ai) == a3, "Wrong nthIt()");
- check((tmp_a = ++ai) == a4, "Wrong nthIt()");
- check(++ai == INVALID, "Wrong nthIt()");
- check(checkPath(cgr, p1), "Wrong checkPath()");
-
- // Check split()
- p1.split(p1.nthIt(2), p2);
- check(p1.length() == 2, "Wrong length");
- ai = p1.nthIt(0);
- check((tmp_a = ai) == a1, "Wrong ArcIt");
- check((tmp_a = ++ai) == a2, "Wrong nthIt()");
- check(++ai == INVALID, "Wrong nthIt()");
- check(checkPath(cgr, p1), "Wrong checkPath()");
- check(p2.length() == 2, "Wrong length");
- ai = p2.nthIt(0);
- check((tmp_a = ai) == a3, "Wrong ArcIt");
- check((tmp_a = ++ai) == a4, "Wrong nthIt()");
- check(++ai == INVALID, "Wrong nthIt()");
- check(checkPath(cgr, p2), "Wrong checkPath()");
-
- // Check split() and splice()
- p1.spliceFront(p2);
- p1.split(p1.nthIt(2), p2);
- p2.split(p2.nthIt(1), p3);
- p2.spliceBack(p1);
- p2.splice(p2.nthIt(1), p3);
- check(p2.length() == 4, "Wrong length");
- check(p2.front() == a1, "Wrong front()");
- check(p2.back() == a4, "Wrong back()");
- ai = p2.nthIt(0);
- check((tmp_a = ai) == a1, "Wrong ArcIt");
- check((tmp_a = ++ai) == a2, "Wrong nthIt()");
- check((tmp_a = ++ai) == a3, "Wrong nthIt()");
- check((tmp_a = ++ai) == a4, "Wrong nthIt()");
- check(++ai == INVALID, "Wrong nthIt()");
- check(checkPath(cgr, p2), "Wrong checkPath()");
- }
-
-};
-
-int main() {
- checkPathConcepts();
- checkPathCopy();
- CheckPathFunctions cpf;
- cpf.run();
+ ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode());
+
+ Path p;
+ StaticPath q,r;
+ p.addBack(a);
+ q=p;
+ r=q;
+ StaticPath s(q);
return 0;
Index: test/preflow_test.cc
===================================================================
--- test/preflow_test.cc (revision 1008)
+++ test/preflow_test.cc (revision 1008)
@@ -0,0 +1,277 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include
+
+#include "test_tools.h"
+#include
+#include
+#include
+#include
+#include
+#include
+
+using namespace lemon;
+
+char test_lgf[] =
+ "@nodes\n"
+ "label\n"
+ "0\n"
+ "1\n"
+ "2\n"
+ "3\n"
+ "4\n"
+ "5\n"
+ "6\n"
+ "7\n"
+ "8\n"
+ "9\n"
+ "@arcs\n"
+ " label capacity\n"
+ "0 1 0 20\n"
+ "0 2 1 0\n"
+ "1 1 2 3\n"
+ "1 2 3 8\n"
+ "1 3 4 8\n"
+ "2 5 5 5\n"
+ "3 2 6 5\n"
+ "3 5 7 5\n"
+ "3 6 8 5\n"
+ "4 3 9 3\n"
+ "5 7 10 3\n"
+ "5 6 11 10\n"
+ "5 8 12 10\n"
+ "6 8 13 8\n"
+ "8 9 14 20\n"
+ "8 1 15 5\n"
+ "9 5 16 5\n"
+ "@attributes\n"
+ "source 1\n"
+ "target 8\n";
+
+void checkPreflowCompile()
+{
+ typedef int VType;
+ typedef concepts::Digraph Digraph;
+
+ typedef Digraph::Node Node;
+ typedef Digraph::Arc Arc;
+ typedef concepts::ReadMap CapMap;
+ typedef concepts::ReadWriteMap FlowMap;
+ typedef concepts::WriteMap CutMap;
+
+ typedef Elevator Elev;
+ typedef LinkedElevator LinkedElev;
+
+ Digraph g;
+ Node n;
+ Arc e;
+ CapMap cap;
+ FlowMap flow;
+ CutMap cut;
+ VType v;
+ bool b;
+ ignore_unused_variable_warning(v,b);
+
+ typedef Preflow
+ ::SetFlowMap
+ ::SetElevator
+ ::SetStandardElevator
+ ::Create PreflowType;
+ PreflowType preflow_test(g, cap, n, n);
+ const PreflowType& const_preflow_test = preflow_test;
+
+ const PreflowType::Elevator& elev = const_preflow_test.elevator();
+ preflow_test.elevator(const_cast(elev));
+ PreflowType::Tolerance tol = const_preflow_test.tolerance();
+ preflow_test.tolerance(tol);
+
+ preflow_test
+ .capacityMap(cap)
+ .flowMap(flow)
+ .source(n)
+ .target(n);
+
+ preflow_test.init();
+ preflow_test.init(cap);
+ preflow_test.startFirstPhase();
+ preflow_test.startSecondPhase();
+ preflow_test.run();
+ preflow_test.runMinCut();
+
+ v = const_preflow_test.flowValue();
+ v = const_preflow_test.flow(e);
+ const FlowMap& fm = const_preflow_test.flowMap();
+ b = const_preflow_test.minCut(n);
+ const_preflow_test.minCutMap(cut);
+
+ ignore_unused_variable_warning(fm);
+}
+
+int cutValue (const SmartDigraph& g,
+ const SmartDigraph::NodeMap& cut,
+ const SmartDigraph::ArcMap& cap) {
+
+ int c=0;
+ for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
+ if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
+ }
+ return c;
+}
+
+bool checkFlow(const SmartDigraph& g,
+ const SmartDigraph::ArcMap& flow,
+ const SmartDigraph::ArcMap& cap,
+ SmartDigraph::Node s, SmartDigraph::Node t) {
+
+ for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
+ if (flow[e] < 0 || flow[e] > cap[e]) return false;
+ }
+
+ for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
+ if (n == s || n == t) continue;
+ int sum = 0;
+ for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
+ sum += flow[e];
+ }
+ for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
+ sum -= flow[e];
+ }
+ if (sum != 0) return false;
+ }
+ return true;
+}
+
+void initFlowTest()
+{
+ DIGRAPH_TYPEDEFS(SmartDigraph);
+
+ SmartDigraph g;
+ SmartDigraph::ArcMap cap(g),iflow(g);
+ Node s=g.addNode(); Node t=g.addNode();
+ Node n1=g.addNode(); Node n2=g.addNode();
+ Arc a;
+ a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
+ a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
+ a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
+
+ Preflow pre(g,cap,s,t);
+ pre.init(iflow);
+ pre.startFirstPhase();
+ check(pre.flowValue() == 10, "The incorrect max flow value.");
+ check(pre.minCut(s), "Wrong min cut (Node s).");
+ check(pre.minCut(n1), "Wrong min cut (Node n1).");
+ check(!pre.minCut(n2), "Wrong min cut (Node n2).");
+ check(!pre.minCut(t), "Wrong min cut (Node t).");
+}
+
+
+int main() {
+
+ typedef SmartDigraph Digraph;
+
+ typedef Digraph::Node Node;
+ typedef Digraph::NodeIt NodeIt;
+ typedef Digraph::ArcIt ArcIt;
+ typedef Digraph::ArcMap CapMap;
+ typedef Digraph::ArcMap FlowMap;
+ typedef Digraph::NodeMap CutMap;
+
+ typedef Preflow PType;
+
+ Digraph g;
+ Node s, t;
+ CapMap cap(g);
+ std::istringstream input(test_lgf);
+ DigraphReader(g,input).
+ arcMap("capacity", cap).
+ node("source",s).
+ node("target",t).
+ run();
+
+ PType preflow_test(g, cap, s, t);
+ preflow_test.run();
+
+ check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
+ "The flow is not feasible.");
+
+ CutMap min_cut(g);
+ preflow_test.minCutMap(min_cut);
+ int min_cut_value=cutValue(g,min_cut,cap);
+
+ check(preflow_test.flowValue() == min_cut_value,
+ "The max flow value is not equal to the three min cut values.");
+
+ FlowMap flow(g);
+ for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
+
+ int flow_value=preflow_test.flowValue();
+
+ for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
+ preflow_test.init(flow);
+ preflow_test.startFirstPhase();
+
+ CutMap min_cut1(g);
+ preflow_test.minCutMap(min_cut1);
+ min_cut_value=cutValue(g,min_cut1,cap);
+
+ check(preflow_test.flowValue() == min_cut_value &&
+ min_cut_value == 2*flow_value,
+ "The max flow value or the min cut value is wrong.");
+
+ preflow_test.startSecondPhase();
+
+ check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
+ "The flow is not feasible.");
+
+ CutMap min_cut2(g);
+ preflow_test.minCutMap(min_cut2);
+ min_cut_value=cutValue(g,min_cut2,cap);
+
+ check(preflow_test.flowValue() == min_cut_value &&
+ min_cut_value == 2*flow_value,
+ "The max flow value or the three min cut values were not doubled");
+
+
+ preflow_test.flowMap(flow);
+
+ NodeIt tmp1(g,s);
+ ++tmp1;
+ if ( tmp1 != INVALID ) s=tmp1;
+
+ NodeIt tmp2(g,t);
+ ++tmp2;
+ if ( tmp2 != INVALID ) t=tmp2;
+
+ preflow_test.source(s);
+ preflow_test.target(t);
+
+ preflow_test.run();
+
+ CutMap min_cut3(g);
+ preflow_test.minCutMap(min_cut3);
+ min_cut_value=cutValue(g,min_cut3,cap);
+
+
+ check(preflow_test.flowValue() == min_cut_value,
+ "The max flow value or the three min cut values are incorrect.");
+
+ initFlowTest();
+
+ return 0;
+}