kru_mst.hpp

在boost基础上实现 对图的最小生成树实现

/*
 * filename:kru_mst.hpp
 * src: d:\vc71\boost-1_31_0\work\src\kruskal_mst\
 * date: 29/8 2004
 * function: my own implementation of the kruskal mst algorithm
 * */
#include <vector>
#include <queue>
#include <boost/property_map.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/pending/indirect_cmp.hpp>

namespace boost{
	/* the core of the kruskal algorithm */
	template<class Graph, class OutputIterator, class Rank, class Parent, class Weight>	
	void kru_mst_impl(const Graph& g, OutputIterator spanning_tree_edges, Rank rank, Parent parent, Weight weight){
		typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
		typedef typename graph_traits<Graph>::edge_descriptor Edge;
		typedef typename graph_traits<Graph>::edge_iterator Edge_iter;
		typedef typename graph_traits<Graph>::vertex_iterator Vertex_iter;
		typedef typename property_traits<Weight>::value_type W_value;
		disjoint_sets<Rank, Parent> dsets(rank, parent);
		Vertex_iter vi,vi_end;	
		for(tie(vi,vi_end) = vertices(g);vi != vi_end;++vi)
			dsets.make_set(*vi);
		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);
		Edge_iter ei,ei_end;
		for(tie(ei,ei_end) = edges(g);ei != ei_end;++ei)
			Q.push(*ei);
		/*
		 * we output the content of the priority_queue Q here
		 * */
		while(!Q.empty()){
			Edge e = Q.top();
			std::cout << "(" << source(e, g) << "," <<  target(e, g) << ")" << "'s weight is " << 
				get(edge_weight,g)[e] << std::endl;
			Q.pop();
		}
		/*
		 * in fact, the content of the Q has been cleared, so we will restore it after the display
		 * (would be improved later)
		 * */
		for(tie(ei,ei_end) = edges(g);ei != ei_end;++ei)
			Q.push(*ei);
		/*
		 * now,we will compute the mst according to the Q and dsets
		 * */
		Vertex u,v;
		while(!Q.empty()){
			Edge e = Q.top();
			Q.pop();
			u = dsets.find_set(source(e, g));	
			v = dsets.find_set(target(e, g));	
			if(u != v){
			 	*spanning_tree_edges++ = e;	
				dsets.link(u, v);
//				dsets.union_set(u, v);
			}
		}
	}
	/* the application of the kruskal_mst() */
	template<class Graph, class OutputIterator>
	inline void	
	kru_mst(const Graph& g, OutputIterator spanning_stree_edges){
		typedef typename graph_traits<Graph>::vertices_size_type size_type;
		typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
		size_type n = num_vertices(g);
		std::vector<size_type> rank_map(n);
		std::vector<Vertex> parent_map(n);
		kru_mst_impl(g, spanning_stree_edges,
				make_iterator_property_map(rank_map.begin(), get(vertex_index, g), rank_map[0]),
				make_iterator_property_map(parent_map.begin(), get(vertex_index, g),parent_map[0]),
				get(edge_weight, g)
				);
	}
}