127 lines
3.8 KiB
C++
127 lines
3.8 KiB
C++
//=======================================================================
|
|
// 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;
|
|
}
|