]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // |
2 | //======================================================================= | |
3 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
4 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |
5 | // | |
6 | // Distributed under the Boost Software License, Version 1.0. (See | |
7 | // accompanying file LICENSE_1_0.txt or copy at | |
8 | // http://www.boost.org/LICENSE_1_0.txt) | |
9 | //======================================================================= | |
10 | // | |
11 | #ifndef BOOST_GRAPH_MST_KRUSKAL_HPP | |
12 | #define BOOST_GRAPH_MST_KRUSKAL_HPP | |
13 | ||
14 | /* | |
15 | *Minimum Spanning Tree | |
16 | * Kruskal Algorithm | |
17 | * | |
18 | *Requirement: | |
19 | * undirected graph | |
20 | */ | |
21 | ||
22 | #include <vector> | |
23 | #include <queue> | |
24 | #include <functional> | |
25 | ||
26 | #include <boost/property_map/property_map.hpp> | |
27 | #include <boost/graph/graph_concepts.hpp> | |
28 | #include <boost/graph/named_function_params.hpp> | |
29 | #include <boost/pending/disjoint_sets.hpp> | |
30 | #include <boost/pending/indirect_cmp.hpp> | |
31 | #include <boost/concept/assert.hpp> | |
32 | ||
33 | ||
34 | namespace boost { | |
35 | ||
36 | // Kruskal's algorithm for Minimum Spanning Tree | |
37 | // | |
38 | // This is a greedy algorithm to calculate the Minimum Spanning Tree | |
39 | // for an undirected graph with weighted edges. The output will be a | |
40 | // set of edges. | |
41 | // | |
42 | ||
43 | namespace detail { | |
44 | ||
45 | template <class Graph, class OutputIterator, | |
46 | class Rank, class Parent, class Weight> | |
47 | void | |
48 | kruskal_mst_impl(const Graph& G, | |
49 | OutputIterator spanning_tree_edges, | |
50 | Rank rank, Parent parent, Weight weight) | |
51 | { | |
52 | if (num_vertices(G) == 0) return; // Nothing to do in this case | |
53 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
54 | typedef typename graph_traits<Graph>::edge_descriptor Edge; | |
55 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); | |
56 | BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph> )); | |
57 | BOOST_CONCEPT_ASSERT(( OutputIteratorConcept<OutputIterator, Edge> )); | |
58 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<Rank, Vertex> )); | |
59 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<Parent, Vertex> )); | |
60 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<Weight, Edge> )); | |
61 | typedef typename property_traits<Weight>::value_type W_value; | |
62 | typedef typename property_traits<Rank>::value_type R_value; | |
63 | typedef typename property_traits<Parent>::value_type P_value; | |
64 | BOOST_CONCEPT_ASSERT(( ComparableConcept<W_value> )); | |
65 | BOOST_CONCEPT_ASSERT(( ConvertibleConcept<P_value, Vertex> )); | |
66 | BOOST_CONCEPT_ASSERT(( IntegerConcept<R_value> )); | |
67 | ||
68 | disjoint_sets<Rank, Parent> dset(rank, parent); | |
69 | ||
70 | typename graph_traits<Graph>::vertex_iterator ui, uiend; | |
71 | for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui) | |
72 | dset.make_set(*ui); | |
73 | ||
74 | typedef indirect_cmp<Weight, std::greater<W_value> > weight_greater; | |
75 | weight_greater wl(weight); | |
76 | std::priority_queue<Edge, std::vector<Edge>, weight_greater> Q(wl); | |
77 | /*push all edge into Q*/ | |
78 | typename graph_traits<Graph>::edge_iterator ei, eiend; | |
79 | for (boost::tie(ei, eiend) = edges(G); ei != eiend; ++ei) | |
80 | Q.push(*ei); | |
81 | ||
82 | while (! Q.empty()) { | |
83 | Edge e = Q.top(); | |
84 | Q.pop(); | |
85 | Vertex u = dset.find_set(source(e, G)); | |
86 | Vertex v = dset.find_set(target(e, G)); | |
87 | if ( u != v ) { | |
88 | *spanning_tree_edges++ = e; | |
89 | dset.link(u, v); | |
90 | } | |
91 | } | |
92 | } | |
93 | ||
94 | } // namespace detail | |
95 | ||
96 | // Named Parameters Variants | |
97 | ||
98 | template <class Graph, class OutputIterator> | |
99 | inline void | |
100 | kruskal_minimum_spanning_tree(const Graph& g, | |
101 | OutputIterator spanning_tree_edges) | |
102 | { | |
103 | typedef typename graph_traits<Graph>::vertices_size_type size_type; | |
104 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
105 | if (num_vertices(g) == 0) return; // Nothing to do in this case | |
106 | typename graph_traits<Graph>::vertices_size_type | |
107 | n = num_vertices(g); | |
108 | std::vector<size_type> rank_map(n); | |
109 | std::vector<vertex_t> pred_map(n); | |
110 | ||
111 | detail::kruskal_mst_impl | |
112 | (g, spanning_tree_edges, | |
113 | make_iterator_property_map(rank_map.begin(), get(vertex_index, g), rank_map[0]), | |
114 | make_iterator_property_map(pred_map.begin(), get(vertex_index, g), pred_map[0]), | |
115 | get(edge_weight, g)); | |
116 | } | |
117 | ||
118 | template <class Graph, class OutputIterator, class P, class T, class R> | |
119 | inline void | |
120 | kruskal_minimum_spanning_tree(const Graph& g, | |
121 | OutputIterator spanning_tree_edges, | |
122 | const bgl_named_params<P, T, R>& params) | |
123 | { | |
124 | typedef typename graph_traits<Graph>::vertices_size_type size_type; | |
125 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
126 | if (num_vertices(g) == 0) return; // Nothing to do in this case | |
127 | typename graph_traits<Graph>::vertices_size_type n; | |
128 | n = is_default_param(get_param(params, vertex_rank)) | |
129 | ? num_vertices(g) : 1; | |
130 | std::vector<size_type> rank_map(n); | |
131 | n = is_default_param(get_param(params, vertex_predecessor)) | |
132 | ? num_vertices(g) : 1; | |
133 | std::vector<vertex_t> pred_map(n); | |
134 | ||
135 | detail::kruskal_mst_impl | |
136 | (g, spanning_tree_edges, | |
137 | choose_param | |
138 | (get_param(params, vertex_rank), | |
139 | make_iterator_property_map | |
140 | (rank_map.begin(), | |
141 | choose_pmap(get_param(params, vertex_index), g, vertex_index), rank_map[0])), | |
142 | choose_param | |
143 | (get_param(params, vertex_predecessor), | |
144 | make_iterator_property_map | |
145 | (pred_map.begin(), | |
146 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index), | |
147 | pred_map[0])), | |
148 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight)); | |
149 | } | |
150 | ||
151 | } // namespace boost | |
152 | ||
153 | ||
154 | #endif // BOOST_GRAPH_MST_KRUSKAL_HPP | |
155 |