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 typedef typename boost::property_traits<Distance>::value_type D;
total_length_visitortotal_length_visitor28 total_length_visitor(D& len, Distance d)
29 : _total_length(len), _distance(d) { }
30 template <class Vertex, class Graph>
finish_vertextotal_length_visitor31 inline void finish_vertex(Vertex s, Graph& g) {
32 _total_length += boost::get(_distance, s);
33 }
34 D& _total_length;
35 Distance _distance;
36 };
37
main(int argc,char * argv[])38 int main(int argc, char* argv[])
39 {
40 using namespace boost;
41 Graph* g;
42
43 unsigned long n = 100;
44 unsigned long n_weight = 0;
45 unsigned long w_weight = 0;
46 unsigned long p_weight = 0;
47 unsigned long d = 10;
48 long s = 0;
49 unsigned long r = 1;
50 char* file_name = NULL;
51
52 while(--argc){
53 if(sscanf(argv[argc],"-n%lu",&n)==1);
54 else if(sscanf(argv[argc],"-N%lu",&n_weight)==1);
55 else if(sscanf(argv[argc],"-W%lu",&w_weight)==1);
56 else if(sscanf(argv[argc],"-P%lu",&p_weight)==1);
57 else if(sscanf(argv[argc],"-d%lu",&d)==1);
58 else if(sscanf(argv[argc],"-r%lu",&r)==1);
59 else if(sscanf(argv[argc],"-s%ld",&s)==1);
60 else if(strcmp(argv[argc],"-v")==0) verbose = 1;
61 else if(strncmp(argv[argc],"-g",2)==0) file_name = argv[argc]+2;
62 else{
63 fprintf(stderr,
64 "Usage: %s [-nN][-dN][-rN][-sN][-NN][-WN][-PN][-v][-gfoo]\n",
65 argv[0]);
66 return -2;
67 }
68 }
69 if (file_name) r = 1;
70
71 while (r--) {
72 if (file_name)
73 g = restore_graph(file_name);
74 else
75 g = miles(n,n_weight,w_weight,p_weight,0L,d,s);
76
77 if(g == NULL || g->n <= 1) {
78 fprintf(stderr,"Sorry, can't create the graph! (error code %ld)\n",
79 panic_code);
80 return-1;
81 }
82
83 printf("The graph %s has %ld edges,\n", g->id, g->m / 2);
84
85 long sp_length = 0;
86
87 // Use the "z" utility field for distance.
88 typedef property_map<Graph*, z_property<long> >::type Distance;
89 Distance d = get(z_property<long>(), g);
90 // Use the "w" property for parent
91 typedef property_map<Graph*, w_property<Vertex*> >::type Parent;
92 Parent p = get(w_property<Vertex*>(), g);
93 total_length_visitor<Distance> length_vis(sp_length, d);
94
95 prim_minimum_spanning_tree(g, p,
96 distance_map(get(z_property<long>(), g)).
97 weight_map(get(edge_length_t(), g)).
98 // Use the "y" utility field for color
99 color_map(get(y_property<long>(), g)).
100 visitor(length_vis));
101
102 printf(" and its minimum spanning tree has length %ld.\n", sp_length);
103
104 gb_recycle(g);
105 s++;
106 }
107 return 0;
108 }
109