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