/usr/include/boost/graph/detail
Edit: /usr/include/boost/graph/detail/sparse_ordering.hpp (6345B)
//=======================================================================
// 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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 king_ordering 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