Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / cuthill_mckee_ordering.hpp
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
40 namespace 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