source: NonGTP/Boost/boost/graph/detail/sparse_ordering.hpp @ 857

Revision 857, 6.9 KB checked in by igarcia, 19 years ago (diff)
Line 
1//
2//=======================================================================
3// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5//
6// This file is part of the Boost Graph Library
7//
8// You should have received a copy of the License Agreement for the
9// Boost Graph Library along with the software; see the file LICENSE.
10// If not, contact Office of Research, University of Notre Dame, Notre
11// Dame, IN 46556.
12//
13// Permission to modify the code and to distribute modified code is
14// granted, provided the text of this NOTICE is retained, a notice that
15// the code was modified is included with the above COPYRIGHT NOTICE and
16// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
17// file is distributed with the modified code.
18//
19// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
20// By way of example, but not limitation, Licensor MAKES NO
21// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
22// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
23// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
24// OR OTHER RIGHTS.
25//=======================================================================
26//
27#ifndef BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
28#define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
29
30#include <boost/config.hpp>
31#include <vector>
32#include <queue>
33#include <boost/pending/queue.hpp>
34#include <boost/pending/mutable_queue.hpp>
35#include <boost/graph/graph_traits.hpp>
36#include <boost/graph/breadth_first_search.hpp>
37#include <boost/graph/properties.hpp>
38#include <boost/pending/indirect_cmp.hpp>
39#include <boost/property_map.hpp>
40#include <boost/bind.hpp>
41#include <boost/graph/iteration_macros.hpp>
42#include <boost/graph/depth_first_search.hpp>
43
44namespace boost {
45
46  namespace sparse {
47
48    // rcm_queue
49    //
50    // This is a custom queue type used in the
51    // *_ordering algorithms.
52    // In addition to the normal queue operations, the
53    // rcm_queue provides:
54    //
55    //   int eccentricity() const;
56    //   value_type spouse() const;
57    //
58
59    // yes, it's a bad name...but it works, so use it
60    template < class Vertex, class DegreeMap,
61               class Container = std::deque<Vertex> >
62    class rcm_queue : public std::queue<Vertex, Container> {
63      typedef std::queue<Vertex> base;
64    public:
65      typedef typename base::value_type value_type;
66      typedef typename base::size_type size_type;
67
68      /* SGI queue has not had a contructor queue(const Container&) */
69      inline rcm_queue(DegreeMap deg)
70        : _size(0), Qsize(1), eccen(-1), degree(deg) { }
71
72      inline void pop() {
73        if ( !_size )
74          Qsize = base::size();
75
76        base::pop();
77        if ( _size == Qsize-1 ) {
78          _size = 0;
79          ++eccen;
80        } else
81          ++_size;
82
83      }
84
85      inline value_type& front() {
86        value_type& u =  base::front();
87        if ( _size == 0 )
88          w = u;
89        else if (get(degree,u) < get(degree,w) )
90          w = u;
91        return u;
92      }
93
94      inline const value_type& front() const {
95        const value_type& u =  base::front();
96        if ( _size == 0 )
97          w = u;
98        else if (get(degree,u) < get(degree,w) )
99          w = u;
100        return u;
101      }
102
103      inline value_type& top() { return front(); }
104      inline const value_type& top() const { return front(); }
105
106      inline size_type size() const { return base::size(); }
107
108      inline size_type eccentricity() const { return eccen; }
109      inline value_type spouse() const { return w; }
110
111    protected:
112      size_type _size;
113      size_type Qsize;
114      int eccen;
115      mutable value_type w;
116      DegreeMap degree;
117    };
118
119
120    template <typename Tp, typename Sequence = std::deque<Tp> >
121    class sparse_ordering_queue : public boost::queue<Tp, Sequence>{
122    public:     
123      typedef typename Sequence::iterator iterator;
124      typedef typename Sequence::reverse_iterator reverse_iterator;
125      typedef queue<Tp,Sequence> queue;
126      typedef typename Sequence::size_type size_type;
127
128      inline iterator begin() { return this->c.begin(); }
129      inline reverse_iterator rbegin() { return this->c.rbegin(); }
130      inline iterator end() { return this->c.end(); }
131      inline reverse_iterator rend() { return this->c.rend(); }
132      inline Tp &operator[](int n) { return this->c[n]; }
133      inline size_type size() {return this->c.size(); }
134    protected:
135      //nothing
136    };
137   
138  } // namespace sparse
139
140  // Compute Pseudo peripheral
141  //
142  // To compute an approximated peripheral for a given vertex.
143  // Used in <tt>king_ordering</tt> algorithm.
144  //
145  template <class Graph, class Vertex, class ColorMap, class DegreeMap>
146  Vertex
147  pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc,
148                         ColorMap color, DegreeMap degree)
149  {
150    typedef typename property_traits<ColorMap>::value_type ColorValue;
151    typedef color_traits<ColorValue> Color;
152   
153    sparse::rcm_queue<Vertex, DegreeMap> Q(degree);
154
155    typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;
156    for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
157      if (get(color, *ui) != Color::red()) put(color, *ui, Color::white());
158    breadth_first_visit(G, u, buffer(Q).color_map(color));
159
160    ecc = Q.eccentricity();
161    return Q.spouse();
162  }
163
164  // Find a good starting node
165  //
166  // This is to find a good starting node for the
167  // king_ordering algorithm. "good" is in the sense
168  // of the ordering generated by RCM.
169  //
170  template <class Graph, class Vertex, class Color, class Degree>
171  Vertex find_starting_node(Graph& G, Vertex r, Color color, Degree degree)
172  {
173    Vertex x, y;
174    int eccen_r, eccen_x;
175
176    x = pseudo_peripheral_pair(G, r, eccen_r, color, degree);
177    y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
178
179    while (eccen_x > eccen_r) {
180      r = x;
181      eccen_r = eccen_x;
182      x = y;
183      y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
184    }
185    return x;
186  }
187
188template <typename Graph>
189class out_degree_property_map
190  : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
191                          out_degree_property_map<Graph> >                 
192{
193public:
194  typedef typename graph_traits<Graph>::vertex_descriptor key_type;
195  typedef typename graph_traits<Graph>::degree_size_type value_type;
196  typedef value_type reference;
197  typedef readable_property_map_tag category;
198  out_degree_property_map(const Graph& g) : m_g(g) { }
199  value_type operator[](const key_type& v) const {
200    return out_degree(v, m_g);
201  }
202private:
203  const Graph& m_g;
204};
205template <typename Graph>
206inline out_degree_property_map<Graph>
207make_out_degree_map(const Graph& g) {
208  return out_degree_property_map<Graph>(g);
209}
210
211} // namespace boost
212
213
214#endif // BOOST_GRAPH_KING_HPP
Note: See TracBrowser for help on using the repository browser.