COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/kruskal_test.cc @ 1557:3e8d928e283d

Last change on this file since 1557:3e8d928e283d was 1557:3e8d928e283d, checked in by Alpar Juttner, 14 years ago

Each version of Kruskal is called the same ( kruskal(g,in,out) ) independently
from the input source and the output type.

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