diff -r d8475431bbbb -r 8e85e6bbefdf src/test/kruskal_test.cc --- a/src/test/kruskal_test.cc Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,119 +0,0 @@ -/* -*- C++ -*- - * src/test/kruskal_test.cc - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#include -#include - -#include "test_tools.h" -#include -#include -#include -#include -#include - - -using namespace std; -using namespace lemon; - -void checkCompileKruskal() -{ - concept::WriteMap w; - - kruskalEdgeMap(concept::StaticGraph(), - concept::ReadMap(), - w); -} - -int main() { - - typedef ListGraph::Node Node; - typedef ListGraph::Edge Edge; - typedef ListGraph::NodeIt NodeIt; - typedef ListGraph::EdgeIt EdgeIt; - - ListGraph G; - - Node s=G.addNode(); - Node v1=G.addNode(); - Node v2=G.addNode(); - Node v3=G.addNode(); - Node v4=G.addNode(); - Node t=G.addNode(); - - Edge e1 = G.addEdge(s, v1); - Edge e2 = G.addEdge(s, v2); - Edge e3 = G.addEdge(v1, v2); - Edge e4 = G.addEdge(v2, v1); - Edge e5 = G.addEdge(v1, v3); - Edge e6 = G.addEdge(v3, v2); - Edge e7 = G.addEdge(v2, v4); - Edge e8 = G.addEdge(v4, v3); - Edge e9 = G.addEdge(v3, t); - Edge e10 = G.addEdge(v4, t); - - typedef ListGraph::EdgeMap ECostMap; - typedef ListGraph::EdgeMap EBoolMap; - - ECostMap edge_cost_map(G, 2); - EBoolMap tree_map(G); - - - //Test with const map. - check(kruskalEdgeMap(G, ConstMap(2), tree_map)==10, - "Total cost should be 10"); - //Test with a edge map (filled with uniform costs). - check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10, - "Total cost should be 10"); - - edge_cost_map.set(e1, -10); - edge_cost_map.set(e2, -9); - edge_cost_map.set(e3, -8); - edge_cost_map.set(e4, -7); - edge_cost_map.set(e5, -6); - edge_cost_map.set(e6, -5); - edge_cost_map.set(e7, -4); - edge_cost_map.set(e8, -3); - edge_cost_map.set(e9, -2); - edge_cost_map.set(e10, -1); - - vector tree_edge_vec; - - //Test with a edge map and inserter. - check(kruskalEdgeMap_IteratorOut(G, edge_cost_map, - back_inserter(tree_edge_vec)) - ==-31, - "Total cost should be -31."); - - tree_edge_vec.clear(); - - //The above test could also be coded like this: - check(kruskal(G, - makeKruskalMapInput(G, edge_cost_map), - makeKruskalSequenceOutput(back_inserter(tree_edge_vec))) - ==-31, - "Total cost should be -31."); - - check(tree_edge_vec.size()==5,"The tree should have 5 edges."); - - check(tree_edge_vec[0]==e1 && - tree_edge_vec[1]==e2 && - tree_edge_vec[2]==e5 && - tree_edge_vec[3]==e7 && - tree_edge_vec[4]==e9, - "Wrong tree."); - - return 0; -}