The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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
20 #include "test_tools.h"
21 #include <lemon/list_graph.h>
22 #include <lemon/min_cost_flow.h>
26 using namespace lemon;
31 void check(bool rc, char *msg="") {
32 passed = passed && rc;
34 std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
44 typedef ListGraph Graph;
45 typedef Graph::Node Node;
46 typedef Graph::Edge Edge;
52 Node s=graph.addNode();
53 Node v1=graph.addNode();
54 Node v2=graph.addNode();
55 Node v3=graph.addNode();
56 Node v4=graph.addNode();
57 Node v5=graph.addNode();
58 Node t=graph.addNode();
60 Edge s_v1=graph.addEdge(s, v1);
61 Edge v1_v2=graph.addEdge(v1, v2);
62 Edge s_v3=graph.addEdge(s, v3);
63 Edge v2_v4=graph.addEdge(v2, v4);
64 Edge v2_v5=graph.addEdge(v2, v5);
65 Edge v3_v5=graph.addEdge(v3, v5);
66 Edge v4_t=graph.addEdge(v4, t);
67 Edge v5_t=graph.addEdge(v5, t);
70 Graph::EdgeMap<int> length(graph);
81 Graph::EdgeMap<int> capacity(graph);
83 capacity.set(s_v1, 2);
84 capacity.set(v1_v2, 2);
85 capacity.set(s_v3, 1);
86 capacity.set(v2_v4, 1);
87 capacity.set(v2_v5, 1);
88 capacity.set(v3_v5, 1);
89 capacity.set(v4_t, 1);
90 capacity.set(v5_t, 2);
92 // ConstMap<Edge, int> const1map(1);
93 std::cout << "Mincostflows algorithm test..." << std::endl;
95 MinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
96 surb_test(graph, length, capacity, s, t);
101 check( surb_test.flowValue() == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
103 check( surb_test.run(k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
105 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
109 check( surb_test.run(k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
111 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
118 check( surb_test.run(k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
120 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
123 std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
126 return passed ? 0 : 1;