http://www.ousob.com --- Legacy Redefined OuSob - File: /wwwroot/clipx/usr/include/boost/graph/detail/sparse_ordering.hpp

// //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // This file is part of the Boost Graph Library // // You should have received a copy of the License Agreement for the // Boost Graph Library along with the software; see the file LICENSE. // If not, contact Office of Research, University of Notre Dame, Notre // Dame, IN 46556. // // Permission to modify the code and to distribute modified code is // granted, provided the text of this NOTICE is retained, a notice that // the code was modified is included with the above COPYRIGHT NOTICE and // with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE // file is distributed with the modified code. // // LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. // By way of example, but not limitation, Licensor MAKES NO // REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY // PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS // OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS // OR OTHER RIGHTS. //======================================================================= // #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.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> queue; 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& 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 (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& 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