123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108 |
- //=======================================================================
- // 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;
- }
|