1.1 --- a/src/test/kruskal_test.cc Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,119 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/test/kruskal_test.cc - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#include <iostream>
1.21 -#include <vector>
1.22 -
1.23 -#include "test_tools.h"
1.24 -#include <lemon/maps.h>
1.25 -#include <lemon/kruskal.h>
1.26 -#include <lemon/list_graph.h>
1.27 -#include <lemon/concept/maps.h>
1.28 -#include <lemon/concept/graph.h>
1.29 -
1.30 -
1.31 -using namespace std;
1.32 -using namespace lemon;
1.33 -
1.34 -void checkCompileKruskal()
1.35 -{
1.36 - concept::WriteMap<concept::StaticGraph::Edge,bool> w;
1.37 -
1.38 - kruskalEdgeMap(concept::StaticGraph(),
1.39 - concept::ReadMap<concept::StaticGraph::Edge,int>(),
1.40 - w);
1.41 -}
1.42 -
1.43 -int main() {
1.44 -
1.45 - typedef ListGraph::Node Node;
1.46 - typedef ListGraph::Edge Edge;
1.47 - typedef ListGraph::NodeIt NodeIt;
1.48 - typedef ListGraph::EdgeIt EdgeIt;
1.49 -
1.50 - ListGraph G;
1.51 -
1.52 - Node s=G.addNode();
1.53 - Node v1=G.addNode();
1.54 - Node v2=G.addNode();
1.55 - Node v3=G.addNode();
1.56 - Node v4=G.addNode();
1.57 - Node t=G.addNode();
1.58 -
1.59 - Edge e1 = G.addEdge(s, v1);
1.60 - Edge e2 = G.addEdge(s, v2);
1.61 - Edge e3 = G.addEdge(v1, v2);
1.62 - Edge e4 = G.addEdge(v2, v1);
1.63 - Edge e5 = G.addEdge(v1, v3);
1.64 - Edge e6 = G.addEdge(v3, v2);
1.65 - Edge e7 = G.addEdge(v2, v4);
1.66 - Edge e8 = G.addEdge(v4, v3);
1.67 - Edge e9 = G.addEdge(v3, t);
1.68 - Edge e10 = G.addEdge(v4, t);
1.69 -
1.70 - typedef ListGraph::EdgeMap<int> ECostMap;
1.71 - typedef ListGraph::EdgeMap<bool> EBoolMap;
1.72 -
1.73 - ECostMap edge_cost_map(G, 2);
1.74 - EBoolMap tree_map(G);
1.75 -
1.76 -
1.77 - //Test with const map.
1.78 - check(kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
1.79 - "Total cost should be 10");
1.80 - //Test with a edge map (filled with uniform costs).
1.81 - check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
1.82 - "Total cost should be 10");
1.83 -
1.84 - edge_cost_map.set(e1, -10);
1.85 - edge_cost_map.set(e2, -9);
1.86 - edge_cost_map.set(e3, -8);
1.87 - edge_cost_map.set(e4, -7);
1.88 - edge_cost_map.set(e5, -6);
1.89 - edge_cost_map.set(e6, -5);
1.90 - edge_cost_map.set(e7, -4);
1.91 - edge_cost_map.set(e8, -3);
1.92 - edge_cost_map.set(e9, -2);
1.93 - edge_cost_map.set(e10, -1);
1.94 -
1.95 - vector<Edge> tree_edge_vec;
1.96 -
1.97 - //Test with a edge map and inserter.
1.98 - check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
1.99 - back_inserter(tree_edge_vec))
1.100 - ==-31,
1.101 - "Total cost should be -31.");
1.102 -
1.103 - tree_edge_vec.clear();
1.104 -
1.105 - //The above test could also be coded like this:
1.106 - check(kruskal(G,
1.107 - makeKruskalMapInput(G, edge_cost_map),
1.108 - makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
1.109 - ==-31,
1.110 - "Total cost should be -31.");
1.111 -
1.112 - check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
1.113 -
1.114 - check(tree_edge_vec[0]==e1 &&
1.115 - tree_edge_vec[1]==e2 &&
1.116 - tree_edge_vec[2]==e5 &&
1.117 - tree_edge_vec[3]==e7 &&
1.118 - tree_edge_vec[4]==e9,
1.119 - "Wrong tree.");
1.120 -
1.121 - return 0;
1.122 -}