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; |
---|
28 | total_length_visitor(D& len, Distance d) |
---|
29 | : _total_length(len), _distance(d) { } |
---|
30 | template <class Vertex, class Graph> |
---|
31 | 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 | |
---|
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 | } |
---|