1 //======================================================================= 2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. 3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek 4 // 5 // Distributed under the Boost Software License, Version 1.0. (See 6 // accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 //======================================================================= 9 10 // Sample output: 11 // 12 // The graph miles(100,0,0,0,0,10,0) has 405 edges, 13 // and its minimum spanning tree has length 14467. 14 // 15 16 #include <boost/config.hpp> 17 #include <string.h> 18 #include <stdio.h> 19 #include <boost/graph/stanford_graph.hpp> 20 #include <boost/graph/prim_minimum_spanning_tree.hpp> 21 22 // A visitor class for accumulating the total length of the minimum 23 // spanning tree. The Distance template parameter is for a 24 // PropertyMap. 25 template < class Distance > 26 struct total_length_visitor : public boost::dijkstra_visitor<> 27 { 28 typedef typename boost::property_traits< Distance >::value_type D; total_length_visitortotal_length_visitor29 total_length_visitor(D& len, Distance d) : _total_length(len), _distance(d) 30 { 31 } 32 template < class Vertex, class Graph > finish_vertextotal_length_visitor33 inline void finish_vertex(Vertex s, Graph& g) 34 { 35 _total_length += boost::get(_distance, s); 36 } 37 D& _total_length; 38 Distance _distance; 39 }; 40 main(int argc,char * argv[])41 int main(int argc, char* argv[]) 42 { 43 using namespace boost; 44 Graph* g; 45 46 unsigned long n = 100; 47 unsigned long n_weight = 0; 48 unsigned long w_weight = 0; 49 unsigned long p_weight = 0; 50 unsigned long d = 10; 51 long s = 0; 52 unsigned long r = 1; 53 char* file_name = NULL; 54 55 while (--argc) 56 { 57 if (sscanf(argv[argc], "-n%lu", &n) == 1) 58 ; 59 else if (sscanf(argv[argc], "-N%lu", &n_weight) == 1) 60 ; 61 else if (sscanf(argv[argc], "-W%lu", &w_weight) == 1) 62 ; 63 else if (sscanf(argv[argc], "-P%lu", &p_weight) == 1) 64 ; 65 else if (sscanf(argv[argc], "-d%lu", &d) == 1) 66 ; 67 else if (sscanf(argv[argc], "-r%lu", &r) == 1) 68 ; 69 else if (sscanf(argv[argc], "-s%ld", &s) == 1) 70 ; 71 else if (strcmp(argv[argc], "-v") == 0) 72 verbose = 1; 73 else if (strncmp(argv[argc], "-g", 2) == 0) 74 file_name = argv[argc] + 2; 75 else 76 { 77 fprintf(stderr, 78 "Usage: %s [-nN][-dN][-rN][-sN][-NN][-WN][-PN][-v][-gfoo]\n", 79 argv[0]); 80 return -2; 81 } 82 } 83 if (file_name) 84 r = 1; 85 86 while (r--) 87 { 88 if (file_name) 89 g = restore_graph(file_name); 90 else 91 g = miles(n, n_weight, w_weight, p_weight, 0L, d, s); 92 93 if (g == NULL || g->n <= 1) 94 { 95 fprintf(stderr, "Sorry, can't create the graph! (error code %ld)\n", 96 panic_code); 97 return -1; 98 } 99 100 printf("The graph %s has %ld edges,\n", g->id, g->m / 2); 101 102 long sp_length = 0; 103 104 // Use the "z" utility field for distance. 105 typedef property_map< Graph*, z_property< long > >::type Distance; 106 Distance d = get(z_property< long >(), g); 107 // Use the "w" property for parent 108 typedef property_map< Graph*, w_property< Vertex* > >::type Parent; 109 Parent p = get(w_property< Vertex* >(), g); 110 total_length_visitor< Distance > length_vis(sp_length, d); 111 112 prim_minimum_spanning_tree(g, p, 113 distance_map(get(z_property< long >(), g)) 114 .weight_map(get(edge_length_t(), g)) 115 . 116 // Use the "y" utility field for color 117 color_map(get(y_property< long >(), g)) 118 .visitor(length_vis)); 119 120 printf(" and its minimum spanning tree has length %ld.\n", sp_length); 121 122 gb_recycle(g); 123 s++; 124 } 125 return 0; 126 } 127