[857] | 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
|
---|