123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198 |
- //=======================================================================
- // 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_DETAIL_SPARSE_ORDERING_HPP
- #define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
- #include <boost/config.hpp>
- #include <vector>
- #include <queue>
- #include <boost/pending/queue.hpp>
- #include <boost/pending/mutable_queue.hpp>
- #include <boost/graph/graph_traits.hpp>
- #include <boost/graph/breadth_first_search.hpp>
- #include <boost/graph/properties.hpp>
- #include <boost/pending/indirect_cmp.hpp>
- #include <boost/property_map/property_map.hpp>
- #include <boost/bind.hpp>
- #include <boost/graph/iteration_macros.hpp>
- #include <boost/graph/depth_first_search.hpp>
- namespace boost {
- namespace sparse {
- // rcm_queue
- //
- // This is a custom queue type used in the
- // *_ordering algorithms.
- // In addition to the normal queue operations, the
- // rcm_queue provides:
- //
- // int eccentricity() const;
- // value_type spouse() const;
- //
- // yes, it's a bad name...but it works, so use it
- template < class Vertex, class DegreeMap,
- class Container = std::deque<Vertex> >
- class rcm_queue : public std::queue<Vertex, Container> {
- typedef std::queue<Vertex> base;
- public:
- typedef typename base::value_type value_type;
- typedef typename base::size_type size_type;
- /* SGI queue has not had a contructor queue(const Container&) */
- inline rcm_queue(DegreeMap deg)
- : _size(0), Qsize(1), eccen(-1), degree(deg) { }
- inline void pop() {
- if ( !_size )
- Qsize = base::size();
- base::pop();
- if ( _size == Qsize-1 ) {
- _size = 0;
- ++eccen;
- } else
- ++_size;
- }
- inline value_type& front() {
- value_type& u = base::front();
- if ( _size == 0 )
- w = u;
- else if (get(degree,u) < get(degree,w) )
- w = u;
- return u;
- }
- inline const value_type& front() const {
- const value_type& u = base::front();
- if ( _size == 0 )
- w = u;
- else if (get(degree,u) < get(degree,w) )
- w = u;
- return u;
- }
- inline value_type& top() { return front(); }
- inline const value_type& top() const { return front(); }
- inline size_type size() const { return base::size(); }
- inline size_type eccentricity() const { return eccen; }
- inline value_type spouse() const { return w; }
- protected:
- size_type _size;
- size_type Qsize;
- int eccen;
- mutable value_type w;
- DegreeMap degree;
- };
- template <typename Tp, typename Sequence = std::deque<Tp> >
- class sparse_ordering_queue : public boost::queue<Tp, Sequence>{
- public:
- typedef typename Sequence::iterator iterator;
- typedef typename Sequence::reverse_iterator reverse_iterator;
- typedef queue<Tp,Sequence> base;
- typedef typename Sequence::size_type size_type;
- inline iterator begin() { return this->c.begin(); }
- inline reverse_iterator rbegin() { return this->c.rbegin(); }
- inline iterator end() { return this->c.end(); }
- inline reverse_iterator rend() { return this->c.rend(); }
- inline Tp &operator[](int n) { return this->c[n]; }
- inline size_type size() {return this->c.size(); }
- protected:
- //nothing
- };
-
- } // namespace sparse
- // Compute Pseudo peripheral
- //
- // To compute an approximated peripheral for a given vertex.
- // Used in <tt>king_ordering</tt> algorithm.
- //
- template <class Graph, class Vertex, class ColorMap, class DegreeMap>
- Vertex
- pseudo_peripheral_pair(Graph const& G, const Vertex& u, int& ecc,
- ColorMap color, DegreeMap degree)
- {
- typedef typename property_traits<ColorMap>::value_type ColorValue;
- typedef color_traits<ColorValue> Color;
-
- sparse::rcm_queue<Vertex, DegreeMap> Q(degree);
- typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;
- for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
- if (get(color, *ui) != Color::red()) put(color, *ui, Color::white());
- breadth_first_visit(G, u, buffer(Q).color_map(color));
- ecc = Q.eccentricity();
- return Q.spouse();
- }
- // Find a good starting node
- //
- // This is to find a good starting node for the
- // king_ordering algorithm. "good" is in the sense
- // of the ordering generated by RCM.
- //
- template <class Graph, class Vertex, class Color, class Degree>
- Vertex find_starting_node(Graph const& G, Vertex r, Color color, Degree degree)
- {
- Vertex x, y;
- int eccen_r, eccen_x;
- x = pseudo_peripheral_pair(G, r, eccen_r, color, degree);
- y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
- while (eccen_x > eccen_r) {
- r = x;
- eccen_r = eccen_x;
- x = y;
- y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
- }
- return x;
- }
- template <typename Graph>
- class out_degree_property_map
- : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
- out_degree_property_map<Graph> >
- {
- public:
- typedef typename graph_traits<Graph>::vertex_descriptor key_type;
- typedef typename graph_traits<Graph>::degree_size_type value_type;
- typedef value_type reference;
- typedef readable_property_map_tag category;
- out_degree_property_map(const Graph& g) : m_g(g) { }
- value_type operator[](const key_type& v) const {
- return out_degree(v, m_g);
- }
- private:
- const Graph& m_g;
- };
- template <typename Graph>
- inline out_degree_property_map<Graph>
- make_out_degree_map(const Graph& g) {
- return out_degree_property_map<Graph>(g);
- }
- } // namespace boost
- #endif // BOOST_GRAPH_KING_HPP
|