Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
demo/kruskal_demo.cc
changeset 1579 ed7da82bbecf
parent 1435 8e85e6bbefdf
child 1580 a9e4208cf4e3
equal deleted inserted replaced
0:eb73558567bb 1:2a56ea80858a 
       
     1 /* -*- C++ -*-
 
       
     2  * demo/kruskal_demo.cc - Part of LEMON, a generic C++ optimization library
 
       
     3  *
 
       
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 
       
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 
       
     6  *
 
       
     7  * Permission to use, modify and distribute this software is granted
 
       
     8  * provided that this copyright notice appears in all copies. For
 
       
     9  * precise terms see the accompanying LICENSE file.
 
       
    10  *
 
       
    11  * This software is provided "AS IS" with no warranty of any kind,
 
       
    12  * express or implied, and with no claim as to its suitability for any
 
       
    13  * purpose.
 
       
    14  *
 
       
    15  */
 
       
    16 
       
    17 ///\ingroup demos
 
       
    18 ///\file
 
       
    19 ///\brief Minimum weight spanning tree by Kruskal algorithm (demo).
 
       
    20 ///
 
       
    21 ///This demo program shows how to find a minimum weight spannin tree
 
       
    22 ///of a graph by using the Kruskal algorithm. 
       
    23 
     1 #include <iostream>
 
    24 #include <iostream>
 
     2 #include <vector>
 
    25 #include <vector>
 
     3 
    26 
     4 #include <lemon/maps.h>
 
    27 #include <lemon/maps.h>
 
     5 #include <lemon/kruskal.h>
 
    28 #include <lemon/kruskal.h>
 
    15   typedef ListGraph::Node Node;
 
    38   typedef ListGraph::Node Node;
 
    16   typedef ListGraph::Edge Edge;
 
    39   typedef ListGraph::Edge Edge;
 
    17   typedef ListGraph::NodeIt NodeIt;
 
    40   typedef ListGraph::NodeIt NodeIt;
 
    18   typedef ListGraph::EdgeIt EdgeIt;
 
    41   typedef ListGraph::EdgeIt EdgeIt;
 
    19 
    42 
    20   ListGraph G;
 
    43   ListGraph g;
 
       
    44   //Make an example graph g.
 
       
    45   Node s=g.addNode();
 
       
    46   Node v1=g.addNode();
 
       
    47   Node v2=g.addNode();
 
       
    48   Node v3=g.addNode();
 
       
    49   Node v4=g.addNode();
 
       
    50   Node t=g.addNode();
 
       
    51   
       
    52   Edge e1 = g.addEdge(s, v1);
 
       
    53   Edge e2 = g.addEdge(s, v2);
 
       
    54   Edge e3 = g.addEdge(v1, v2);
 
       
    55   Edge e4 = g.addEdge(v2, v1);
 
       
    56   Edge e5 = g.addEdge(v1, v3);
 
       
    57   Edge e6 = g.addEdge(v3, v2);
 
       
    58   Edge e7 = g.addEdge(v2, v4);
 
       
    59   Edge e8 = g.addEdge(v4, v3);
 
       
    60   Edge e9 = g.addEdge(v3, t);
 
       
    61   Edge e10 = g.addEdge(v4, t);
 
    21 
    62 
    22   Node s=G.addNode();
 
    63   //Make the input and output for the kruskal.
 
    23   Node v1=G.addNode();
 
       
    24   Node v2=G.addNode();
 
       
    25   Node v3=G.addNode();
 
       
    26   Node v4=G.addNode();
 
       
    27   Node t=G.addNode();
 
       
    28   
       
    29   Edge e1 = G.addEdge(s, v1);
 
       
    30   Edge e2 = G.addEdge(s, v2);
 
       
    31   Edge e3 = G.addEdge(v1, v2);
 
       
    32   Edge e4 = G.addEdge(v2, v1);
 
       
    33   Edge e5 = G.addEdge(v1, v3);
 
       
    34   Edge e6 = G.addEdge(v3, v2);
 
       
    35   Edge e7 = G.addEdge(v2, v4);
 
       
    36   Edge e8 = G.addEdge(v4, v3);
 
       
    37   Edge e9 = G.addEdge(v3, t);
 
       
    38   Edge e10 = G.addEdge(v4, t);
 
       
    39 
       
    40   typedef ListGraph::EdgeMap<int> ECostMap;
 
    64   typedef ListGraph::EdgeMap<int> ECostMap;
 
    41   typedef ListGraph::EdgeMap<bool> EBoolMap;
 
    65   typedef ListGraph::EdgeMap<bool> EBoolMap;
 
    42 
    66 
    43   ECostMap edge_cost_map(G, 2);
 
    67   ECostMap edge_cost_map(g, 2);
 
    44   EBoolMap tree_map(G);
 
    68   EBoolMap tree_map(g);
 
    45   
       
    46 
    69 
    47   //Test with const map.
 
    70   // Kruskal.
 
    48   std::cout << "The weight of the minimum spanning tree is " << kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)<<std::endl;
 
    71   std::cout << "The weight of the minimum spanning tree by using Kruskal algorithm is " 
       
    72 	    << kruskal(g, ConstMap<ListGraph::Edge,int>(2), tree_map)<<std::endl;
 
    49 
    73 
    50 /*
 
    74   //Make another input (non-uniform costs) for the kruskal.
 
    51   ==10,
 
    75   ECostMap edge_cost_map_2(g);
 
    52 	"Total cost should be 10");
 
    76   edge_cost_map_2.set(e1, -10);
 
    53   //Test with a edge map (filled with uniform costs).
 
    77   edge_cost_map_2.set(e2, -9);
 
    54   check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
 
    78   edge_cost_map_2.set(e3, -8);
 
    55 	"Total cost should be 10");
 
    79   edge_cost_map_2.set(e4, -7);
 
    56 
    80   edge_cost_map_2.set(e5, -6);
 
    57   edge_cost_map.set(e1, -10);
 
    81   edge_cost_map_2.set(e6, -5);
 
    58   edge_cost_map.set(e2, -9);
 
    82   edge_cost_map_2.set(e7, -4);
 
    59   edge_cost_map.set(e3, -8);
 
    83   edge_cost_map_2.set(e8, -3);
 
    60   edge_cost_map.set(e4, -7);
 
    84   edge_cost_map_2.set(e9, -2);
 
    61   edge_cost_map.set(e5, -6);
 
    85   edge_cost_map_2.set(e10, -1);
 
    62   edge_cost_map.set(e6, -5);
 
       
    63   edge_cost_map.set(e7, -4);
 
       
    64   edge_cost_map.set(e8, -3);
 
       
    65   edge_cost_map.set(e9, -2);
 
       
    66   edge_cost_map.set(e10, -1);
 
       
    67 
    86 
    68   vector<Edge> tree_edge_vec;
 
    87   vector<Edge> tree_edge_vec;
 
    69 
    88 
    70   //Test with a edge map and inserter.
 
    89   //Test with non uniform costs and inserter.
 
    71   check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
 
    90   std::cout << "The weight of the minimum spanning tree with non-uniform costs is " << 
    72 				   back_inserter(tree_edge_vec))
 
    91     kruskal(g, edge_cost_map_2, std::back_inserter(tree_edge_vec)) <<std::endl;
 
    73 	==-31,
 
       
    74 	"Total cost should be -31.");
 
       
    75 
    92 
       
    93   //The vector for the edges of the output tree.
 
    76   tree_edge_vec.clear();
 
    94   tree_edge_vec.clear();
 
    77 
    95 
    78   //The above test could also be coded like this:
 
    96   //Test with makeKruskalSequenceOutput and makeKruskalSequenceOutput.
 
    79   check(kruskal(G,
 
       
    80 		makeKruskalMapInput(G, edge_cost_map),
 
       
    81 		makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
 
       
    82 	==-31,
 
       
    83 	"Total cost should be -31.");
 
       
    84 
    97 
    85   check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
 
    98   std::cout << "The weight of the minimum spanning tree again is " << 
       
    99    kruskal(g,makeKruskalMapInput(g,edge_cost_map_2),makeKruskalSequenceOutput(std::back_inserter(tree_edge_vec)))<< std::endl;
 
    86 
   100 
    87   check(tree_edge_vec[0]==e1 &&
 
   101 
    88 	tree_edge_vec[1]==e2 &&
 
       
    89 	tree_edge_vec[2]==e5 &&
 
       
    90 	tree_edge_vec[3]==e7 &&
 
       
    91 	tree_edge_vec[4]==e9,
 
       
    92 	"Wrong tree.");
 
       
    93 */
 
       
    94   return 0;
 
   102   return 0;
 
    95 }
 
   103 }
lemon-0.x