alpar@906
|
1 |
/* -*- C++ -*-
|
alpar@906
|
2 |
* src/test/kruskal_test.cc - Part of HUGOlib, a generic C++ optimization library
|
alpar@906
|
3 |
*
|
alpar@906
|
4 |
* Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@906
|
5 |
* (Egervary Combinatorial Optimization Research Group, EGRES).
|
alpar@906
|
6 |
*
|
alpar@906
|
7 |
* Permission to use, modify and distribute this software is granted
|
alpar@906
|
8 |
* provided that this copyright notice appears in all copies. For
|
alpar@906
|
9 |
* precise terms see the accompanying LICENSE file.
|
alpar@906
|
10 |
*
|
alpar@906
|
11 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@906
|
12 |
* express or implied, and with no claim as to its suitability for any
|
alpar@906
|
13 |
* purpose.
|
alpar@906
|
14 |
*
|
alpar@906
|
15 |
*/
|
alpar@906
|
16 |
|
alpar@810
|
17 |
#include <iostream>
|
alpar@810
|
18 |
#include <vector>
|
alpar@810
|
19 |
|
alpar@810
|
20 |
#include "test_tools.h"
|
alpar@810
|
21 |
#include <hugo/maps.h>
|
alpar@810
|
22 |
#include <hugo/kruskal.h>
|
alpar@810
|
23 |
#include <hugo/list_graph.h>
|
alpar@810
|
24 |
#include <hugo/skeletons/maps.h>
|
alpar@810
|
25 |
#include <hugo/skeletons/graph.h>
|
alpar@810
|
26 |
|
alpar@810
|
27 |
|
alpar@810
|
28 |
using namespace std;
|
alpar@810
|
29 |
using namespace hugo;
|
alpar@810
|
30 |
|
alpar@810
|
31 |
void checkCompileKruskal()
|
alpar@810
|
32 |
{
|
alpar@880
|
33 |
skeleton::WriteMap<skeleton::StaticGraph::Edge,bool> w;
|
alpar@810
|
34 |
|
alpar@880
|
35 |
kruskalEdgeMap(skeleton::StaticGraph(),
|
alpar@880
|
36 |
skeleton::ReadMap<skeleton::StaticGraph::Edge,int>(),
|
alpar@810
|
37 |
w);
|
alpar@810
|
38 |
}
|
alpar@810
|
39 |
|
alpar@810
|
40 |
int main() {
|
alpar@810
|
41 |
|
alpar@810
|
42 |
typedef ListGraph::Node Node;
|
alpar@810
|
43 |
typedef ListGraph::Edge Edge;
|
alpar@810
|
44 |
typedef ListGraph::NodeIt NodeIt;
|
alpar@810
|
45 |
typedef ListGraph::EdgeIt EdgeIt;
|
alpar@810
|
46 |
|
alpar@810
|
47 |
ListGraph G;
|
alpar@810
|
48 |
|
alpar@810
|
49 |
Node s=G.addNode();
|
alpar@810
|
50 |
Node v1=G.addNode();
|
alpar@810
|
51 |
Node v2=G.addNode();
|
alpar@810
|
52 |
Node v3=G.addNode();
|
alpar@810
|
53 |
Node v4=G.addNode();
|
alpar@810
|
54 |
Node t=G.addNode();
|
alpar@810
|
55 |
|
alpar@810
|
56 |
Edge e1 = G.addEdge(s, v1);
|
alpar@810
|
57 |
Edge e2 = G.addEdge(s, v2);
|
alpar@810
|
58 |
Edge e3 = G.addEdge(v1, v2);
|
alpar@810
|
59 |
Edge e4 = G.addEdge(v2, v1);
|
alpar@810
|
60 |
Edge e5 = G.addEdge(v1, v3);
|
alpar@810
|
61 |
Edge e6 = G.addEdge(v3, v2);
|
alpar@810
|
62 |
Edge e7 = G.addEdge(v2, v4);
|
alpar@810
|
63 |
Edge e8 = G.addEdge(v4, v3);
|
alpar@810
|
64 |
Edge e9 = G.addEdge(v3, t);
|
alpar@810
|
65 |
Edge e10 = G.addEdge(v4, t);
|
alpar@810
|
66 |
|
alpar@810
|
67 |
typedef ListGraph::EdgeMap<int> ECostMap;
|
alpar@810
|
68 |
typedef ListGraph::EdgeMap<bool> EBoolMap;
|
alpar@810
|
69 |
|
alpar@810
|
70 |
ECostMap edge_cost_map(G, 2);
|
alpar@810
|
71 |
EBoolMap tree_map(G);
|
alpar@810
|
72 |
|
alpar@810
|
73 |
|
alpar@810
|
74 |
//Test with const map.
|
alpar@810
|
75 |
check(kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
|
alpar@810
|
76 |
"Total cost should be 10");
|
alpar@810
|
77 |
//Test with a edge map (filled with uniform costs).
|
alpar@810
|
78 |
check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
|
alpar@810
|
79 |
"Total cost should be 10");
|
alpar@810
|
80 |
|
alpar@810
|
81 |
edge_cost_map.set(e1, -10);
|
alpar@810
|
82 |
edge_cost_map.set(e2, -9);
|
alpar@810
|
83 |
edge_cost_map.set(e3, -8);
|
alpar@810
|
84 |
edge_cost_map.set(e4, -7);
|
alpar@810
|
85 |
edge_cost_map.set(e5, -6);
|
alpar@810
|
86 |
edge_cost_map.set(e6, -5);
|
alpar@810
|
87 |
edge_cost_map.set(e7, -4);
|
alpar@810
|
88 |
edge_cost_map.set(e8, -3);
|
alpar@810
|
89 |
edge_cost_map.set(e9, -2);
|
alpar@810
|
90 |
edge_cost_map.set(e10, -1);
|
alpar@810
|
91 |
|
alpar@810
|
92 |
vector<Edge> tree_edge_vec;
|
alpar@810
|
93 |
|
alpar@810
|
94 |
//Test with a edge map and inserter.
|
alpar@810
|
95 |
check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
|
alpar@810
|
96 |
back_inserter(tree_edge_vec))
|
alpar@810
|
97 |
==-31,
|
alpar@810
|
98 |
"Total cost should be -31.");
|
alpar@810
|
99 |
|
klao@885
|
100 |
tree_edge_vec.clear();
|
klao@885
|
101 |
|
klao@885
|
102 |
//The above test could also be coded like this:
|
klao@885
|
103 |
check(kruskal(G,
|
klao@885
|
104 |
makeKruskalMapInput(G, edge_cost_map),
|
klao@885
|
105 |
makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
|
klao@885
|
106 |
==-31,
|
klao@885
|
107 |
"Total cost should be -31.");
|
klao@885
|
108 |
|
alpar@810
|
109 |
check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
|
alpar@810
|
110 |
|
alpar@810
|
111 |
check(tree_edge_vec[0]==e1 &&
|
alpar@810
|
112 |
tree_edge_vec[1]==e2 &&
|
alpar@810
|
113 |
tree_edge_vec[2]==e5 &&
|
alpar@810
|
114 |
tree_edge_vec[3]==e7 &&
|
alpar@810
|
115 |
tree_edge_vec[4]==e9,
|
alpar@810
|
116 |
"Wrong tree.");
|
alpar@810
|
117 |
|
alpar@810
|
118 |
return 0;
|
alpar@810
|
119 |
}
|