]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, | |
3 | // | |
4 | // Distributed under the Boost Software License, Version 1.0. (See | |
5 | // accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | //======================================================================= | |
92f5a8d4 TL |
8 | |
9 | /* | |
10 | IMPORTANT!!! | |
11 | ~~~~~~~~~~~~ | |
12 | This example uses interfaces that have been deprecated and removed from Boost.Grpah. | |
13 | Someone needs to update it, as it does NOT compile. | |
14 | */ | |
15 | ||
16 | ||
7c673cae FG |
17 | #include <boost/config.hpp> |
18 | #include <iostream> | |
19 | #include <fstream> | |
20 | #include <boost/lexical_cast.hpp> | |
21 | #include <boost/graph/graphviz.hpp> | |
22 | #include <boost/graph/kruskal_min_spanning_tree.hpp> | |
23 | ||
24 | int | |
25 | main() | |
26 | { | |
27 | using namespace boost; | |
28 | GraphvizGraph g_dot; | |
29 | read_graphviz("figs/telephone-network.dot", g_dot); | |
30 | ||
31 | typedef adjacency_list < vecS, vecS, undirectedS, no_property, | |
32 | property < edge_weight_t, int > > Graph; | |
33 | Graph g(num_vertices(g_dot)); | |
34 | property_map < GraphvizGraph, edge_attribute_t >::type | |
35 | edge_attr_map = get(edge_attribute, g_dot); | |
36 | graph_traits < GraphvizGraph >::edge_iterator ei, ei_end; | |
37 | for (boost::tie(ei, ei_end) = edges(g_dot); ei != ei_end; ++ei) { | |
38 | int weight = lexical_cast < int >(edge_attr_map[*ei]["label"]); | |
39 | property < edge_weight_t, int >edge_property(weight); | |
40 | add_edge(source(*ei, g_dot), target(*ei, g_dot), edge_property, g); | |
41 | } | |
42 | ||
43 | std::vector < graph_traits < Graph >::edge_descriptor > mst; | |
44 | typedef std::vector < graph_traits < Graph >::edge_descriptor >::size_type size_type; | |
45 | kruskal_minimum_spanning_tree(g, std::back_inserter(mst)); | |
46 | ||
47 | property_map < Graph, edge_weight_t >::type weight = get(edge_weight, g); | |
48 | int total_weight = 0; | |
49 | for (size_type e = 0; e < mst.size(); ++e) | |
50 | total_weight += get(weight, mst[e]); | |
51 | std::cout << "total weight: " << total_weight << std::endl; | |
52 | ||
53 | typedef graph_traits < Graph >::vertex_descriptor Vertex; | |
54 | for (size_type i = 0; i < mst.size(); ++i) { | |
55 | Vertex u = source(mst[i], g), v = target(mst[i], g); | |
56 | edge_attr_map[edge(u, v, g_dot).first]["color"] = "black"; | |
57 | } | |
58 | std::ofstream out("figs/telephone-mst-kruskal.dot"); | |
59 | graph_property < GraphvizGraph, graph_edge_attribute_t >::type & | |
60 | graph_edge_attr_map = get_property(g_dot, graph_edge_attribute); | |
61 | graph_edge_attr_map["color"] = "gray"; | |
62 | graph_edge_attr_map["style"] = "bold"; | |
63 | write_graphviz(out, g_dot); | |
64 | ||
65 | return EXIT_SUCCESS; | |
66 | } |