test/kruskal_test.cc
changeset 106 9ba2d265e191
child 171 02f4d5d9bfd7
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/kruskal_test.cc	Thu Mar 20 23:06:35 2008 +0000
     1.3 @@ -0,0 +1,149 @@
     1.4 +/* -*- C++ -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library
     1.7 + *
     1.8 + * Copyright (C) 2003-2008
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#include <iostream>
    1.23 +#include <vector>
    1.24 +
    1.25 +#include "test_tools.h"
    1.26 +#include <lemon/maps.h>
    1.27 +#include <lemon/kruskal.h>
    1.28 +#include <lemon/list_graph.h>
    1.29 +
    1.30 +#include <lemon/concepts/maps.h>
    1.31 +#include <lemon/concepts/digraph.h>
    1.32 +#include <lemon/concepts/graph.h>
    1.33 +
    1.34 +
    1.35 +using namespace std;
    1.36 +using namespace lemon;
    1.37 +
    1.38 +void checkCompileKruskal()
    1.39 +{
    1.40 +  concepts::WriteMap<concepts::Digraph::Arc,bool> w;
    1.41 +  concepts::WriteMap<concepts::Graph::Edge,bool> uw;
    1.42 +
    1.43 +  concepts::ReadMap<concepts::Digraph::Arc,int> r;
    1.44 +  concepts::ReadMap<concepts::Graph::Edge,int> ur;
    1.45 +
    1.46 +  concepts::Digraph g;
    1.47 +  concepts::Graph ug;
    1.48 +
    1.49 +  kruskal(g, r, w);
    1.50 +  kruskal(ug, ur, uw);
    1.51 +
    1.52 +  std::vector<std::pair<concepts::Digraph::Arc, int> > rs;
    1.53 +  std::vector<std::pair<concepts::Graph::Edge, int> > urs;
    1.54 +
    1.55 +  kruskal(g, rs, w);
    1.56 +  kruskal(ug, urs, uw);
    1.57 +
    1.58 +  std::vector<concepts::Digraph::Arc> ws;
    1.59 +  std::vector<concepts::Graph::Edge> uws;
    1.60 +
    1.61 +  kruskal(g, r, ws.begin());
    1.62 +  kruskal(ug, ur, uws.begin());
    1.63 +
    1.64 +}
    1.65 +
    1.66 +int main() {
    1.67 +
    1.68 +  typedef ListGraph::Node Node;
    1.69 +  typedef ListGraph::Edge Edge;
    1.70 +  typedef ListGraph::NodeIt NodeIt;
    1.71 +  typedef ListGraph::ArcIt ArcIt;
    1.72 +
    1.73 +  ListGraph G;
    1.74 +
    1.75 +  Node s=G.addNode();
    1.76 +  Node v1=G.addNode();
    1.77 +  Node v2=G.addNode();
    1.78 +  Node v3=G.addNode();
    1.79 +  Node v4=G.addNode();
    1.80 +  Node t=G.addNode();
    1.81 +  
    1.82 +  Edge e1 = G.addEdge(s, v1);
    1.83 +  Edge e2 = G.addEdge(s, v2);
    1.84 +  Edge e3 = G.addEdge(v1, v2);
    1.85 +  Edge e4 = G.addEdge(v2, v1);
    1.86 +  Edge e5 = G.addEdge(v1, v3);
    1.87 +  Edge e6 = G.addEdge(v3, v2);
    1.88 +  Edge e7 = G.addEdge(v2, v4);
    1.89 +  Edge e8 = G.addEdge(v4, v3);
    1.90 +  Edge e9 = G.addEdge(v3, t);
    1.91 +  Edge e10 = G.addEdge(v4, t);
    1.92 +
    1.93 +  typedef ListGraph::EdgeMap<int> ECostMap;
    1.94 +  typedef ListGraph::EdgeMap<bool> EBoolMap;
    1.95 +
    1.96 +  ECostMap edge_cost_map(G, 2);
    1.97 +  EBoolMap tree_map(G);
    1.98 +  
    1.99 +
   1.100 +  //Test with const map.
   1.101 +  check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
   1.102 +	"Total cost should be 10");
   1.103 +  //Test with a edge map (filled with uniform costs).
   1.104 +  check(kruskal(G, edge_cost_map, tree_map)==10,
   1.105 +	"Total cost should be 10");
   1.106 +
   1.107 +  edge_cost_map.set(e1, -10);
   1.108 +  edge_cost_map.set(e2, -9);
   1.109 +  edge_cost_map.set(e3, -8);
   1.110 +  edge_cost_map.set(e4, -7);
   1.111 +  edge_cost_map.set(e5, -6);
   1.112 +  edge_cost_map.set(e6, -5);
   1.113 +  edge_cost_map.set(e7, -4);
   1.114 +  edge_cost_map.set(e8, -3);
   1.115 +  edge_cost_map.set(e9, -2);
   1.116 +  edge_cost_map.set(e10, -1);
   1.117 +
   1.118 +  vector<Edge> tree_edge_vec(5);
   1.119 +
   1.120 +  //Test with a edge map and inserter.
   1.121 +  check(kruskal(G, edge_cost_map,
   1.122 +		 tree_edge_vec.begin())
   1.123 +	==-31,
   1.124 +	"Total cost should be -31.");
   1.125 +  
   1.126 +  tree_edge_vec.clear();
   1.127 +
   1.128 +  check(kruskal(G, edge_cost_map,
   1.129 +		back_inserter(tree_edge_vec))
   1.130 +	==-31,
   1.131 +	"Total cost should be -31.");
   1.132 +  
   1.133 +//   tree_edge_vec.clear();
   1.134 +  
   1.135 +//   //The above test could also be coded like this:
   1.136 +//   check(kruskal(G,
   1.137 +// 		makeKruskalMapInput(G, edge_cost_map),
   1.138 +// 		makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
   1.139 +// 	==-31,
   1.140 +// 	"Total cost should be -31.");
   1.141 +
   1.142 +  check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
   1.143 +
   1.144 +  check(tree_edge_vec[0]==e1 &&
   1.145 +	tree_edge_vec[1]==e2 &&
   1.146 +	tree_edge_vec[2]==e5 &&
   1.147 +	tree_edge_vec[3]==e7 &&
   1.148 +	tree_edge_vec[4]==e9,
   1.149 +	"Wrong tree.");
   1.150 +
   1.151 +  return 0;
   1.152 +}