athos@659
|
1 |
#include <iostream>
|
athos@661
|
2 |
//#include "test_tools.h"
|
athos@659
|
3 |
#include <hugo/list_graph.h>
|
athos@659
|
4 |
#include <mincostflow.h>
|
athos@659
|
5 |
//#include <path.h>
|
athos@659
|
6 |
//#include <maps.h>
|
athos@659
|
7 |
|
athos@659
|
8 |
using namespace std;
|
athos@659
|
9 |
using namespace hugo;
|
athos@659
|
10 |
|
athos@659
|
11 |
|
athos@659
|
12 |
|
athos@659
|
13 |
bool passed = true;
|
athos@659
|
14 |
/*
|
athos@659
|
15 |
void check(bool rc, char *msg="") {
|
athos@659
|
16 |
passed = passed && rc;
|
athos@659
|
17 |
if(!rc) {
|
athos@659
|
18 |
std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
|
athos@659
|
19 |
|
athos@659
|
20 |
|
athos@659
|
21 |
}
|
athos@659
|
22 |
}
|
athos@659
|
23 |
*/
|
athos@659
|
24 |
|
athos@659
|
25 |
|
athos@659
|
26 |
int main()
|
athos@659
|
27 |
{
|
athos@659
|
28 |
|
athos@659
|
29 |
typedef ListGraph::Node Node;
|
athos@659
|
30 |
typedef ListGraph::Edge Edge;
|
athos@659
|
31 |
|
athos@659
|
32 |
ListGraph graph;
|
athos@659
|
33 |
|
athos@659
|
34 |
//Ahuja könyv példája
|
athos@659
|
35 |
|
athos@659
|
36 |
Node s=graph.addNode();
|
athos@659
|
37 |
Node v1=graph.addNode();
|
athos@659
|
38 |
Node v2=graph.addNode();
|
athos@659
|
39 |
Node v3=graph.addNode();
|
athos@659
|
40 |
Node v4=graph.addNode();
|
athos@659
|
41 |
Node v5=graph.addNode();
|
athos@659
|
42 |
Node t=graph.addNode();
|
athos@659
|
43 |
|
athos@659
|
44 |
Edge s_v1=graph.addEdge(s, v1);
|
athos@659
|
45 |
Edge v1_v2=graph.addEdge(v1, v2);
|
athos@659
|
46 |
Edge s_v3=graph.addEdge(s, v3);
|
athos@659
|
47 |
Edge v2_v4=graph.addEdge(v2, v4);
|
athos@659
|
48 |
Edge v2_v5=graph.addEdge(v2, v5);
|
athos@659
|
49 |
Edge v3_v5=graph.addEdge(v3, v5);
|
athos@659
|
50 |
Edge v4_t=graph.addEdge(v4, t);
|
athos@659
|
51 |
Edge v5_t=graph.addEdge(v5, t);
|
athos@659
|
52 |
|
athos@659
|
53 |
|
athos@661
|
54 |
ListGraph::EdgeMap<int> cost(graph);
|
athos@659
|
55 |
|
athos@661
|
56 |
cost.set(s_v1, 6);
|
athos@661
|
57 |
cost.set(v1_v2, 4);
|
athos@661
|
58 |
cost.set(s_v3, 10);
|
athos@661
|
59 |
cost.set(v2_v4, 5);
|
athos@661
|
60 |
cost.set(v2_v5, 1);
|
athos@661
|
61 |
cost.set(v3_v5, 4);
|
athos@661
|
62 |
cost.set(v4_t, 8);
|
athos@661
|
63 |
cost.set(v5_t, 8);
|
athos@659
|
64 |
|
athos@659
|
65 |
/*
|
athos@659
|
66 |
ListGraph::EdgeMap<int> capacity(graph);
|
athos@659
|
67 |
|
athos@659
|
68 |
capacity.set(s_v1, 2);
|
athos@659
|
69 |
capacity.set(v1_v2, 2);
|
athos@659
|
70 |
capacity.set(s_v3, 1);
|
athos@659
|
71 |
capacity.set(v2_v4, 1);
|
athos@659
|
72 |
capacity.set(v2_v5, 1);
|
athos@659
|
73 |
capacity.set(v3_v5, 1);
|
athos@659
|
74 |
capacity.set(v4_t, 1);
|
athos@659
|
75 |
capacity.set(v5_t, 2);
|
athos@659
|
76 |
*/
|
athos@659
|
77 |
|
athos@659
|
78 |
// ConstMap<Edge, int> const1map(1);
|
athos@659
|
79 |
std::cout << "Enhanced capacity scaling algorithm test (for the mincostflow problem)..." << std::endl;
|
athos@659
|
80 |
|
athos@659
|
81 |
MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::NodeMap<int> >
|
athos@661
|
82 |
min_cost_flow_test(graph, cost, supply_demand);
|
athos@659
|
83 |
|
athos@659
|
84 |
int k=1;
|
athos@659
|
85 |
|
athos@659
|
86 |
/*
|
athos@661
|
87 |
check( min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total cost should be 19");
|
athos@659
|
88 |
|
athos@659
|
89 |
check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
|
athos@659
|
90 |
|
athos@659
|
91 |
k=2;
|
athos@659
|
92 |
|
athos@661
|
93 |
check( min_cost_flow_test.run(s,t,k) == 2 && min_cost_flow_test.totalLength() == 41,"Two paths, total cost should be 41");
|
athos@659
|
94 |
|
athos@659
|
95 |
check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
|
athos@659
|
96 |
|
athos@659
|
97 |
|
athos@659
|
98 |
k=4;
|
athos@659
|
99 |
|
athos@661
|
100 |
check( min_cost_flow_test.run(s,t,k) == 3 && min_cost_flow_test.totalLength() == 64,"Three paths, total cost should be 64");
|
athos@659
|
101 |
|
athos@659
|
102 |
check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
|
athos@659
|
103 |
|
athos@659
|
104 |
|
athos@659
|
105 |
cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
|
athos@659
|
106 |
<< endl;
|
athos@659
|
107 |
|
athos@659
|
108 |
return passed ? 0 : 1;
|
athos@659
|
109 |
*/
|
athos@659
|
110 |
}
|