third_party/boost/include/boost/graph/king_ordering.hpp - webm/webmlive - Git at Google

 //=======================================================================
 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
 // Copyright 2004, 2005 Trustees of Indiana University
 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
 //          Doug Gregor, D. Kevin McGrath
 //
 // Distributed under the Boost Software License, Version 1.0. (See
 // accompanying file LICENSE_1_0.txt or copy at
 // http://www.boost.org/LICENSE_1_0.txt)
 //=======================================================================//
 #ifndef BOOST_GRAPH_KING_HPP
 #define BOOST_GRAPH_KING_HPP

 #include <boost/config.hpp>
 #include <boost/graph/detail/sparse_ordering.hpp>
 #include <boost/graph/graph_utility.hpp>

 /*
   King Algorithm for matrix reordering
 */

 namespace boost {
   namespace detail {
     template<typename OutputIterator, typename Buffer, typename Compare,
              typename PseudoDegreeMap, typename VecMap, typename VertexIndexMap>
     class bfs_king_visitor:public default_bfs_visitor
     {
     public:
       bfs_king_visitor(OutputIterator *iter, Buffer *b, Compare compare,
                        PseudoDegreeMap deg, std::vector<int> loc, VecMap color,
                        VertexIndexMap vertices):
         permutation(iter), Qptr(b), degree(deg), comp(compare),
         Qlocation(loc), colors(color), vertex_map(vertices) { }

       template <typename Vertex, typename Graph>
       void finish_vertex(Vertex, Graph& g) {
         typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
         Vertex v, w;

         typedef typename std::deque<Vertex>::iterator iterator;
         typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;

         reverse_iterator rend = Qptr->rend()-index_begin;
         reverse_iterator rbegin = Qptr->rbegin();


         //heap the vertices already there
         std::make_heap(rbegin, rend, boost::bind<bool>(comp, _2, _1));

         unsigned i = 0;

         for(i = index_begin; i != Qptr->size(); ++i){
           colors[get(vertex_map, (*Qptr)[i])] = 1;
           Qlocation[get(vertex_map, (*Qptr)[i])] = i;
         }

         i = 0;

         for( ; rbegin != rend; rend--){
           percolate_down<Vertex>(i);
           w = (*Qptr)[index_begin+i];
           for (boost::tie(ei, ei_end) = out_edges(w, g); ei != ei_end; ++ei) {
             v = target(*ei, g);
             put(degree, v, get(degree, v) - 1);

             if (colors[get(vertex_map, v)] == 1) {
               percolate_up<Vertex>(get(vertex_map, v), i);
             }
           }

           colors[get(vertex_map, w)] = 0;
           i++;
         }
       }

       template <typename Vertex, typename Graph>
       void examine_vertex(Vertex u, const Graph&) {

         *(*permutation)++ = u;
         index_begin = Qptr->size();

       }
     protected:


       //this function replaces pop_heap, and tracks state information
       template <typename Vertex>
       void percolate_down(int offset){
         typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;

         int heap_last = index_begin + offset;
         int heap_first = Qptr->size() - 1;

         //pop_heap functionality:
         //swap first, last
         std::swap((*Qptr)[heap_last], (*Qptr)[heap_first]);

         //swap in the location queue
         std::swap(Qlocation[heap_first], Qlocation[heap_last]);

         //set drifter, children
         int drifter = heap_first;
         int drifter_heap = Qptr->size() - drifter;

         int right_child_heap = drifter_heap * 2 + 1;
         int right_child = Qptr->size() - right_child_heap;

         int left_child_heap = drifter_heap * 2;
         int left_child = Qptr->size() - left_child_heap;

         //check that we are staying in the heap
         bool valid = (right_child < heap_last) ? false : true;

         //pick smallest child of drifter, and keep in mind there might only be left child
         int smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree,(*Qptr)[right_child])) ?
           right_child : left_child;

         while(valid && smallest_child < heap_last && comp((*Qptr)[drifter], (*Qptr)[smallest_child])){

           //if smallest child smaller than drifter, swap them
           std::swap((*Qptr)[smallest_child], (*Qptr)[drifter]);
           std::swap(Qlocation[drifter], Qlocation[smallest_child]);

           //update the values, run again, as necessary
           drifter = smallest_child;
           drifter_heap = Qptr->size() - drifter;

           right_child_heap = drifter_heap * 2 + 1;
           right_child = Qptr->size() - right_child_heap;

           left_child_heap = drifter_heap * 2;
           left_child = Qptr->size() - left_child_heap;

           valid = (right_child < heap_last) ? false : true;

           smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree,(*Qptr)[right_child])) ?
             right_child : left_child;
         }

       }


       // this is like percolate down, but we always compare against the
       // parent, as there is only a single choice
       template <typename Vertex>
       void percolate_up(int vertex, int offset){

         int child_location = Qlocation[vertex];
         int heap_child_location = Qptr->size() - child_location;
         int heap_parent_location = (int)(heap_child_location/2);
         unsigned parent_location = Qptr->size() - heap_parent_location;

         bool valid = (heap_parent_location != 0 && child_location > index_begin + offset &&
                       parent_location < Qptr->size());

         while(valid && comp((*Qptr)[child_location], (*Qptr)[parent_location])){

           //swap in the heap
           std::swap((*Qptr)[child_location], (*Qptr)[parent_location]);

           //swap in the location queue
           std::swap(Qlocation[child_location], Qlocation[parent_location]);

           child_location = parent_location;
           heap_child_location = heap_parent_location;
           heap_parent_location = (int)(heap_child_location/2);
           parent_location = Qptr->size() - heap_parent_location;
           valid = (heap_parent_location != 0 && child_location > index_begin + offset);
         }
       }

       OutputIterator *permutation;
       int index_begin;
       Buffer *Qptr;
       PseudoDegreeMap degree;
       Compare comp;
       std::vector<int> Qlocation;
       VecMap colors;
       VertexIndexMap vertex_map;
     };


   } // namespace detail


   template<class Graph, class OutputIterator, class ColorMap, class DegreeMap,
            typename VertexIndexMap>
   OutputIterator
   king_ordering(const Graph& g,
                 std::deque< typename graph_traits<Graph>::vertex_descriptor >
                   vertex_queue,
                 OutputIterator permutation,
                 ColorMap color, DegreeMap degree,
                 VertexIndexMap index_map)
   {
     typedef typename property_traits<DegreeMap>::value_type ds_type;
     typedef typename property_traits<ColorMap>::value_type ColorValue;
     typedef color_traits<ColorValue> Color;
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
     typedef iterator_property_map<typename std::vector<ds_type>::iterator, VertexIndexMap, ds_type, ds_type&> PseudoDegreeMap;
     typedef indirect_cmp<PseudoDegreeMap, std::less<ds_type> > Compare;
     typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
     typedef typename detail::bfs_king_visitor<OutputIterator, queue, Compare,
       PseudoDegreeMap, std::vector<int>, VertexIndexMap > Visitor;
     typedef typename graph_traits<Graph>::vertices_size_type
       vertices_size_type;
     std::vector<ds_type> pseudo_degree_vec(num_vertices(g));
     PseudoDegreeMap pseudo_degree(pseudo_degree_vec.begin(), index_map);

     typename graph_traits<Graph>::vertex_iterator ui, ui_end;
     queue Q;
     // Copy degree to pseudo_degree
     // initialize the color map
     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){
       put(pseudo_degree, *ui, get(degree, *ui));
       put(color, *ui, Color::white());
     }

     Compare comp(pseudo_degree);
     std::vector<int> colors(num_vertices(g));

     for(vertices_size_type i = 0; i < num_vertices(g); i++)
       colors[i] = 0;

     std::vector<int> loc(num_vertices(g));

     //create the visitor
     Visitor vis(&permutation, &Q, comp, pseudo_degree, loc, colors, index_map);

     while( !vertex_queue.empty() ) {
       Vertex s = vertex_queue.front();
       vertex_queue.pop_front();

       //call BFS with visitor
       breadth_first_visit(g, s, Q, vis, color);
     }

     return permutation;
   }


   // This is the case where only a single starting vertex is supplied.
   template <class Graph, class OutputIterator,
             class ColorMap, class DegreeMap, typename VertexIndexMap>
   OutputIterator
   king_ordering(const Graph& g,
                 typename graph_traits<Graph>::vertex_descriptor s,
                 OutputIterator permutation,
                 ColorMap color, DegreeMap degree, VertexIndexMap index_map)
   {

     std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;
     vertex_queue.push_front( s );
     return king_ordering(g, vertex_queue, permutation, color, degree,
                          index_map);
   }


   template < class Graph, class OutputIterator,
              class ColorMap, class DegreeMap, class VertexIndexMap>
   OutputIterator
   king_ordering(const Graph& G, OutputIterator permutation,
                 ColorMap color, DegreeMap degree, VertexIndexMap index_map)
   {
     if (has_no_vertices(G))
       return permutation;

     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
     typedef typename boost::graph_traits<Graph>::vertex_iterator   VerIter;
     typedef typename property_traits<ColorMap>::value_type ColorValue;
     typedef color_traits<ColorValue> Color;

     std::deque<Vertex>      vertex_queue;

     // Mark everything white
     BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());

     // Find one vertex from each connected component
     BGL_FORALL_VERTICES_T(v, G, Graph) {
       if (get(color, v) == Color::white()) {
         depth_first_visit(G, v, dfs_visitor<>(), color);
         vertex_queue.push_back(v);
       }
     }

     // Find starting nodes for all vertices
     // TBD: How to do this with a directed graph?
     for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();
          i != vertex_queue.end(); ++i)
       *i = find_starting_node(G, *i, color, degree);

     return king_ordering(G, vertex_queue, permutation, color, degree,
                          index_map);
   }

   template<typename Graph, typename OutputIterator, typename VertexIndexMap>
   OutputIterator
   king_ordering(const Graph& G, OutputIterator permutation,
                 VertexIndexMap index_map)
   {
     if (has_no_vertices(G))
       return permutation;

     typedef out_degree_property_map<Graph> DegreeMap;
     std::vector<default_color_type> colors(num_vertices(G));
     return king_ordering(G, permutation,
                          make_iterator_property_map(&colors[0], index_map,
                                                     colors[0]),
                          make_out_degree_map(G), index_map);
   }

   template<typename Graph, typename OutputIterator>
   inline OutputIterator
   king_ordering(const Graph& G, OutputIterator permutation)
   { return king_ordering(G, permutation, get(vertex_index, G)); }

 } // namespace boost


 #endif // BOOST_GRAPH_KING_HPP
	//=======================================================================
	// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
	// Copyright 2004, 2005 Trustees of Indiana University
	// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
	// Doug Gregor, D. Kevin McGrath
	//
	// Distributed under the Boost Software License, Version 1.0. (See
	// accompanying file LICENSE_1_0.txt or copy at
	// http://www.boost.org/LICENSE_1_0.txt)
	//=======================================================================//
	#ifndef BOOST_GRAPH_KING_HPP
	#define BOOST_GRAPH_KING_HPP

	#include <boost/config.hpp>
	#include <boost/graph/detail/sparse_ordering.hpp>
	#include <boost/graph/graph_utility.hpp>

	/*
	King Algorithm for matrix reordering
	*/

	namespace boost {
	namespace detail {
	template<typename OutputIterator, typename Buffer, typename Compare,
	typename PseudoDegreeMap, typename VecMap, typename VertexIndexMap>
	class bfs_king_visitor:public default_bfs_visitor
	{
	public:
	bfs_king_visitor(OutputIterator iter, Buffer b, Compare compare,
	PseudoDegreeMap deg, std::vector<int> loc, VecMap color,
	VertexIndexMap vertices):
	permutation(iter), Qptr(b), degree(deg), comp(compare),
	Qlocation(loc), colors(color), vertex_map(vertices) { }

	template <typename Vertex, typename Graph>
	void finish_vertex(Vertex, Graph& g) {
	typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
	Vertex v, w;

	typedef typename std::deque<Vertex>::iterator iterator;
	typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;

	reverse_iterator rend = Qptr->rend()-index_begin;
	reverse_iterator rbegin = Qptr->rbegin();


	//heap the vertices already there
	std::make_heap(rbegin, rend, boost::bind<bool>(comp, _2, _1));

	unsigned i = 0;

	for(i = index_begin; i != Qptr->size(); ++i){
	colors[get(vertex_map, (*Qptr)[i])] = 1;
	Qlocation[get(vertex_map, (*Qptr)[i])] = i;
	}

	i = 0;

	for( ; rbegin != rend; rend--){
	percolate_down<Vertex>(i);
	w = (*Qptr)[index_begin+i];
	for (boost::tie(ei, ei_end) = out_edges(w, g); ei != ei_end; ++ei) {
	v = target(*ei, g);
	put(degree, v, get(degree, v) - 1);

	if (colors[get(vertex_map, v)] == 1) {
	percolate_up<Vertex>(get(vertex_map, v), i);
	}
	}

	colors[get(vertex_map, w)] = 0;
	i++;
	}
	}

	template <typename Vertex, typename Graph>
	void examine_vertex(Vertex u, const Graph&) {

	(permutation)++ = u;
	index_begin = Qptr->size();

	}
	protected:


	//this function replaces pop_heap, and tracks state information
	template <typename Vertex>
	void percolate_down(int offset){
	typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;

	int heap_last = index_begin + offset;
	int heap_first = Qptr->size() - 1;

	//pop_heap functionality:
	//swap first, last
	std::swap((Qptr)[heap_last], (Qptr)[heap_first]);

	//swap in the location queue
	std::swap(Qlocation[heap_first], Qlocation[heap_last]);

	//set drifter, children
	int drifter = heap_first;
	int drifter_heap = Qptr->size() - drifter;

	int right_child_heap = drifter_heap * 2 + 1;
	int right_child = Qptr->size() - right_child_heap;

	int left_child_heap = drifter_heap * 2;
	int left_child = Qptr->size() - left_child_heap;

	//check that we are staying in the heap
	bool valid = (right_child < heap_last) ? false : true;

	//pick smallest child of drifter, and keep in mind there might only be left child
	int smallest_child = (valid && get(degree, (Qptr)[left_child]) > get(degree,(Qptr)[right_child])) ?
	right_child : left_child;

	while(valid && smallest_child < heap_last && comp((Qptr)[drifter], (Qptr)[smallest_child])){

	//if smallest child smaller than drifter, swap them
	std::swap((Qptr)[smallest_child], (Qptr)[drifter]);
	std::swap(Qlocation[drifter], Qlocation[smallest_child]);

	//update the values, run again, as necessary
	drifter = smallest_child;
	drifter_heap = Qptr->size() - drifter;

	right_child_heap = drifter_heap * 2 + 1;
	right_child = Qptr->size() - right_child_heap;

	left_child_heap = drifter_heap * 2;
	left_child = Qptr->size() - left_child_heap;

	valid = (right_child < heap_last) ? false : true;

	smallest_child = (valid && get(degree, (Qptr)[left_child]) > get(degree,(Qptr)[right_child])) ?
	right_child : left_child;
	}

	}



	// this is like percolate down, but we always compare against the
	// parent, as there is only a single choice
	template <typename Vertex>
	void percolate_up(int vertex, int offset){

	int child_location = Qlocation[vertex];
	int heap_child_location = Qptr->size() - child_location;
	int heap_parent_location = (int)(heap_child_location/2);
	unsigned parent_location = Qptr->size() - heap_parent_location;

	bool valid = (heap_parent_location != 0 && child_location > index_begin + offset &&
	parent_location < Qptr->size());

	while(valid && comp((Qptr)[child_location], (Qptr)[parent_location])){

	//swap in the heap
	std::swap((Qptr)[child_location], (Qptr)[parent_location]);

	//swap in the location queue
	std::swap(Qlocation[child_location], Qlocation[parent_location]);

	child_location = parent_location;
	heap_child_location = heap_parent_location;
	heap_parent_location = (int)(heap_child_location/2);
	parent_location = Qptr->size() - heap_parent_location;
	valid = (heap_parent_location != 0 && child_location > index_begin + offset);
	}
	}

	OutputIterator *permutation;
	int index_begin;
	Buffer *Qptr;
	PseudoDegreeMap degree;
	Compare comp;
	std::vector<int> Qlocation;
	VecMap colors;
	VertexIndexMap vertex_map;
	};


	} // namespace detail


	template<class Graph, class OutputIterator, class ColorMap, class DegreeMap,
	typename VertexIndexMap>
	OutputIterator
	king_ordering(const Graph& g,
	std::deque< typename graph_traits<Graph>::vertex_descriptor >
	vertex_queue,
	OutputIterator permutation,
	ColorMap color, DegreeMap degree,
	VertexIndexMap index_map)
	{
	typedef typename property_traits<DegreeMap>::value_type ds_type;
	typedef typename property_traits<ColorMap>::value_type ColorValue;
	typedef color_traits<ColorValue> Color;
	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
	typedef iterator_property_map<typename std::vector<ds_type>::iterator, VertexIndexMap, ds_type, ds_type&> PseudoDegreeMap;
	typedef indirect_cmp<PseudoDegreeMap, std::less<ds_type> > Compare;
	typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
	typedef typename detail::bfs_king_visitor<OutputIterator, queue, Compare,
	PseudoDegreeMap, std::vector<int>, VertexIndexMap > Visitor;
	typedef typename graph_traits<Graph>::vertices_size_type
	vertices_size_type;
	std::vector<ds_type> pseudo_degree_vec(num_vertices(g));
	PseudoDegreeMap pseudo_degree(pseudo_degree_vec.begin(), index_map);

	typename graph_traits<Graph>::vertex_iterator ui, ui_end;
	queue Q;
	// Copy degree to pseudo_degree
	// initialize the color map
	for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){
	put(pseudo_degree, ui, get(degree, ui));
	put(color, *ui, Color::white());
	}

	Compare comp(pseudo_degree);
	std::vector<int> colors(num_vertices(g));

	for(vertices_size_type i = 0; i < num_vertices(g); i++)
	colors[i] = 0;

	std::vector<int> loc(num_vertices(g));

	//create the visitor
	Visitor vis(&permutation, &Q, comp, pseudo_degree, loc, colors, index_map);

	while( !vertex_queue.empty() ) {
	Vertex s = vertex_queue.front();
	vertex_queue.pop_front();

	//call BFS with visitor
	breadth_first_visit(g, s, Q, vis, color);
	}

	return permutation;
	}


	// This is the case where only a single starting vertex is supplied.
	template <class Graph, class OutputIterator,
	class ColorMap, class DegreeMap, typename VertexIndexMap>
	OutputIterator
	king_ordering(const Graph& g,
	typename graph_traits<Graph>::vertex_descriptor s,
	OutputIterator permutation,
	ColorMap color, DegreeMap degree, VertexIndexMap index_map)
	{

	std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;
	vertex_queue.push_front( s );
	return king_ordering(g, vertex_queue, permutation, color, degree,
	index_map);
	}


	template < class Graph, class OutputIterator,
	class ColorMap, class DegreeMap, class VertexIndexMap>
	OutputIterator
	king_ordering(const Graph& G, OutputIterator permutation,
	ColorMap color, DegreeMap degree, VertexIndexMap index_map)
	{
	if (has_no_vertices(G))
	return permutation;

	typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
	typedef typename boost::graph_traits<Graph>::vertex_iterator VerIter;
	typedef typename property_traits<ColorMap>::value_type ColorValue;
	typedef color_traits<ColorValue> Color;

	std::deque<Vertex> vertex_queue;

	// Mark everything white
	BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());

	// Find one vertex from each connected component
	BGL_FORALL_VERTICES_T(v, G, Graph) {
	if (get(color, v) == Color::white()) {
	depth_first_visit(G, v, dfs_visitor<>(), color);
	vertex_queue.push_back(v);
	}
	}

	// Find starting nodes for all vertices
	// TBD: How to do this with a directed graph?
	for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();
	i != vertex_queue.end(); ++i)
	i = find_starting_node(G, i, color, degree);

	return king_ordering(G, vertex_queue, permutation, color, degree,
	index_map);
	}

	template<typename Graph, typename OutputIterator, typename VertexIndexMap>
	OutputIterator
	king_ordering(const Graph& G, OutputIterator permutation,
	VertexIndexMap index_map)
	{
	if (has_no_vertices(G))
	return permutation;

	typedef out_degree_property_map<Graph> DegreeMap;
	std::vector<default_color_type> colors(num_vertices(G));
	return king_ordering(G, permutation,
	make_iterator_property_map(&colors[0], index_map,
	colors[0]),
	make_out_degree_map(G), index_map);
	}

	template<typename Graph, typename OutputIterator>
	inline OutputIterator
	king_ordering(const Graph& G, OutputIterator permutation)
	{ return king_ordering(G, permutation, get(vertex_index, G)); }

	} // namespace boost


	#endif // BOOST_GRAPH_KING_HPP