epoc32/include/stdapis/boost/graph/cuthill_mckee_ordering.hpp
branchSymbian2
changeset 2 2fe1408b6811
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/cuthill_mckee_ordering.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,190 @@
     1.4 +//=======================================================================
     1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     1.6 +// Copyright 2004, 2005 Trustees of Indiana University
     1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
     1.8 +//          Doug Gregor, D. Kevin McGrath
     1.9 +//
    1.10 +// Distributed under the Boost Software License, Version 1.0. (See
    1.11 +// accompanying file LICENSE_1_0.txt or copy at
    1.12 +// http://www.boost.org/LICENSE_1_0.txt)
    1.13 +//=======================================================================
    1.14 +#ifndef BOOST_GRAPH_CUTHILL_MCKEE_HPP
    1.15 +#define BOOST_GRAPH_CUTHILL_MCKEE_HPP
    1.16 +
    1.17 +#include <boost/config.hpp>
    1.18 +#include <boost/graph/detail/sparse_ordering.hpp>
    1.19 +#include <algorithm>
    1.20 +
    1.21 +
    1.22 +/*
    1.23 +  (Reverse) Cuthill-McKee Algorithm for matrix reordering
    1.24 +*/
    1.25 +
    1.26 +namespace boost {
    1.27 +
    1.28 +  namespace detail {
    1.29 +
    1.30 +
    1.31 +
    1.32 +    template < typename OutputIterator, typename Buffer, typename DegreeMap > 
    1.33 +    class bfs_rcm_visitor:public default_bfs_visitor
    1.34 +    {
    1.35 +    public:
    1.36 +      bfs_rcm_visitor(OutputIterator *iter, Buffer *b, DegreeMap deg): 
    1.37 +        permutation(iter), Qptr(b), degree(deg) { }
    1.38 +      template <class Vertex, class Graph>
    1.39 +      void examine_vertex(Vertex u, Graph&) {
    1.40 +        *(*permutation)++ = u;
    1.41 +        index_begin = Qptr->size();
    1.42 +      }
    1.43 +      template <class Vertex, class Graph>
    1.44 +      void finish_vertex(Vertex, Graph&) {
    1.45 +        using std::sort;
    1.46 +
    1.47 +        typedef typename property_traits<DegreeMap>::value_type ds_type;
    1.48 +
    1.49 +        typedef indirect_cmp<DegreeMap, std::less<ds_type> > Compare;
    1.50 +        Compare comp(degree);
    1.51 +                
    1.52 +        sort(Qptr->begin()+index_begin, Qptr->end(), comp);
    1.53 +      }
    1.54 +    protected:
    1.55 +      OutputIterator *permutation;
    1.56 +      int index_begin;
    1.57 +      Buffer *Qptr;
    1.58 +      DegreeMap degree;
    1.59 +    };
    1.60 +
    1.61 +  } // namespace detail  
    1.62 +
    1.63 +
    1.64 +  // Reverse Cuthill-McKee algorithm with a given starting Vertex.
    1.65 +  //
    1.66 +  // If user provides a reverse iterator, this will be a reverse-cuthill-mckee
    1.67 +  // algorithm, otherwise it will be a standard CM algorithm
    1.68 +
    1.69 +  template <class Graph, class OutputIterator,
    1.70 +            class ColorMap, class DegreeMap>
    1.71 +  OutputIterator
    1.72 +  cuthill_mckee_ordering(const Graph& g,
    1.73 +                         std::deque< typename
    1.74 +                         graph_traits<Graph>::vertex_descriptor > vertex_queue,
    1.75 +                         OutputIterator permutation, 
    1.76 +                         ColorMap color, DegreeMap degree)
    1.77 +  {
    1.78 +
    1.79 +    //create queue, visitor...don't forget namespaces!
    1.80 +    typedef typename property_traits<DegreeMap>::value_type ds_type;
    1.81 +    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    1.82 +    typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
    1.83 +    typedef typename detail::bfs_rcm_visitor<OutputIterator, queue, DegreeMap> Visitor;
    1.84 +    typedef typename property_traits<ColorMap>::value_type ColorValue;
    1.85 +    typedef color_traits<ColorValue> Color;
    1.86 +
    1.87 +
    1.88 +    queue Q;
    1.89 +
    1.90 +    //create a bfs_rcm_visitor as defined above
    1.91 +    Visitor     vis(&permutation, &Q, degree);
    1.92 +
    1.93 +    typename graph_traits<Graph>::vertex_iterator ui, ui_end;    
    1.94 +
    1.95 +    // Copy degree to pseudo_degree
    1.96 +    // initialize the color map
    1.97 +    for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){
    1.98 +      put(color, *ui, Color::white());
    1.99 +    }
   1.100 +
   1.101 +
   1.102 +    while( !vertex_queue.empty() ) {
   1.103 +      Vertex s = vertex_queue.front();
   1.104 +      vertex_queue.pop_front();
   1.105 +      
   1.106 +      //call BFS with visitor
   1.107 +      breadth_first_visit(g, s, Q, vis, color);
   1.108 +    }
   1.109 +    return permutation;
   1.110 +  }
   1.111 +    
   1.112 +
   1.113 +  // This is the case where only a single starting vertex is supplied.
   1.114 +  template <class Graph, class OutputIterator,
   1.115 +            class ColorMap, class DegreeMap>
   1.116 +  OutputIterator
   1.117 +  cuthill_mckee_ordering(const Graph& g,
   1.118 +                         typename graph_traits<Graph>::vertex_descriptor s,
   1.119 +                         OutputIterator permutation, 
   1.120 +                         ColorMap color, DegreeMap degree)
   1.121 +  {
   1.122 +
   1.123 +    std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;
   1.124 +    vertex_queue.push_front( s );
   1.125 +
   1.126 +    return cuthill_mckee_ordering(g, vertex_queue, permutation, color, degree);
   1.127 +  
   1.128 +  }
   1.129 +  
   1.130 +
   1.131 +  // This is the version of CM which selects its own starting vertex
   1.132 +  template < class Graph, class OutputIterator, 
   1.133 +             class ColorMap, class DegreeMap>
   1.134 +  OutputIterator 
   1.135 +  cuthill_mckee_ordering(const Graph& G, OutputIterator permutation, 
   1.136 +                         ColorMap color, DegreeMap degree)
   1.137 +  {
   1.138 +    if (vertices(G).first == vertices(G).second)
   1.139 +      return permutation;
   1.140 +
   1.141 +    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
   1.142 +    typedef typename boost::graph_traits<Graph>::vertex_iterator   VerIter;
   1.143 +    typedef typename property_traits<ColorMap>::value_type ColorValue;
   1.144 +    typedef color_traits<ColorValue> Color;
   1.145 +
   1.146 +    std::deque<Vertex>      vertex_queue;
   1.147 +
   1.148 +    // Mark everything white
   1.149 +    BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
   1.150 +
   1.151 +    // Find one vertex from each connected component 
   1.152 +    BGL_FORALL_VERTICES_T(v, G, Graph) {
   1.153 +      if (get(color, v) == Color::white()) {
   1.154 +        depth_first_visit(G, v, dfs_visitor<>(), color);
   1.155 +        vertex_queue.push_back(v);
   1.156 +      }
   1.157 +    }
   1.158 +
   1.159 +    // Find starting nodes for all vertices
   1.160 +    // TBD: How to do this with a directed graph?
   1.161 +    for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();
   1.162 +         i != vertex_queue.end(); ++i)
   1.163 +      *i = find_starting_node(G, *i, color, degree);
   1.164 +    
   1.165 +    return cuthill_mckee_ordering(G, vertex_queue, permutation,
   1.166 +                                  color, degree);
   1.167 +  }
   1.168 +
   1.169 +  template<typename Graph, typename OutputIterator, typename VertexIndexMap>
   1.170 +  OutputIterator 
   1.171 +  cuthill_mckee_ordering(const Graph& G, OutputIterator permutation, 
   1.172 +                         VertexIndexMap index_map)
   1.173 +  {
   1.174 +    if (vertices(G).first == vertices(G).second)
   1.175 +      return permutation;
   1.176 +    
   1.177 +    typedef out_degree_property_map<Graph> DegreeMap;
   1.178 +    std::vector<default_color_type> colors(num_vertices(G));
   1.179 +    return cuthill_mckee_ordering(G, permutation, 
   1.180 +                                  make_iterator_property_map(&colors[0], 
   1.181 +                                                             index_map,
   1.182 +                                                             colors[0]),
   1.183 +                                  make_out_degree_map(G));
   1.184 +  }
   1.185 +
   1.186 +  template<typename Graph, typename OutputIterator>
   1.187 +  inline OutputIterator 
   1.188 +  cuthill_mckee_ordering(const Graph& G, OutputIterator permutation)
   1.189 +  { return cuthill_mckee_ordering(G, permutation, get(vertex_index, G)); }
   1.190 +} // namespace boost
   1.191 +
   1.192 +
   1.193 +#endif // BOOST_GRAPH_CUTHILL_MCKEE_HPP