athos@610
|
1 |
#include <iostream>
|
athos@610
|
2 |
#include <hugo/list_graph.h>
|
athos@610
|
3 |
#include <hugo/minlengthpaths.h>
|
alpar@790
|
4 |
//#include <path.h>
|
athos@611
|
5 |
#include "test_tools.h"
|
athos@610
|
6 |
|
athos@610
|
7 |
using namespace std;
|
athos@610
|
8 |
using namespace hugo;
|
athos@610
|
9 |
|
athos@610
|
10 |
|
athos@610
|
11 |
|
athos@610
|
12 |
bool passed = true;
|
athos@610
|
13 |
|
athos@610
|
14 |
|
athos@610
|
15 |
int main()
|
athos@610
|
16 |
{
|
athos@610
|
17 |
|
athos@610
|
18 |
typedef ListGraph::Node Node;
|
athos@610
|
19 |
typedef ListGraph::Edge Edge;
|
athos@610
|
20 |
|
athos@610
|
21 |
ListGraph graph;
|
athos@610
|
22 |
|
athos@610
|
23 |
//Ahuja könyv példája
|
athos@610
|
24 |
|
athos@610
|
25 |
Node s=graph.addNode();
|
athos@610
|
26 |
Node v1=graph.addNode();
|
athos@610
|
27 |
Node v2=graph.addNode();
|
athos@610
|
28 |
Node v3=graph.addNode();
|
athos@610
|
29 |
Node v4=graph.addNode();
|
athos@610
|
30 |
Node v5=graph.addNode();
|
athos@610
|
31 |
Node t=graph.addNode();
|
athos@610
|
32 |
|
athos@610
|
33 |
Edge s_v1=graph.addEdge(s, v1);
|
athos@610
|
34 |
Edge v1_v2=graph.addEdge(v1, v2);
|
athos@610
|
35 |
Edge s_v3=graph.addEdge(s, v3);
|
athos@610
|
36 |
Edge v2_v4=graph.addEdge(v2, v4);
|
athos@610
|
37 |
Edge v2_v5=graph.addEdge(v2, v5);
|
athos@610
|
38 |
Edge v3_v5=graph.addEdge(v3, v5);
|
athos@610
|
39 |
Edge v4_t=graph.addEdge(v4, t);
|
athos@610
|
40 |
Edge v5_t=graph.addEdge(v5, t);
|
athos@610
|
41 |
|
athos@610
|
42 |
|
athos@610
|
43 |
ListGraph::EdgeMap<int> length(graph);
|
athos@610
|
44 |
|
athos@610
|
45 |
length.set(s_v1, 6);
|
athos@610
|
46 |
length.set(v1_v2, 4);
|
athos@610
|
47 |
length.set(s_v3, 10);
|
athos@610
|
48 |
length.set(v2_v4, 5);
|
athos@610
|
49 |
length.set(v2_v5, 1);
|
athos@610
|
50 |
length.set(v3_v5, 5);
|
athos@610
|
51 |
length.set(v4_t, 8);
|
athos@610
|
52 |
length.set(v5_t, 8);
|
athos@610
|
53 |
|
athos@610
|
54 |
std::cout << "Minlengthpaths algorithm test..." << std::endl;
|
athos@610
|
55 |
|
athos@610
|
56 |
|
athos@610
|
57 |
int k=3;
|
athos@610
|
58 |
MinLengthPaths< ListGraph, ListGraph::EdgeMap<int> >
|
athos@610
|
59 |
surb_test(graph, length);
|
athos@610
|
60 |
|
alpar@791
|
61 |
check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,
|
alpar@791
|
62 |
"Two paths, total length should be 46");
|
athos@610
|
63 |
|
alpar@791
|
64 |
check( surb_test.checkComplementarySlackness(),
|
alpar@791
|
65 |
"Complementary slackness conditions are not met.");
|
athos@610
|
66 |
|
alpar@790
|
67 |
// typedef DirPath<ListGraph> DPath;
|
alpar@790
|
68 |
// DPath P(graph);
|
athos@610
|
69 |
|
athos@610
|
70 |
/*
|
athos@610
|
71 |
surb_test.getPath(P,0);
|
athos@610
|
72 |
check(P.length() == 4, "First path should contain 4 edges.");
|
athos@610
|
73 |
cout<<P.length()<<endl;
|
athos@610
|
74 |
surb_test.getPath(P,1);
|
athos@610
|
75 |
check(P.length() == 3, "Second path: 3 edges.");
|
athos@610
|
76 |
cout<<P.length()<<endl;
|
athos@610
|
77 |
*/
|
athos@610
|
78 |
|
athos@610
|
79 |
k=1;
|
alpar@791
|
80 |
check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,
|
alpar@791
|
81 |
"One path, total length should be 19");
|
athos@610
|
82 |
|
alpar@791
|
83 |
check( surb_test.checkComplementarySlackness(),
|
alpar@791
|
84 |
"Complementary slackness conditions are not met.");
|
athos@610
|
85 |
|
alpar@790
|
86 |
// surb_test.getPath(P,0);
|
alpar@790
|
87 |
// check(P.length() == 4, "First path should contain 4 edges.");
|
athos@610
|
88 |
|
athos@610
|
89 |
cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
|
athos@610
|
90 |
<< endl;
|
athos@610
|
91 |
|
athos@610
|
92 |
return passed ? 0 : 1;
|
athos@610
|
93 |
|
athos@610
|
94 |
}
|