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