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

Revision 857, 12.4 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[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_KING_HPP
29#define BOOST_GRAPH_KING_HPP
30
31#include <boost/config.hpp>
32#include <boost/graph/detail/sparse_ordering.hpp>
33
34/*
35  King Algorithm for matrix reordering
36*/
37
38namespace boost {
39  namespace detail {
40    template<typename OutputIterator, typename Buffer, typename Compare,
41             typename PseudoDegreeMap, typename VecMap, typename VertexIndexMap>
42    class bfs_king_visitor:public default_bfs_visitor
43    {
44    public:
45      bfs_king_visitor(OutputIterator *iter, Buffer *b, Compare compare,
46                       PseudoDegreeMap deg, std::vector<int> loc, VecMap color,
47                       VertexIndexMap vertices):
48        permutation(iter), Qptr(b), degree(deg), comp(compare),
49        Qlocation(loc), colors(color), vertex_map(vertices) { }
50     
51      template <typename Vertex, typename Graph>
52      void finish_vertex(Vertex, Graph& g) {
53        typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
54        Vertex v, w;
55
56        typedef typename std::deque<Vertex>::iterator iterator;
57        typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;
58
59        reverse_iterator rend = Qptr->rend()-index_begin;
60        reverse_iterator rbegin = Qptr->rbegin();
61
62
63        //heap the vertices already there
64        std::make_heap(rbegin, rend, boost::bind<bool>(comp, _2, _1));
65
66        int i = 0;
67       
68        for(i = index_begin; i != Qptr->size(); ++i){
69          colors[get(vertex_map, (*Qptr)[i])] = 1;
70          Qlocation[get(vertex_map, (*Qptr)[i])] = i;
71        }
72
73        i = 0;
74
75        for( ; rbegin != rend; rend--){
76          percolate_down<Vertex>(i);
77          w = (*Qptr)[index_begin+i];
78          for (tie(ei, ei_end) = out_edges(w, g); ei != ei_end; ++ei) {
79            v = target(*ei, g);
80            put(degree, v, get(degree, v) - 1);
81   
82            if (colors[get(vertex_map, v)] == 1) {
83              percolate_up<Vertex>(get(vertex_map, v), i);           
84            }
85          }
86         
87          colors[get(vertex_map, w)] = 0;
88          i++;
89        }
90      }
91   
92      template <typename Vertex, typename Graph>
93      void examine_vertex(Vertex u, const Graph&) {
94       
95        *(*permutation)++ = u;
96        index_begin = Qptr->size();
97       
98      }
99    protected:
100
101
102      //this function replaces pop_heap, and tracks state information
103      template <typename Vertex>
104      void percolate_down(int offset){
105        typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;
106       
107        int heap_last = index_begin + offset;
108        int heap_first = Qptr->size() - 1;
109       
110        //pop_heap functionality:
111        //swap first, last
112        std::swap((*Qptr)[heap_last], (*Qptr)[heap_first]);
113       
114        //swap in the location queue
115        std::swap(Qlocation[heap_first], Qlocation[heap_last]);
116
117        //set drifter, children
118        int drifter = heap_first;
119        int drifter_heap = Qptr->size() - drifter;
120
121        int right_child_heap = drifter_heap * 2 + 1;
122        int right_child = Qptr->size() - right_child_heap;
123
124        int left_child_heap = drifter_heap * 2;
125        int left_child = Qptr->size() - left_child_heap;
126
127        //check that we are staying in the heap
128        bool valid = (right_child < heap_last) ? false : true;
129       
130        //pick smallest child of drifter, and keep in mind there might only be left child
131        int smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree,(*Qptr)[right_child])) ?
132          right_child : left_child;
133       
134        while(valid && smallest_child < heap_last && comp((*Qptr)[drifter], (*Qptr)[smallest_child])){
135         
136          //if smallest child smaller than drifter, swap them
137          std::swap((*Qptr)[smallest_child], (*Qptr)[drifter]);
138          std::swap(Qlocation[drifter], Qlocation[smallest_child]);
139
140          //update the values, run again, as necessary
141          drifter = smallest_child;
142          drifter_heap = Qptr->size() - drifter;
143
144          right_child_heap = drifter_heap * 2 + 1;
145          right_child = Qptr->size() - right_child_heap;
146
147          left_child_heap = drifter_heap * 2;
148          left_child = Qptr->size() - left_child_heap;
149
150          valid = (right_child < heap_last) ? false : true;
151
152          smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree,(*Qptr)[right_child])) ?
153            right_child : left_child;
154        }
155
156      }
157
158
159     
160      // this is like percolate down, but we always compare against the
161      // parent, as there is only a single choice
162      template <typename Vertex>
163      void percolate_up(int vertex, int offset){
164       
165        int child_location = Qlocation[vertex];
166        int heap_child_location = Qptr->size() - child_location;
167        int heap_parent_location = (int)(heap_child_location/2);
168        int parent_location = Qptr->size() - heap_parent_location;
169
170        bool valid = (heap_parent_location != 0 && child_location > index_begin + offset &&
171                      parent_location < Qptr->size());
172
173        while(valid && comp((*Qptr)[child_location], (*Qptr)[parent_location])){
174         
175          //swap in the heap
176          std::swap((*Qptr)[child_location], (*Qptr)[parent_location]);
177         
178          //swap in the location queue
179          std::swap(Qlocation[child_location], Qlocation[parent_location]);
180
181          child_location = parent_location;
182          heap_child_location = heap_parent_location;
183          heap_parent_location = (int)(heap_child_location/2);
184          parent_location = Qptr->size() - heap_parent_location;
185          valid = (heap_parent_location != 0 && child_location > index_begin + offset);
186        }
187      }
188     
189      OutputIterator *permutation;
190      int index_begin;
191      Buffer *Qptr;
192      PseudoDegreeMap degree;
193      Compare comp;
194      std::vector<int> Qlocation;
195      VecMap colors;
196      VertexIndexMap vertex_map;
197    };
198 
199
200  } // namespace detail 
201 
202
203  template<class Graph, class OutputIterator, class ColorMap, class DegreeMap,
204           typename VertexIndexMap>
205  OutputIterator
206  king_ordering(const Graph& g,
207                std::deque< typename graph_traits<Graph>::vertex_descriptor >
208                  vertex_queue,
209                OutputIterator permutation,
210                ColorMap color, DegreeMap degree,
211                VertexIndexMap index_map)
212  {
213    typedef typename property_traits<DegreeMap>::value_type DS;
214    typedef typename property_traits<ColorMap>::value_type ColorValue;
215    typedef color_traits<ColorValue> Color;
216    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
217    typedef iterator_property_map<typename std::vector<DS>::iterator, VertexIndexMap, DS, DS&> PseudoDegreeMap;
218    typedef indirect_cmp<PseudoDegreeMap, std::less<DS> > Compare;
219    typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
220    typedef typename detail::bfs_king_visitor<OutputIterator, queue, Compare,             
221      PseudoDegreeMap, std::vector<int>, VertexIndexMap > Visitor;
222    typedef typename graph_traits<Graph>::vertices_size_type
223      vertices_size_type;
224    std::vector<DS> pseudo_degree_vec(num_vertices(g));
225    PseudoDegreeMap pseudo_degree(pseudo_degree_vec.begin(), index_map);
226   
227    typename graph_traits<Graph>::vertex_iterator ui, ui_end;   
228    queue Q;
229    // Copy degree to pseudo_degree
230    // initialize the color map
231    for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){
232      put(pseudo_degree, *ui, get(degree, *ui));
233      put(color, *ui, Color::white());
234    }
235   
236    Compare comp(pseudo_degree);
237    std::vector<int> colors(num_vertices(g));
238
239    for(vertices_size_type i = 0; i < num_vertices(g); i++)
240      colors[i] = 0;
241
242    std::vector<int> loc(num_vertices(g));
243
244    //create the visitor
245    Visitor vis(&permutation, &Q, comp, pseudo_degree, loc, colors, index_map);
246   
247    while( !vertex_queue.empty() ) {
248      Vertex s = vertex_queue.front();
249      vertex_queue.pop_front();
250     
251      //call BFS with visitor
252      breadth_first_visit(g, s, Q, vis, color);
253    }
254
255    return permutation;
256  }
257
258 
259  // This is the case where only a single starting vertex is supplied.
260  template <class Graph, class OutputIterator,
261            class ColorMap, class DegreeMap, typename VertexIndexMap>
262  OutputIterator
263  king_ordering(const Graph& g,
264                typename graph_traits<Graph>::vertex_descriptor s,
265                OutputIterator permutation,
266                ColorMap color, DegreeMap degree, VertexIndexMap index_map)
267  {
268
269    std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;
270    vertex_queue.push_front( s );
271    return king_ordering(g, vertex_queue, permutation, color, degree,
272                         index_map);
273  }
274
275 
276  template < class Graph, class OutputIterator,
277             class ColorMap, class DegreeMap, class VertexIndexMap>
278  OutputIterator
279  king_ordering(const Graph& G, OutputIterator permutation,
280                ColorMap color, DegreeMap degree, VertexIndexMap index_map)
281  {
282    if (vertices(G).first == vertices(G).second)
283      return permutation;
284
285    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
286    typedef typename boost::graph_traits<Graph>::vertex_iterator   VerIter;
287    typedef typename property_traits<ColorMap>::value_type ColorValue;
288    typedef color_traits<ColorValue> Color;
289
290    std::deque<Vertex>      vertex_queue;
291
292    // Mark everything white
293    BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
294
295    // Find one vertex from each connected component
296    BGL_FORALL_VERTICES_T(v, G, Graph) {
297      if (get(color, v) == Color::white()) {
298        depth_first_visit(G, v, dfs_visitor<>(), color);
299        vertex_queue.push_back(v);
300      }
301    }
302
303    // Find starting nodes for all vertices
304    // TBD: How to do this with a directed graph?
305    for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();
306         i != vertex_queue.end(); ++i)
307      *i = find_starting_node(G, *i, color, degree);
308   
309    return king_ordering(G, vertex_queue, permutation, color, degree,
310                         index_map);
311  }
312
313  template<typename Graph, typename OutputIterator, typename VertexIndexMap>
314  OutputIterator
315  king_ordering(const Graph& G, OutputIterator permutation,
316                VertexIndexMap index_map)
317  {
318    if (vertices(G).first == vertices(G).second)
319      return permutation;
320
321    typedef out_degree_property_map<Graph> DegreeMap;
322    std::vector<default_color_type> colors(num_vertices(G));
323    return king_ordering(G, permutation,
324                         make_iterator_property_map(&colors[0], index_map,
325                                                    colors[0]),
326                         make_out_degree_map(G), index_map);
327  }
328
329  template<typename Graph, typename OutputIterator>
330  inline OutputIterator
331  king_ordering(const Graph& G, OutputIterator permutation)
332  { return king_ordering(G, permutation, get(vertex_index, G)); }
333
334} // namespace boost
335
336
337#endif // BOOST_GRAPH_KING_HPP
Note: See TracBrowser for help on using the repository browser.