test/kruskal_test.cc
changeset 260 c691064dfd4f
parent 171 02f4d5d9bfd7
equal deleted inserted replaced
1:75feb6ecca2d 2:cd8abfe94f78
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    71   Node v1=G.addNode();
    71   Node v1=G.addNode();
    72   Node v2=G.addNode();
    72   Node v2=G.addNode();
    73   Node v3=G.addNode();
    73   Node v3=G.addNode();
    74   Node v4=G.addNode();
    74   Node v4=G.addNode();
    75   Node t=G.addNode();
    75   Node t=G.addNode();
    76   
    76 
    77   Edge e1 = G.addEdge(s, v1);
    77   Edge e1 = G.addEdge(s, v1);
    78   Edge e2 = G.addEdge(s, v2);
    78   Edge e2 = G.addEdge(s, v2);
    79   Edge e3 = G.addEdge(v1, v2);
    79   Edge e3 = G.addEdge(v1, v2);
    80   Edge e4 = G.addEdge(v2, v1);
    80   Edge e4 = G.addEdge(v2, v1);
    81   Edge e5 = G.addEdge(v1, v3);
    81   Edge e5 = G.addEdge(v1, v3);
    88   typedef ListGraph::EdgeMap<int> ECostMap;
    88   typedef ListGraph::EdgeMap<int> ECostMap;
    89   typedef ListGraph::EdgeMap<bool> EBoolMap;
    89   typedef ListGraph::EdgeMap<bool> EBoolMap;
    90 
    90 
    91   ECostMap edge_cost_map(G, 2);
    91   ECostMap edge_cost_map(G, 2);
    92   EBoolMap tree_map(G);
    92   EBoolMap tree_map(G);
    93   
    93 
    94 
    94 
    95   //Test with const map.
    95   //Test with const map.
    96   check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
    96   check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
    97 	"Total cost should be 10");
    97         "Total cost should be 10");
    98   //Test with an edge map (filled with uniform costs).
    98   //Test with an edge map (filled with uniform costs).
    99   check(kruskal(G, edge_cost_map, tree_map)==10,
    99   check(kruskal(G, edge_cost_map, tree_map)==10,
   100 	"Total cost should be 10");
   100         "Total cost should be 10");
   101 
   101 
   102   edge_cost_map.set(e1, -10);
   102   edge_cost_map.set(e1, -10);
   103   edge_cost_map.set(e2, -9);
   103   edge_cost_map.set(e2, -9);
   104   edge_cost_map.set(e3, -8);
   104   edge_cost_map.set(e3, -8);
   105   edge_cost_map.set(e4, -7);
   105   edge_cost_map.set(e4, -7);
   112 
   112 
   113   vector<Edge> tree_edge_vec(5);
   113   vector<Edge> tree_edge_vec(5);
   114 
   114 
   115   //Test with a edge map and inserter.
   115   //Test with a edge map and inserter.
   116   check(kruskal(G, edge_cost_map,
   116   check(kruskal(G, edge_cost_map,
   117 		 tree_edge_vec.begin())
   117                  tree_edge_vec.begin())
   118 	==-31,
   118         ==-31,
   119 	"Total cost should be -31.");
   119         "Total cost should be -31.");
   120   
   120 
   121   tree_edge_vec.clear();
   121   tree_edge_vec.clear();
   122 
   122 
   123   check(kruskal(G, edge_cost_map,
   123   check(kruskal(G, edge_cost_map,
   124 		back_inserter(tree_edge_vec))
   124                 back_inserter(tree_edge_vec))
   125 	==-31,
   125         ==-31,
   126 	"Total cost should be -31.");
   126         "Total cost should be -31.");
   127   
   127 
   128 //   tree_edge_vec.clear();
   128 //   tree_edge_vec.clear();
   129   
   129 
   130 //   //The above test could also be coded like this:
   130 //   //The above test could also be coded like this:
   131 //   check(kruskal(G,
   131 //   check(kruskal(G,
   132 // 		makeKruskalMapInput(G, edge_cost_map),
   132 //                 makeKruskalMapInput(G, edge_cost_map),
   133 // 		makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
   133 //                 makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
   134 // 	==-31,
   134 //         ==-31,
   135 // 	"Total cost should be -31.");
   135 //         "Total cost should be -31.");
   136 
   136 
   137   check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
   137   check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
   138 
   138 
   139   check(tree_edge_vec[0]==e1 &&
   139   check(tree_edge_vec[0]==e1 &&
   140 	tree_edge_vec[1]==e2 &&
   140         tree_edge_vec[1]==e2 &&
   141 	tree_edge_vec[2]==e5 &&
   141         tree_edge_vec[2]==e5 &&
   142 	tree_edge_vec[3]==e7 &&
   142         tree_edge_vec[3]==e7 &&
   143 	tree_edge_vec[4]==e9,
   143         tree_edge_vec[4]==e9,
   144 	"Wrong tree.");
   144         "Wrong tree.");
   145 
   145 
   146   return 0;
   146   return 0;
   147 }
   147 }