lemon-0.x: src/test/kruskal_test.cc@e9fbc747ca47

     1 #include <iostream>

     2 #include <vector>

     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>

    12 using namespace std;

    13 using namespace hugo;

    15 void checkCompileKruskal()

    16 {

    17   skeleton::WriteMap<skeleton::StaticGraphSkeleton::Edge,bool> w;

    19   kruskalEdgeMap(skeleton::StaticGraphSkeleton(),

    20 		 skeleton::ReadMap<skeleton::StaticGraphSkeleton::Edge,int>(),

    21 		 w);

    22 }

    24 int main() {

    26   typedef ListGraph::Node Node;

    27   typedef ListGraph::Edge Edge;

    28   typedef ListGraph::NodeIt NodeIt;

    29   typedef ListGraph::EdgeIt EdgeIt;

    31   ListGraph G;

    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();

    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);

    51   typedef ListGraph::EdgeMap<int> ECostMap;

    52   typedef ListGraph::EdgeMap<bool> EBoolMap;

    54   ECostMap edge_cost_map(G, 2);

    55   EBoolMap tree_map(G);

    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");

    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);

    76   vector<Edge> tree_edge_vec;

    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.");

    84   check(tree_edge_vec.size()==5,"The tree should have 5 edges.");

    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.");

    93   return 0;

    94 }

author	alpar
	Mon, 06 Sep 2004 17:12:00 +0000
changeset 810	e9fbc747ca47
child 880	9d0bfd35b97c
permissions	-rw-r--r--