src/test/kruskal_test.cc
author alpar
Mon, 13 Sep 2004 11:24:35 +0000
changeset 835 eb9587f09b42
child 880 9d0bfd35b97c
permissions -rw-r--r--
Remove one remaining range checking.
     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 
    12 using namespace std;
    13 using namespace hugo;
    14 
    15 void 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 
    24 int 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 }