xref: /third_party/boost/boost/graph/detail/sparse_ordering.hpp

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