sparse_ordering.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

//=======================================================================
// 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.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& 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 (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& 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