NodeSubGraphWrapper, test, and ducumentation modifications.
2 //#include "test_tools.h"
3 #include <lemon/list_graph.h>
4 #include <mincostflow.h>
15 void check(bool rc, char *msg="") {
16 passed = passed && rc;
18 std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
29 typedef ListGraph::Node Node;
30 typedef ListGraph::Edge Edge;
36 Node s=graph.addNode();
37 Node v1=graph.addNode();
38 Node v2=graph.addNode();
39 Node v3=graph.addNode();
40 Node v4=graph.addNode();
41 Node v5=graph.addNode();
42 Node t=graph.addNode();
44 ListGraph::NodeMap<int> supply_demand(graph);
46 supply_demand.set(s, 2);
47 supply_demand.set(v1, 3);
48 supply_demand.set(v3, -1);
49 supply_demand.set(t, -4);
51 Edge s_v1=graph.addEdge(s, v1);
52 Edge v1_v2=graph.addEdge(v1, v2);
53 Edge s_v3=graph.addEdge(s, v3);
54 Edge v2_v4=graph.addEdge(v2, v4);
55 Edge v2_v5=graph.addEdge(v2, v5);
56 Edge v3_v5=graph.addEdge(v3, v5);
57 Edge v4_t=graph.addEdge(v4, t);
58 Edge v5_t=graph.addEdge(v5, t);
61 ListGraph::EdgeMap<int> cost(graph);
73 ListGraph::EdgeMap<int> capacity(graph);
75 capacity.set(s_v1, 2);
76 capacity.set(v1_v2, 2);
77 capacity.set(s_v3, 1);
78 capacity.set(v2_v4, 1);
79 capacity.set(v2_v5, 1);
80 capacity.set(v3_v5, 1);
81 capacity.set(v4_t, 1);
82 capacity.set(v5_t, 2);
85 // ConstMap<Edge, int> const1map(1);
86 std::cout << "Enhanced capacity scaling algorithm test (for the mincostflow problem)..." << std::endl;
88 MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::NodeMap<int> >
89 min_cost_flow_test(graph, cost, supply_demand);
91 min_cost_flow_test.run();
93 check(min_cost_flow_test.checkOptimality(), "Is the primal-dual solution pair really optimal?");
96 check( min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total cost should be 19");
98 check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
102 check( min_cost_flow_test.run(s,t,k) == 2 && min_cost_flow_test.totalLength() == 41,"Two paths, total cost should be 41");
104 check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
109 check( min_cost_flow_test.run(s,t,k) == 3 && min_cost_flow_test.totalLength() == 64,"Three paths, total cost should be 64");
111 check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
114 cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
117 return passed ? 0 : 1;