//=======================================================================
|
// 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
|
