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-2013
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/list_graph.h>
23 #include <lemon/circulation.h>
24 #include <lemon/lgf_reader.h>
25 #include <lemon/concepts/digraph.h>
26 #include <lemon/concepts/maps.h>
27
28 using namespace lemon;
29
30 char test_lgf[] =
31 "@nodes\n"
32 "label\n"
33 "0\n"
34 "1\n"
35 "2\n"
36 "3\n"
37 "4\n"
38 "5\n"
39 "@arcs\n"
40 " lcap ucap\n"
41 "0 1 2 10\n"
42 "0 2 2 6\n"
43 "1 3 4 7\n"
44 "1 4 0 5\n"
45 "2 4 1 3\n"
46 "3 5 3 8\n"
47 "4 5 3 7\n"
48 "@attributes\n"
49 "source 0\n"
50 "sink 5\n";
51
checkCirculationCompile()52 void checkCirculationCompile()
53 {
54 typedef int VType;
55 typedef concepts::Digraph Digraph;
56
57 typedef Digraph::Node Node;
58 typedef Digraph::Arc Arc;
59 typedef concepts::ReadMap<Arc,VType> CapMap;
60 typedef concepts::ReadMap<Node,VType> SupplyMap;
61 typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
62 typedef concepts::WriteMap<Node,bool> BarrierMap;
63
64 typedef Elevator<Digraph, Digraph::Node> Elev;
65 typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
66
67 Digraph g;
68 Node n;
69 Arc a;
70 CapMap lcap, ucap;
71 SupplyMap supply;
72 FlowMap flow;
73 BarrierMap bar;
74 VType v;
75 bool b;
76 ::lemon::ignore_unused_variable_warning(v,b);
77
78 typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>
79 ::SetFlowMap<FlowMap>
80 ::SetElevator<Elev>
81 ::SetStandardElevator<LinkedElev>
82 ::Create CirculationType;
83 CirculationType circ_test(g, lcap, ucap, supply);
84 const CirculationType& const_circ_test = circ_test;
85
86 circ_test
87 .lowerMap(lcap)
88 .upperMap(ucap)
89 .supplyMap(supply)
90 .flowMap(flow);
91
92 const CirculationType::Elevator& elev = const_circ_test.elevator();
93 circ_test.elevator(const_cast<CirculationType::Elevator&>(elev));
94 CirculationType::Tolerance tol = const_circ_test.tolerance();
95 circ_test.tolerance(tol);
96
97 circ_test.init();
98 circ_test.greedyInit();
99 circ_test.start();
100 circ_test.run();
101
102 v = const_circ_test.flow(a);
103 const FlowMap& fm = const_circ_test.flowMap();
104 b = const_circ_test.barrier(n);
105 const_circ_test.barrierMap(bar);
106
107 ::lemon::ignore_unused_variable_warning(fm);
108 }
109
110 template <class G, class LM, class UM, class DM>
checkCirculation(const G & g,const LM & lm,const UM & um,const DM & dm,bool find)111 void checkCirculation(const G& g, const LM& lm, const UM& um,
112 const DM& dm, bool find)
113 {
114 Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
115 bool ret = circ.run();
116 if (find) {
117 check(ret, "A feasible solution should have been found.");
118 check(circ.checkFlow(), "The found flow is corrupt.");
119 check(!circ.checkBarrier(), "A barrier should not have been found.");
120 } else {
121 check(!ret, "A feasible solution should not have been found.");
122 check(circ.checkBarrier(), "The found barrier is corrupt.");
123 }
124 }
125
main(int,char * [])126 int main (int, char*[])
127 {
128 typedef ListDigraph Digraph;
129 DIGRAPH_TYPEDEFS(Digraph);
130
131 Digraph g;
132 IntArcMap lo(g), up(g);
133 IntNodeMap delta(g, 0);
134 Node s, t;
135
136 std::istringstream input(test_lgf);
137 DigraphReader<Digraph>(g,input).
138 arcMap("lcap", lo).
139 arcMap("ucap", up).
140 node("source",s).
141 node("sink",t).
142 run();
143
144 delta[s] = 7; delta[t] = -7;
145 checkCirculation(g, lo, up, delta, true);
146
147 delta[s] = 13; delta[t] = -13;
148 checkCirculation(g, lo, up, delta, true);
149
150 delta[s] = 6; delta[t] = -6;
151 checkCirculation(g, lo, up, delta, false);
152
153 delta[s] = 14; delta[t] = -14;
154 checkCirculation(g, lo, up, delta, false);
155
156 delta[s] = 7; delta[t] = -13;
157 checkCirculation(g, lo, up, delta, true);
158
159 delta[s] = 5; delta[t] = -15;
160 checkCirculation(g, lo, up, delta, true);
161
162 delta[s] = 10; delta[t] = -11;
163 checkCirculation(g, lo, up, delta, true);
164
165 delta[s] = 11; delta[t] = -10;
166 checkCirculation(g, lo, up, delta, false);
167
168 return 0;
169 }
170