source: NonGTP/Boost/boost/graph/cuthill_mckee_ordering.hpp @ 857

Revision 857, 7.3 KB checked in by igarcia, 19 years ago (diff)
Line 
1//
2//=======================================================================
3// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
5//          Doug Gregor, D. Kevin McGrath
6//
7// This file is part of the Boost Graph Library
8//
9// You should have received a copy of the License Agreement for the
10// Boost Graph Library along with the software; see the file LICENSE.
11// If not, contact Office of Research, University of Notre Dame, Notre
12// Dame, IN 46556.
13//
14// Permission to modify the code and to distribute modified code is
15// granted, provided the text of this NOTICE is retained, a notice that
16// the code was modified is included with the above COPYRIGHT NOTICE and
17// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
18// file is distributed with the modified code.
19//
20// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
21// By way of example, but not limitation, Licensor MAKES NO
22// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
23// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
24// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
25// OR OTHER RIGHTS.
26//=======================================================================
27//
28#ifndef BOOST_GRAPH_CUTHILL_MCKEE_HPP
29#define BOOST_GRAPH_CUTHILL_MCKEE_HPP
30
31#include <boost/config.hpp>
32#include <boost/graph/detail/sparse_ordering.hpp>
33#include <algorithm>
34
35
36/*
37  (Reverse) Cuthill-McKee Algorithm for matrix reordering
38*/
39
40namespace boost {
41
42  namespace detail {
43
44
45
46    template < typename OutputIterator, typename Buffer, typename DegreeMap >
47    class bfs_rcm_visitor:public default_bfs_visitor
48    {
49    public:
50      bfs_rcm_visitor(OutputIterator *iter, Buffer *b, DegreeMap deg):
51        permutation(iter), Qptr(b), degree(deg) { }
52      template <class Vertex, class Graph>
53      void examine_vertex(Vertex u, Graph&) {
54        *(*permutation)++ = u;
55        index_begin = Qptr->size();
56      }
57      template <class Vertex, class Graph>
58      void finish_vertex(Vertex, Graph&) {
59        using std::sort;
60
61        typedef typename property_traits<DegreeMap>::value_type DS;
62
63        typedef indirect_cmp<DegreeMap, std::less<DS> > Compare;
64        Compare comp(degree);
65               
66        sort(Qptr->begin()+index_begin, Qptr->end(), comp);
67      }
68    protected:
69      OutputIterator *permutation;
70      int index_begin;
71      Buffer *Qptr;
72      DegreeMap degree;
73    };
74
75  } // namespace detail 
76
77
78  // Reverse Cuthill-McKee algorithm with a given starting Vertex.
79  //
80  // If user provides a reverse iterator, this will be a reverse-cuthill-mckee
81  // algorithm, otherwise it will be a standard CM algorithm
82
83  template <class Graph, class OutputIterator,
84            class ColorMap, class DegreeMap>
85  OutputIterator
86  cuthill_mckee_ordering(const Graph& g,
87                         std::deque< typename
88                         graph_traits<Graph>::vertex_descriptor > vertex_queue,
89                         OutputIterator permutation,
90                         ColorMap color, DegreeMap degree)
91  {
92
93    //create queue, visitor...don't forget namespaces!
94    typedef typename property_traits<DegreeMap>::value_type DS;
95    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
96    typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
97    typedef typename detail::bfs_rcm_visitor<OutputIterator, queue, DegreeMap> Visitor;
98    typedef typename property_traits<ColorMap>::value_type ColorValue;
99    typedef color_traits<ColorValue> Color;
100
101
102    queue Q;
103
104    //create a bfs_rcm_visitor as defined above
105    Visitor     vis(&permutation, &Q, degree);
106
107    typename graph_traits<Graph>::vertex_iterator ui, ui_end;   
108
109    // Copy degree to pseudo_degree
110    // initialize the color map
111    for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){
112      put(color, *ui, Color::white());
113    }
114
115
116    while( !vertex_queue.empty() ) {
117      Vertex s = vertex_queue.front();
118      vertex_queue.pop_front();
119     
120      //call BFS with visitor
121      breadth_first_visit(g, s, Q, vis, color);
122    }
123    return permutation;
124  }
125   
126
127  // This is the case where only a single starting vertex is supplied.
128  template <class Graph, class OutputIterator,
129            class ColorMap, class DegreeMap>
130  OutputIterator
131  cuthill_mckee_ordering(const Graph& g,
132                         typename graph_traits<Graph>::vertex_descriptor s,
133                         OutputIterator permutation,
134                         ColorMap color, DegreeMap degree)
135  {
136
137    std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;
138    vertex_queue.push_front( s );
139
140    return cuthill_mckee_ordering(g, vertex_queue, permutation, color, degree);
141 
142  }
143 
144
145  // This is the version of CM which selects its own starting vertex
146  template < class Graph, class OutputIterator,
147             class ColorMap, class DegreeMap>
148  OutputIterator
149  cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
150                         ColorMap color, DegreeMap degree)
151  {
152    if (vertices(G).first == vertices(G).second)
153      return permutation;
154
155    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
156    typedef typename boost::graph_traits<Graph>::vertex_iterator   VerIter;
157    typedef typename property_traits<ColorMap>::value_type ColorValue;
158    typedef color_traits<ColorValue> Color;
159
160    std::deque<Vertex>      vertex_queue;
161
162    // Mark everything white
163    BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
164
165    // Find one vertex from each connected component
166    BGL_FORALL_VERTICES_T(v, G, Graph) {
167      if (get(color, v) == Color::white()) {
168        depth_first_visit(G, v, dfs_visitor<>(), color);
169        vertex_queue.push_back(v);
170      }
171    }
172
173    // Find starting nodes for all vertices
174    // TBD: How to do this with a directed graph?
175    for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();
176         i != vertex_queue.end(); ++i)
177      *i = find_starting_node(G, *i, color, degree);
178   
179    return cuthill_mckee_ordering(G, vertex_queue, permutation,
180                                  color, degree);
181  }
182
183  template<typename Graph, typename OutputIterator, typename VertexIndexMap>
184  OutputIterator
185  cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
186                         VertexIndexMap index_map)
187  {
188    if (vertices(G).first == vertices(G).second)
189      return permutation;
190   
191    typedef out_degree_property_map<Graph> DegreeMap;
192    std::vector<default_color_type> colors(num_vertices(G));
193    return cuthill_mckee_ordering(G, permutation,
194                                  make_iterator_property_map(&colors[0],
195                                                             index_map,
196                                                             colors[0]),
197                                  make_out_degree_map(G));
198  }
199
200  template<typename Graph, typename OutputIterator>
201  inline OutputIterator
202  cuthill_mckee_ordering(const Graph& G, OutputIterator permutation)
203  { return cuthill_mckee_ordering(G, permutation, get(vertex_index, G)); }
204} // namespace boost
205
206
207#endif // BOOST_GRAPH_CUTHILL_MCKEE_HPP
Note: See TracBrowser for help on using the repository browser.