williamr@2: //======================================================================= williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. williamr@2: // Copyright 2004, 2005 Trustees of Indiana University williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, williamr@2: // Doug Gregor, D. Kevin McGrath williamr@2: // williamr@2: // Distributed under the Boost Software License, Version 1.0. (See williamr@2: // accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: //=======================================================================// williamr@2: #ifndef BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP williamr@2: #define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP williamr@2: williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: williamr@2: namespace boost { williamr@2: williamr@2: namespace sparse { williamr@2: williamr@2: // rcm_queue williamr@2: // williamr@2: // This is a custom queue type used in the williamr@2: // *_ordering algorithms. williamr@2: // In addition to the normal queue operations, the williamr@2: // rcm_queue provides: williamr@2: // williamr@2: // int eccentricity() const; williamr@2: // value_type spouse() const; williamr@2: // williamr@2: williamr@2: // yes, it's a bad name...but it works, so use it williamr@2: template < class Vertex, class DegreeMap, williamr@2: class Container = std::deque > williamr@2: class rcm_queue : public std::queue { williamr@2: typedef std::queue base; williamr@2: public: williamr@2: typedef typename base::value_type value_type; williamr@2: typedef typename base::size_type size_type; williamr@2: williamr@2: /* SGI queue has not had a contructor queue(const Container&) */ williamr@2: inline rcm_queue(DegreeMap deg) williamr@2: : _size(0), Qsize(1), eccen(-1), degree(deg) { } williamr@2: williamr@2: inline void pop() { williamr@2: if ( !_size ) williamr@2: Qsize = base::size(); williamr@2: williamr@2: base::pop(); williamr@2: if ( _size == Qsize-1 ) { williamr@2: _size = 0; williamr@2: ++eccen; williamr@2: } else williamr@2: ++_size; williamr@2: williamr@2: } williamr@2: williamr@2: inline value_type& front() { williamr@2: value_type& u = base::front(); williamr@2: if ( _size == 0 ) williamr@2: w = u; williamr@2: else if (get(degree,u) < get(degree,w) ) williamr@2: w = u; williamr@2: return u; williamr@2: } williamr@2: williamr@2: inline const value_type& front() const { williamr@2: const value_type& u = base::front(); williamr@2: if ( _size == 0 ) williamr@2: w = u; williamr@2: else if (get(degree,u) < get(degree,w) ) williamr@2: w = u; williamr@2: return u; williamr@2: } williamr@2: williamr@2: inline value_type& top() { return front(); } williamr@2: inline const value_type& top() const { return front(); } williamr@2: williamr@2: inline size_type size() const { return base::size(); } williamr@2: williamr@2: inline size_type eccentricity() const { return eccen; } williamr@2: inline value_type spouse() const { return w; } williamr@2: williamr@2: protected: williamr@2: size_type _size; williamr@2: size_type Qsize; williamr@2: int eccen; williamr@2: mutable value_type w; williamr@2: DegreeMap degree; williamr@2: }; williamr@2: williamr@2: williamr@2: template > williamr@2: class sparse_ordering_queue : public boost::queue{ williamr@2: public: williamr@2: typedef typename Sequence::iterator iterator; williamr@2: typedef typename Sequence::reverse_iterator reverse_iterator; williamr@2: typedef queue base; williamr@2: typedef typename Sequence::size_type size_type; williamr@2: williamr@2: inline iterator begin() { return this->c.begin(); } williamr@2: inline reverse_iterator rbegin() { return this->c.rbegin(); } williamr@2: inline iterator end() { return this->c.end(); } williamr@2: inline reverse_iterator rend() { return this->c.rend(); } williamr@2: inline Tp &operator[](int n) { return this->c[n]; } williamr@2: inline size_type size() {return this->c.size(); } williamr@2: protected: williamr@2: //nothing williamr@2: }; williamr@2: williamr@2: } // namespace sparse williamr@2: williamr@2: // Compute Pseudo peripheral williamr@2: // williamr@2: // To compute an approximated peripheral for a given vertex. williamr@2: // Used in king_ordering algorithm. williamr@2: // williamr@2: template williamr@2: Vertex williamr@2: pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc, williamr@2: ColorMap color, DegreeMap degree) williamr@2: { williamr@2: typedef typename property_traits::value_type ColorValue; williamr@2: typedef color_traits Color; williamr@2: williamr@2: sparse::rcm_queue Q(degree); williamr@2: williamr@2: typename boost::graph_traits::vertex_iterator ui, ui_end; williamr@2: for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) williamr@2: if (get(color, *ui) != Color::red()) put(color, *ui, Color::white()); williamr@2: breadth_first_visit(G, u, buffer(Q).color_map(color)); williamr@2: williamr@2: ecc = Q.eccentricity(); williamr@2: return Q.spouse(); williamr@2: } williamr@2: williamr@2: // Find a good starting node williamr@2: // williamr@2: // This is to find a good starting node for the williamr@2: // king_ordering algorithm. "good" is in the sense williamr@2: // of the ordering generated by RCM. williamr@2: // williamr@2: template williamr@2: Vertex find_starting_node(Graph& G, Vertex r, Color color, Degree degree) williamr@2: { williamr@2: Vertex x, y; williamr@2: int eccen_r, eccen_x; williamr@2: williamr@2: x = pseudo_peripheral_pair(G, r, eccen_r, color, degree); williamr@2: y = pseudo_peripheral_pair(G, x, eccen_x, color, degree); williamr@2: williamr@2: while (eccen_x > eccen_r) { williamr@2: r = x; williamr@2: eccen_r = eccen_x; williamr@2: x = y; williamr@2: y = pseudo_peripheral_pair(G, x, eccen_x, color, degree); williamr@2: } williamr@2: return x; williamr@2: } williamr@2: williamr@2: template williamr@2: class out_degree_property_map williamr@2: : public put_get_helper::degree_size_type, williamr@2: out_degree_property_map > williamr@2: { williamr@2: public: williamr@2: typedef typename graph_traits::vertex_descriptor key_type; williamr@2: typedef typename graph_traits::degree_size_type value_type; williamr@2: typedef value_type reference; williamr@2: typedef readable_property_map_tag category; williamr@2: out_degree_property_map(const Graph& g) : m_g(g) { } williamr@2: value_type operator[](const key_type& v) const { williamr@2: return out_degree(v, m_g); williamr@2: } williamr@2: private: williamr@2: const Graph& m_g; williamr@2: }; williamr@2: template williamr@2: inline out_degree_property_map williamr@2: make_out_degree_map(const Graph& g) { williamr@2: return out_degree_property_map(g); williamr@2: } williamr@2: williamr@2: } // namespace boost williamr@2: williamr@2: williamr@2: #endif // BOOST_GRAPH_KING_HPP