COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/kruskal_test.cc @ 810:e9fbc747ca47

Last change on this file since 810:e9fbc747ca47 was 810:e9fbc747ca47, checked in by Alpar Juttner, 16 years ago

Kruskal alg. (src/hugo/kruskal.h, src/test/kruskal_test.cc) is (almost) done.

  • Some input adaptor is still missing.
  • The class and function names should be revised.
  • Docs still needs some improvement.
File size: 2.2 KB
Line 
1#include <iostream>
2#include <vector>
3
4#include "test_tools.h"
5#include <hugo/maps.h>
6#include <hugo/kruskal.h>
7#include <hugo/list_graph.h>
8#include <hugo/skeletons/maps.h>
9#include <hugo/skeletons/graph.h>
10
11
12using namespace std;
13using namespace hugo;
14
15void checkCompileKruskal()
16{
17  skeleton::WriteMap<skeleton::StaticGraphSkeleton::Edge,bool> w;
18
19  kruskalEdgeMap(skeleton::StaticGraphSkeleton(),
20                 skeleton::ReadMap<skeleton::StaticGraphSkeleton::Edge,int>(),
21                 w);
22}
23
24int main() {
25
26  typedef ListGraph::Node Node;
27  typedef ListGraph::Edge Edge;
28  typedef ListGraph::NodeIt NodeIt;
29  typedef ListGraph::EdgeIt EdgeIt;
30
31  ListGraph G;
32
33  Node s=G.addNode();
34  Node v1=G.addNode();
35  Node v2=G.addNode();
36  Node v3=G.addNode();
37  Node v4=G.addNode();
38  Node t=G.addNode();
39 
40  Edge e1 = G.addEdge(s, v1);
41  Edge e2 = G.addEdge(s, v2);
42  Edge e3 = G.addEdge(v1, v2);
43  Edge e4 = G.addEdge(v2, v1);
44  Edge e5 = G.addEdge(v1, v3);
45  Edge e6 = G.addEdge(v3, v2);
46  Edge e7 = G.addEdge(v2, v4);
47  Edge e8 = G.addEdge(v4, v3);
48  Edge e9 = G.addEdge(v3, t);
49  Edge e10 = G.addEdge(v4, t);
50
51  typedef ListGraph::EdgeMap<int> ECostMap;
52  typedef ListGraph::EdgeMap<bool> EBoolMap;
53
54  ECostMap edge_cost_map(G, 2);
55  EBoolMap tree_map(G);
56 
57
58  //Test with const map.
59  check(kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
60        "Total cost should be 10");
61  //Test with a edge map (filled with uniform costs).
62  check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
63        "Total cost should be 10");
64
65  edge_cost_map.set(e1, -10);
66  edge_cost_map.set(e2, -9);
67  edge_cost_map.set(e3, -8);
68  edge_cost_map.set(e4, -7);
69  edge_cost_map.set(e5, -6);
70  edge_cost_map.set(e6, -5);
71  edge_cost_map.set(e7, -4);
72  edge_cost_map.set(e8, -3);
73  edge_cost_map.set(e9, -2);
74  edge_cost_map.set(e10, -1);
75
76  vector<Edge> tree_edge_vec;
77
78  //Test with a edge map and inserter.
79  check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
80                                   back_inserter(tree_edge_vec))
81        ==-31,
82        "Total cost should be -31.");
83
84  check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
85
86  check(tree_edge_vec[0]==e1 &&
87        tree_edge_vec[1]==e2 &&
88        tree_edge_vec[2]==e5 &&
89        tree_edge_vec[3]==e7 &&
90        tree_edge_vec[4]==e9,
91        "Wrong tree.");
92
93  return 0;
94}
Note: See TracBrowser for help on using the repository browser.