]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/graph/example/kruskal-telephone.cpp
1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
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 //=======================================================================
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.
17 #include <boost/config.hpp>
20 #include <boost/lexical_cast.hpp>
21 #include <boost/graph/graphviz.hpp>
22 #include <boost/graph/kruskal_min_spanning_tree.hpp>
27 using namespace boost
;
29 read_graphviz("figs/telephone-network.dot", g_dot
);
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
);
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
));
47 property_map
< Graph
, edge_weight_t
>::type weight
= get(edge_weight
, g
);
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
;
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";
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
);