test/kruskal_test.cc
changeset 1557 3e8d928e283d
parent 1435 8e85e6bbefdf
child 1875 98698b69a902
equal deleted inserted replaced
0:66e8cad1e26c 1:d544e1386e44
    30 
    30 
    31 void checkCompileKruskal()
    31 void checkCompileKruskal()
    32 {
    32 {
    33   concept::WriteMap<concept::StaticGraph::Edge,bool> w;
    33   concept::WriteMap<concept::StaticGraph::Edge,bool> w;
    34 
    34 
    35   kruskalEdgeMap(concept::StaticGraph(),
    35   kruskal(concept::StaticGraph(),
    36 		 concept::ReadMap<concept::StaticGraph::Edge,int>(),
    36 	  concept::ReadMap<concept::StaticGraph::Edge,int>(),
    37 		 w);
    37 	  w);
    38 }
    38 }
    39 
    39 
    40 int main() {
    40 int main() {
    41 
    41 
    42   typedef ListGraph::Node Node;
    42   typedef ListGraph::Node Node;
    70   ECostMap edge_cost_map(G, 2);
    70   ECostMap edge_cost_map(G, 2);
    71   EBoolMap tree_map(G);
    71   EBoolMap tree_map(G);
    72   
    72   
    73 
    73 
    74   //Test with const map.
    74   //Test with const map.
    75   check(kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
    75   check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
    76 	"Total cost should be 10");
    76 	"Total cost should be 10");
    77   //Test with a edge map (filled with uniform costs).
    77   //Test with a edge map (filled with uniform costs).
    78   check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
    78   check(kruskal(G, edge_cost_map, tree_map)==10,
    79 	"Total cost should be 10");
    79 	"Total cost should be 10");
    80 
    80 
    81   edge_cost_map.set(e1, -10);
    81   edge_cost_map.set(e1, -10);
    82   edge_cost_map.set(e2, -9);
    82   edge_cost_map.set(e2, -9);
    83   edge_cost_map.set(e3, -8);
    83   edge_cost_map.set(e3, -8);
    87   edge_cost_map.set(e7, -4);
    87   edge_cost_map.set(e7, -4);
    88   edge_cost_map.set(e8, -3);
    88   edge_cost_map.set(e8, -3);
    89   edge_cost_map.set(e9, -2);
    89   edge_cost_map.set(e9, -2);
    90   edge_cost_map.set(e10, -1);
    90   edge_cost_map.set(e10, -1);
    91 
    91 
    92   vector<Edge> tree_edge_vec;
    92   vector<Edge> tree_edge_vec(5);
    93 
    93 
    94   //Test with a edge map and inserter.
    94   //Test with a edge map and inserter.
    95   check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
    95   check(kruskal(G, edge_cost_map,
    96 				   back_inserter(tree_edge_vec))
    96 		 tree_edge_vec.begin())
    97 	==-31,
    97 	==-31,
    98 	"Total cost should be -31.");
    98 	"Total cost should be -31.");
    99 
    99   
   100   tree_edge_vec.clear();
   100   tree_edge_vec.clear();
   101 
   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   
   102   //The above test could also be coded like this:
   109   //The above test could also be coded like this:
   103   check(kruskal(G,
   110   check(kruskal(G,
   104 		makeKruskalMapInput(G, edge_cost_map),
   111 		makeKruskalMapInput(G, edge_cost_map),
   105 		makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
   112 		makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
   106 	==-31,
   113 	==-31,