.
2 #include "test_tools.h"
3 #include <hugo/list_graph.h>
4 #include <hugo/mincostflows.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 Edge s_v1=graph.addEdge(s, v1);
45 Edge v1_v2=graph.addEdge(v1, v2);
46 Edge s_v3=graph.addEdge(s, v3);
47 Edge v2_v4=graph.addEdge(v2, v4);
48 Edge v2_v5=graph.addEdge(v2, v5);
49 Edge v3_v5=graph.addEdge(v3, v5);
50 Edge v4_t=graph.addEdge(v4, t);
51 Edge v5_t=graph.addEdge(v5, t);
54 ListGraph::EdgeMap<int> length(graph);
65 ListGraph::EdgeMap<int> capacity(graph);
67 capacity.set(s_v1, 2);
68 capacity.set(v1_v2, 2);
69 capacity.set(s_v3, 1);
70 capacity.set(v2_v4, 1);
71 capacity.set(v2_v5, 1);
72 capacity.set(v3_v5, 1);
73 capacity.set(v4_t, 1);
74 capacity.set(v5_t, 2);
76 // ConstMap<Edge, int> const1map(1);
77 std::cout << "Mincostflows algorithm test..." << std::endl;
79 MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> >
80 surb_test(graph, length, capacity);
84 check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
86 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
90 check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
92 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
97 check( surb_test.run(s,t,k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
99 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
102 cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
105 return passed ? 0 : 1;