Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Copyright 2004, 2005 Trustees of Indiana University
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
5 // Doug Gregor, D. Kevin McGrath
7 // Distributed under the Boost Software License, Version 1.0. (See
8 // accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 //=======================================================================//
11 #ifndef BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
12 #define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
14 #include <boost/config.hpp>
17 #include <boost/pending/queue.hpp>
18 #include <boost/pending/mutable_queue.hpp>
19 #include <boost/graph/graph_traits.hpp>
20 #include <boost/graph/breadth_first_search.hpp>
21 #include <boost/graph/properties.hpp>
22 #include <boost/pending/indirect_cmp.hpp>
23 #include <boost/property_map.hpp>
24 #include <boost/bind.hpp>
25 #include <boost/graph/iteration_macros.hpp>
26 #include <boost/graph/depth_first_search.hpp>
34 // This is a custom queue type used in the
35 // *_ordering algorithms.
36 // In addition to the normal queue operations, the
37 // rcm_queue provides:
39 // int eccentricity() const;
40 // value_type spouse() const;
43 // yes, it's a bad name...but it works, so use it
44 template < class Vertex, class DegreeMap,
45 class Container = std::deque<Vertex> >
46 class rcm_queue : public std::queue<Vertex, Container> {
47 typedef std::queue<Vertex> base;
49 typedef typename base::value_type value_type;
50 typedef typename base::size_type size_type;
52 /* SGI queue has not had a contructor queue(const Container&) */
53 inline rcm_queue(DegreeMap deg)
54 : _size(0), Qsize(1), eccen(-1), degree(deg) { }
61 if ( _size == Qsize-1 ) {
69 inline value_type& front() {
70 value_type& u = base::front();
73 else if (get(degree,u) < get(degree,w) )
78 inline const value_type& front() const {
79 const value_type& u = base::front();
82 else if (get(degree,u) < get(degree,w) )
87 inline value_type& top() { return front(); }
88 inline const value_type& top() const { return front(); }
90 inline size_type size() const { return base::size(); }
92 inline size_type eccentricity() const { return eccen; }
93 inline value_type spouse() const { return w; }
104 template <typename Tp, typename Sequence = std::deque<Tp> >
105 class sparse_ordering_queue : public boost::queue<Tp, Sequence>{
107 typedef typename Sequence::iterator iterator;
108 typedef typename Sequence::reverse_iterator reverse_iterator;
109 typedef queue<Tp,Sequence> base;
110 typedef typename Sequence::size_type size_type;
112 inline iterator begin() { return this->c.begin(); }
113 inline reverse_iterator rbegin() { return this->c.rbegin(); }
114 inline iterator end() { return this->c.end(); }
115 inline reverse_iterator rend() { return this->c.rend(); }
116 inline Tp &operator[](int n) { return this->c[n]; }
117 inline size_type size() {return this->c.size(); }
122 } // namespace sparse
124 // Compute Pseudo peripheral
126 // To compute an approximated peripheral for a given vertex.
127 // Used in <tt>king_ordering</tt> algorithm.
129 template <class Graph, class Vertex, class ColorMap, class DegreeMap>
131 pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc,
132 ColorMap color, DegreeMap degree)
134 typedef typename property_traits<ColorMap>::value_type ColorValue;
135 typedef color_traits<ColorValue> Color;
137 sparse::rcm_queue<Vertex, DegreeMap> Q(degree);
139 typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;
140 for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
141 if (get(color, *ui) != Color::red()) put(color, *ui, Color::white());
142 breadth_first_visit(G, u, buffer(Q).color_map(color));
144 ecc = Q.eccentricity();
148 // Find a good starting node
150 // This is to find a good starting node for the
151 // king_ordering algorithm. "good" is in the sense
152 // of the ordering generated by RCM.
154 template <class Graph, class Vertex, class Color, class Degree>
155 Vertex find_starting_node(Graph& G, Vertex r, Color color, Degree degree)
158 int eccen_r, eccen_x;
160 x = pseudo_peripheral_pair(G, r, eccen_r, color, degree);
161 y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
163 while (eccen_x > eccen_r) {
167 y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
172 template <typename Graph>
173 class out_degree_property_map
174 : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
175 out_degree_property_map<Graph> >
178 typedef typename graph_traits<Graph>::vertex_descriptor key_type;
179 typedef typename graph_traits<Graph>::degree_size_type value_type;
180 typedef value_type reference;
181 typedef readable_property_map_tag category;
182 out_degree_property_map(const Graph& g) : m_g(g) { }
183 value_type operator[](const key_type& v) const {
184 return out_degree(v, m_g);
189 template <typename Graph>
190 inline out_degree_property_map<Graph>
191 make_out_degree_map(const Graph& g) {
192 return out_degree_property_map<Graph>(g);
198 #endif // BOOST_GRAPH_KING_HPP