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