Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/example/miles_span.cpp @ 12

Last change on this file since 12 was 12, checked in by landauf, 17 years ago

added boost

File size: 3.4 KB
Line 
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.
25template <class Distance>
26struct 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
38int 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}
Note: See TracBrowser for help on using the repository browser.