#define BOOST_GRAPH_MST_KRUSKAL_HPP
/*
- *Minimum Spanning Tree
+ *Minimum Spanning Tree
* Kruskal Algorithm
*
*Requirement:
#include <boost/pending/indirect_cmp.hpp>
#include <boost/concept/assert.hpp>
+namespace boost
+{
-namespace boost {
-
- // Kruskal's algorithm for Minimum Spanning Tree
- //
- // This is a greedy algorithm to calculate the Minimum Spanning Tree
- // for an undirected graph with weighted edges. The output will be a
- // set of edges.
- //
+// Kruskal's algorithm for Minimum Spanning Tree
+//
+// This is a greedy algorithm to calculate the Minimum Spanning Tree
+// for an undirected graph with weighted edges. The output will be a
+// set of edges.
+//
- namespace detail {
+namespace detail
+{
- template <class Graph, class OutputIterator,
- class Rank, class Parent, class Weight>
- void
- kruskal_mst_impl(const Graph& G,
- OutputIterator spanning_tree_edges,
- Rank rank, Parent parent, Weight weight)
+ template < class Graph, class OutputIterator, class Rank, class Parent,
+ class Weight >
+ void kruskal_mst_impl(const Graph& G, OutputIterator spanning_tree_edges,
+ Rank rank, Parent parent, Weight weight)
{
- if (num_vertices(G) == 0) return; // Nothing to do in this case
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
- BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
- BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph> ));
- BOOST_CONCEPT_ASSERT(( OutputIteratorConcept<OutputIterator, Edge> ));
- BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<Rank, Vertex> ));
- BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<Parent, Vertex> ));
- BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<Weight, Edge> ));
- typedef typename property_traits<Weight>::value_type W_value;
- typedef typename property_traits<Rank>::value_type R_value;
- typedef typename property_traits<Parent>::value_type P_value;
- BOOST_CONCEPT_ASSERT(( ComparableConcept<W_value> ));
- BOOST_CONCEPT_ASSERT(( ConvertibleConcept<P_value, Vertex> ));
- BOOST_CONCEPT_ASSERT(( IntegerConcept<R_value> ));
-
- disjoint_sets<Rank, Parent> dset(rank, parent);
-
- typename graph_traits<Graph>::vertex_iterator ui, uiend;
- for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui)
- dset.make_set(*ui);
-
- typedef indirect_cmp<Weight, std::greater<W_value> > weight_greater;
- weight_greater wl(weight);
- std::priority_queue<Edge, std::vector<Edge>, weight_greater> Q(wl);
- /*push all edge into Q*/
- typename graph_traits<Graph>::edge_iterator ei, eiend;
- for (boost::tie(ei, eiend) = edges(G); ei != eiend; ++ei)
- Q.push(*ei);
-
- while (! Q.empty()) {
- Edge e = Q.top();
- Q.pop();
- Vertex u = dset.find_set(source(e, G));
- Vertex v = dset.find_set(target(e, G));
- if ( u != v ) {
- *spanning_tree_edges++ = e;
- dset.link(u, v);
+ if (num_vertices(G) == 0)
+ return; // Nothing to do in this case
+ typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
+ typedef typename graph_traits< Graph >::edge_descriptor Edge;
+ BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
+ BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< Graph >));
+ BOOST_CONCEPT_ASSERT((OutputIteratorConcept< OutputIterator, Edge >));
+ BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< Rank, Vertex >));
+ BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< Parent, Vertex >));
+ BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< Weight, Edge >));
+ typedef typename property_traits< Weight >::value_type W_value;
+ typedef typename property_traits< Rank >::value_type R_value;
+ typedef typename property_traits< Parent >::value_type P_value;
+ BOOST_CONCEPT_ASSERT((ComparableConcept< W_value >));
+ BOOST_CONCEPT_ASSERT((ConvertibleConcept< P_value, Vertex >));
+ BOOST_CONCEPT_ASSERT((IntegerConcept< R_value >));
+
+ disjoint_sets< Rank, Parent > dset(rank, parent);
+
+ typename graph_traits< Graph >::vertex_iterator ui, uiend;
+ for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui)
+ dset.make_set(*ui);
+
+ typedef indirect_cmp< Weight, std::greater< W_value > > weight_greater;
+ weight_greater wl(weight);
+ std::priority_queue< Edge, std::vector< Edge >, weight_greater > Q(wl);
+ /*push all edge into Q*/
+ typename graph_traits< Graph >::edge_iterator ei, eiend;
+ for (boost::tie(ei, eiend) = edges(G); ei != eiend; ++ei)
+ Q.push(*ei);
+
+ while (!Q.empty())
+ {
+ Edge e = Q.top();
+ Q.pop();
+ Vertex u = dset.find_set(source(e, G));
+ Vertex v = dset.find_set(target(e, G));
+ if (u != v)
+ {
+ *spanning_tree_edges++ = e;
+ dset.link(u, v);
+ }
}
- }
}
- } // namespace detail
-
- // Named Parameters Variants
-
- template <class Graph, class OutputIterator>
- inline void
- kruskal_minimum_spanning_tree(const Graph& g,
- OutputIterator spanning_tree_edges)
- {
- typedef typename graph_traits<Graph>::vertices_size_type size_type;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
- if (num_vertices(g) == 0) return; // Nothing to do in this case
- typename graph_traits<Graph>::vertices_size_type
- n = num_vertices(g);
- std::vector<size_type> rank_map(n);
- std::vector<vertex_t> pred_map(n);
-
- detail::kruskal_mst_impl
- (g, spanning_tree_edges,
- make_iterator_property_map(rank_map.begin(), get(vertex_index, g), rank_map[0]),
- make_iterator_property_map(pred_map.begin(), get(vertex_index, g), pred_map[0]),
- get(edge_weight, g));
- }
-
- template <class Graph, class OutputIterator, class P, class T, class R>
- inline void
- kruskal_minimum_spanning_tree(const Graph& g,
- OutputIterator spanning_tree_edges,
- const bgl_named_params<P, T, R>& params)
- {
- typedef typename graph_traits<Graph>::vertices_size_type size_type;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
- if (num_vertices(g) == 0) return; // Nothing to do in this case
- typename graph_traits<Graph>::vertices_size_type n;
- n = is_default_param(get_param(params, vertex_rank))
- ? num_vertices(g) : 1;
- std::vector<size_type> rank_map(n);
+} // namespace detail
+
+// Named Parameters Variants
+
+template < class Graph, class OutputIterator >
+inline void kruskal_minimum_spanning_tree(
+ const Graph& g, OutputIterator spanning_tree_edges)
+{
+ typedef typename graph_traits< Graph >::vertices_size_type size_type;
+ typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
+ if (num_vertices(g) == 0)
+ return; // Nothing to do in this case
+ typename graph_traits< Graph >::vertices_size_type n = num_vertices(g);
+ std::vector< size_type > rank_map(n);
+ std::vector< vertex_t > pred_map(n);
+
+ detail::kruskal_mst_impl(g, spanning_tree_edges,
+ make_iterator_property_map(
+ rank_map.begin(), get(vertex_index, g), rank_map[0]),
+ make_iterator_property_map(
+ pred_map.begin(), get(vertex_index, g), pred_map[0]),
+ get(edge_weight, g));
+}
+
+template < class Graph, class OutputIterator, class P, class T, class R >
+inline void kruskal_minimum_spanning_tree(const Graph& g,
+ OutputIterator spanning_tree_edges,
+ const bgl_named_params< P, T, R >& params)
+{
+ typedef typename graph_traits< Graph >::vertices_size_type size_type;
+ typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
+ if (num_vertices(g) == 0)
+ return; // Nothing to do in this case
+ typename graph_traits< Graph >::vertices_size_type n;
+ n = is_default_param(get_param(params, vertex_rank)) ? num_vertices(g) : 1;
+ std::vector< size_type > rank_map(n);
n = is_default_param(get_param(params, vertex_predecessor))
- ? num_vertices(g) : 1;
- std::vector<vertex_t> pred_map(n);
-
- detail::kruskal_mst_impl
- (g, spanning_tree_edges,
- choose_param
- (get_param(params, vertex_rank),
- make_iterator_property_map
- (rank_map.begin(),
- choose_pmap(get_param(params, vertex_index), g, vertex_index), rank_map[0])),
- choose_param
- (get_param(params, vertex_predecessor),
- make_iterator_property_map
- (pred_map.begin(),
- choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
- pred_map[0])),
- choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
- }
-
-} // namespace boost
+ ? num_vertices(g)
+ : 1;
+ std::vector< vertex_t > pred_map(n);
+
+ detail::kruskal_mst_impl(g, spanning_tree_edges,
+ choose_param(get_param(params, vertex_rank),
+ make_iterator_property_map(rank_map.begin(),
+ choose_pmap(get_param(params, vertex_index), g, vertex_index),
+ rank_map[0])),
+ choose_param(get_param(params, vertex_predecessor),
+ make_iterator_property_map(pred_map.begin(),
+ choose_const_pmap(
+ get_param(params, vertex_index), g, vertex_index),
+ pred_map[0])),
+ choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
+}
+} // namespace boost
#endif // BOOST_GRAPH_MST_KRUSKAL_HPP
-
projects / ceph.git / blobdiff