Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / minimum_degree_ordering.hpp
1 //-*-c++-*-
2 //=======================================================================
3 // Copyright 1997-2001 University of Notre Dame.
4 // Authors: Lie-Quan Lee, Jeremy Siek
5 //
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10 //
11 #ifndef MINIMUM_DEGREE_ORDERING_HPP
12 #define MINIMUM_DEGREE_ORDERING_HPP
13
14 #include <vector>
15 #include <cassert>
16 #include <boost/config.hpp>
17 #include <boost/pending/bucket_sorter.hpp>
18 #include <boost/detail/numeric_traits.hpp> // for integer_traits
19 #include <boost/graph/graph_traits.hpp>
20 #include <boost/property_map.hpp>
21
22 namespace boost {
23
24   namespace detail {
25
26     // 
27     // Given a set of n integers (where the integer values range from
28     // zero to n-1), we want to keep track of a collection of stacks
29     // of integers. It so happens that an integer will appear in at
30     // most one stack at a time, so the stacks form disjoint sets.
31     // Because of these restrictions, we can use one big array to
32     // store all the stacks, intertwined with one another.
33     // No allocation/deallocation happens in the push()/pop() methods
34     // so this is faster than using std::stack's.
35     //
36     template <class SignedInteger>
37     class Stacks {
38       typedef SignedInteger value_type;
39       typedef typename std::vector<value_type>::size_type size_type;
40     public:
41       Stacks(size_type n) : data(n) {}
42       
43       //: stack 
44       class stack {
45         typedef typename std::vector<value_type>::iterator Iterator;
46       public:
47         stack(Iterator _data, const value_type& head)
48           :  data(_data), current(head) {}
49
50         // did not use default argument here to avoid internal compiler error
51         // in g++.
52         stack(Iterator _data)
53           : data(_data), current(-(std::numeric_limits<value_type>::max)()) {}
54         
55         void pop() {
56           assert(! empty());
57           current = data[current];
58         }
59         void push(value_type v) {
60           data[v] = current; 
61           current = v;
62         }
63         bool empty() {
64           return current == -(std::numeric_limits<value_type>::max)(); 
65         }
66         value_type& top() { return current; }
67       private:
68         Iterator data;
69         value_type current;
70       };
71
72       // To return a stack object 
73       stack make_stack()
74         { return stack(data.begin()); }
75     protected:
76       std::vector<value_type> data;
77     };
78
79
80     // marker class, a generalization of coloring. 
81     //
82     // This class is to provide a generalization of coloring which has
83     // complexity of amortized constant time to set all vertices' color
84     // back to be untagged. It implemented by increasing a tag.
85     //
86     // The colors are:
87     //   not tagged 
88     //   tagged
89     //   multiple_tagged
90     //   done
91     //
92     template <class SignedInteger, class Vertex, class VertexIndexMap>
93     class Marker {
94       typedef SignedInteger value_type;
95       typedef typename std::vector<value_type>::size_type size_type;
96       
97       static value_type done() 
98       { return (std::numeric_limits<value_type>::max)()/2; }
99     public:
100       Marker(size_type _num, VertexIndexMap index_map) 
101         : tag(1 - (std::numeric_limits<value_type>::max)()),
102           data(_num, - (std::numeric_limits<value_type>::max)()),
103           id(index_map) {}
104       
105       void mark_done(Vertex node) { data[get(id, node)] = done(); }
106       
107       bool is_done(Vertex node) { return data[get(id, node)] == done(); }
108       
109       void mark_tagged(Vertex node) { data[get(id, node)] = tag; }
110       
111       void mark_multiple_tagged(Vertex node) { data[get(id, node)] = multiple_tag; }
112   
113       bool is_tagged(Vertex node) const { return data[get(id, node)] >= tag; }
114
115       bool is_not_tagged(Vertex node) const { return data[get(id, node)] < tag; }
116
117       bool is_multiple_tagged(Vertex node) const 
118         { return data[get(id, node)] >= multiple_tag; }
119
120       void increment_tag() {
121         const size_type num = data.size();
122         ++tag;
123         if ( tag >= done() ) {
124           tag = 1 - (std::numeric_limits<value_type>::max)();
125           for (size_type i = 0; i < num; ++i)
126             if ( data[i] < done() ) 
127               data[i] = - (std::numeric_limits<value_type>::max)();
128         }
129       }
130       
131       void set_multiple_tag(value_type mdeg0) 
132       { 
133         const size_type num = data.size();
134         multiple_tag = tag + mdeg0; 
135         
136         if ( multiple_tag >= done() ) {
137           tag = 1-(std::numeric_limits<value_type>::max)();
138           
139           for (size_type i=0; i<num; i++)
140             if ( data[i] < done() ) 
141               data[i] = -(std::numeric_limits<value_type>::max)();
142           
143           multiple_tag = tag + mdeg0; 
144         }
145       }
146       
147       void set_tag_as_multiple_tag() { tag = multiple_tag; }
148       
149     protected:
150       value_type tag;
151       value_type multiple_tag;
152       std::vector<value_type> data;
153       VertexIndexMap id;
154     };
155     
156     template< class Iterator, class SignedInteger, 
157        class Vertex, class VertexIndexMap, int offset = 1 >
158     class Numbering {
159       typedef SignedInteger number_type;
160       number_type num; //start from 1 instead of zero
161       Iterator   data;
162       number_type max_num;
163       VertexIndexMap id;
164     public:
165       Numbering(Iterator _data, number_type _max_num, VertexIndexMap id) 
166         : num(1), data(_data), max_num(_max_num), id(id) {}
167       void operator()(Vertex node) { data[get(id, node)] = -num; }
168       bool all_done(number_type i = 0) const { return num + i > max_num; }
169       void increment(number_type i = 1) { num += i; }
170       bool is_numbered(Vertex node) const {
171         return data[get(id, node)] < 0;
172       }
173       void indistinguishable(Vertex i, Vertex j) {
174         data[get(id, i)] = - (get(id, j) + offset);
175       }
176     };
177
178     template <class SignedInteger, class Vertex, class VertexIndexMap>
179     class degreelists_marker {
180     public:
181       typedef SignedInteger value_type;
182       typedef typename std::vector<value_type>::size_type size_type;
183       degreelists_marker(size_type n, VertexIndexMap id)
184         : marks(n, 0), id(id) {}
185       void mark_need_update(Vertex i) { marks[get(id, i)] = 1;  }
186       bool need_update(Vertex i) { return marks[get(id, i)] == 1; }
187       bool outmatched_or_done (Vertex i) { return marks[get(id, i)] == -1; }
188       void mark(Vertex i) { marks[get(id, i)] = -1; }
189       void unmark(Vertex i) { marks[get(id, i)] = 0; }
190     private:
191       std::vector<value_type> marks;
192       VertexIndexMap id;
193     };
194
195     // Helper function object for edge removal
196     template <class Graph, class MarkerP, class NumberD, class Stack,
197       class VertexIndexMap>
198     class predicateRemoveEdge1 {
199       typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
200       typedef typename graph_traits<Graph>::edge_descriptor edge_t;
201     public:
202       predicateRemoveEdge1(Graph& _g, MarkerP& _marker, 
203                            NumberD _numbering, Stack& n_e, VertexIndexMap id)
204         : g(&_g), marker(&_marker), numbering(_numbering),
205           neighbor_elements(&n_e), id(id) {}
206
207       bool operator()(edge_t e) {
208         vertex_t dist = target(e, *g);
209         if ( marker->is_tagged(dist) )
210           return true;
211         marker->mark_tagged(dist);
212         if (numbering.is_numbered(dist)) {
213           neighbor_elements->push(get(id, dist));
214           return true;
215         }
216         return false;
217       }
218     private:
219       Graph*   g;
220       MarkerP* marker;
221       NumberD  numbering;
222       Stack*   neighbor_elements;
223       VertexIndexMap id;
224     };
225
226     // Helper function object for edge removal
227     template <class Graph, class MarkerP>
228     class predicate_remove_tagged_edges
229     {
230       typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
231       typedef typename graph_traits<Graph>::edge_descriptor edge_t;
232     public:
233       predicate_remove_tagged_edges(Graph& _g, MarkerP& _marker)
234         : g(&_g), marker(&_marker) {}
235
236       bool operator()(edge_t e) {
237         vertex_t dist = target(e, *g);
238         if ( marker->is_tagged(dist) )
239           return true;
240         return false;
241       }
242     private:
243       Graph*   g;
244       MarkerP* marker;
245     };
246
247     template<class Graph, class DegreeMap, 
248              class InversePermutationMap, 
249              class PermutationMap,
250              class SuperNodeMap, 
251              class VertexIndexMap>
252     class mmd_impl
253     {
254       // Typedefs
255       typedef graph_traits<Graph> Traits;
256       typedef typename Traits::vertices_size_type size_type;
257       typedef typename detail::integer_traits<size_type>::difference_type 
258         diff_t;
259       typedef typename Traits::vertex_descriptor vertex_t;
260       typedef typename Traits::adjacency_iterator adj_iter;
261       typedef iterator_property_map<vertex_t*, 
262         identity_property_map, vertex_t, vertex_t&> IndexVertexMap;
263       typedef detail::Stacks<diff_t> Workspace;
264       typedef bucket_sorter<size_type, vertex_t, DegreeMap, VertexIndexMap> 
265         DegreeLists;
266       typedef Numbering<InversePermutationMap, diff_t, vertex_t,VertexIndexMap>
267         NumberingD;
268       typedef degreelists_marker<diff_t, vertex_t, VertexIndexMap> 
269         DegreeListsMarker;
270       typedef Marker<diff_t, vertex_t, VertexIndexMap> MarkerP;
271
272       // Data Members
273
274       // input parameters
275       Graph& G;
276       int delta;
277       DegreeMap degree;
278       InversePermutationMap inverse_perm;
279       PermutationMap perm;
280       SuperNodeMap supernode_size;
281       VertexIndexMap vertex_index_map;
282
283       // internal data-structures
284       std::vector<vertex_t> index_vertex_vec;
285       size_type n;
286       IndexVertexMap index_vertex_map;
287       DegreeLists degreelists;
288       NumberingD numbering;
289       DegreeListsMarker degree_lists_marker;
290       MarkerP marker;
291       Workspace work_space;
292     public:
293       mmd_impl(Graph& g, size_type n_, int delta, DegreeMap degree, 
294                InversePermutationMap inverse_perm, 
295                PermutationMap perm,
296                SuperNodeMap supernode_size, 
297                VertexIndexMap id) 
298         : G(g), delta(delta), degree(degree), 
299         inverse_perm(inverse_perm), 
300         perm(perm), 
301         supernode_size(supernode_size), 
302         vertex_index_map(id),
303         index_vertex_vec(n_), 
304         n(n_),
305         degreelists(n_ + 1, n_, degree, id),
306         numbering(inverse_perm, n_, vertex_index_map),
307         degree_lists_marker(n_, vertex_index_map), 
308         marker(n_, vertex_index_map),
309         work_space(n_)
310       {
311         typename graph_traits<Graph>::vertex_iterator v, vend;
312         size_type vid = 0;
313         for (tie(v, vend) = vertices(G); v != vend; ++v, ++vid)
314           index_vertex_vec[vid] = *v;
315         index_vertex_map = IndexVertexMap(&index_vertex_vec[0]);
316
317         // Initialize degreelists.  Degreelists organizes the nodes
318         // according to their degree.
319         for (tie(v, vend) = vertices(G); v != vend; ++v) {
320           put(degree, *v, out_degree(*v, G));
321           degreelists.push(*v);
322         }
323       }
324
325       void do_mmd()
326       {
327         // Eliminate the isolated nodes -- these are simply the nodes
328         // with no neighbors, which are accessible as a list (really, a
329         // stack) at location 0.  Since these don't affect any other
330         // nodes, we can eliminate them without doing degree updates.
331         typename DegreeLists::stack list_isolated = degreelists[0];
332         while (!list_isolated.empty()) {
333           vertex_t node = list_isolated.top();
334           marker.mark_done(node);
335           numbering(node);
336           numbering.increment();
337           list_isolated.pop();
338         }
339         size_type min_degree = 1;
340         typename DegreeLists::stack list_min_degree = degreelists[min_degree];
341
342         while (list_min_degree.empty()) {
343           ++min_degree;
344           list_min_degree = degreelists[min_degree];
345         }
346
347         // check if the whole eliminating process is done
348         while (!numbering.all_done()) {
349
350           size_type min_degree_limit = min_degree + delta; // WARNING
351           typename Workspace::stack llist = work_space.make_stack();
352
353           // multiple elimination
354           while (delta >= 0) {
355
356             // Find the next non-empty degree
357             for (list_min_degree = degreelists[min_degree]; 
358                  list_min_degree.empty() && min_degree <= min_degree_limit; 
359                  ++min_degree, list_min_degree = degreelists[min_degree])
360               ;
361             if (min_degree > min_degree_limit)
362               break;
363
364             const vertex_t node = list_min_degree.top();
365             const size_type node_id = get(vertex_index_map, node);
366             list_min_degree.pop();
367             numbering(node);
368
369             // check if node is the last one
370             if (numbering.all_done(supernode_size[node])) {
371               numbering.increment(supernode_size[node]);
372               break;
373             }
374             marker.increment_tag();
375             marker.mark_tagged(node);
376
377             this->eliminate(node);
378
379             numbering.increment(supernode_size[node]);
380             llist.push(node_id);
381           } // multiple elimination
382
383           if (numbering.all_done()) 
384             break;
385
386           this->update( llist, min_degree);
387         }
388
389       } // do_mmd()
390
391       void eliminate(vertex_t node)
392       {
393         typename Workspace::stack element_neighbor = work_space.make_stack();
394
395         // Create two function objects for edge removal
396         typedef typename Workspace::stack WorkStack;
397         predicateRemoveEdge1<Graph, MarkerP, NumberingD, 
398                              WorkStack, VertexIndexMap>
399           p(G, marker, numbering, element_neighbor, vertex_index_map);
400
401         predicate_remove_tagged_edges<Graph, MarkerP> p2(G, marker);
402
403         // Reconstruct the adjacent node list, push element neighbor in a List.
404         remove_out_edge_if(node, p, G);
405         //during removal element neighbors are collected.
406
407         while (!element_neighbor.empty()) {
408           // element absorb
409           size_type e_id = element_neighbor.top();
410           vertex_t element = get(index_vertex_map, e_id);
411           adj_iter i, i_end;
412           for (tie(i, i_end) = adjacent_vertices(element, G); i != i_end; ++i){
413             vertex_t i_node = *i;
414             if (!marker.is_tagged(i_node) && !numbering.is_numbered(i_node)) {
415               marker.mark_tagged(i_node);
416               add_edge(node, i_node, G);
417             }
418           }
419           element_neighbor.pop();
420         }
421         adj_iter v, ve;
422         for (tie(v, ve) = adjacent_vertices(node, G); v != ve; ++v) {
423           vertex_t v_node = *v;
424           if (!degree_lists_marker.need_update(v_node) 
425               && !degree_lists_marker.outmatched_or_done(v_node)) {
426             degreelists.remove(v_node);
427           }
428           //update out edges of v_node
429           remove_out_edge_if(v_node, p2, G);
430
431           if ( out_degree(v_node, G) == 0 ) { // indistinguishable nodes
432             supernode_size[node] += supernode_size[v_node];
433             supernode_size[v_node] = 0;
434             numbering.indistinguishable(v_node, node);
435             marker.mark_done(v_node);
436             degree_lists_marker.mark(v_node);
437           } else {                           // not indistinguishable nodes
438             add_edge(v_node, node, G);
439             degree_lists_marker.mark_need_update(v_node);
440           }
441         }
442       } // eliminate()
443
444
445       template <class Stack>
446       void update(Stack llist, size_type& min_degree)
447       {
448         size_type min_degree0 = min_degree + delta + 1;
449
450         while (! llist.empty()) {
451           size_type deg, deg0 = 0;
452
453           marker.set_multiple_tag(min_degree0);
454           typename Workspace::stack q2list = work_space.make_stack();
455           typename Workspace::stack qxlist = work_space.make_stack();
456
457           vertex_t current = get(index_vertex_map, llist.top());
458           adj_iter i, ie;
459           for (tie(i,ie) = adjacent_vertices(current, G); i != ie; ++i) {
460             vertex_t i_node = *i;
461             const size_type i_id = get(vertex_index_map, i_node);
462             if (supernode_size[i_node] != 0) {
463               deg0 += supernode_size[i_node];
464               marker.mark_multiple_tagged(i_node);
465               if (degree_lists_marker.need_update(i_node)) {
466                 if (out_degree(i_node, G) == 2)
467                   q2list.push(i_id);
468                 else
469                   qxlist.push(i_id);
470               }
471             }
472           }
473
474           while (!q2list.empty()) {
475             const size_type u_id = q2list.top();
476             vertex_t u_node = get(index_vertex_map, u_id);
477             // if u_id is outmatched by others, no need to update degree
478             if (degree_lists_marker.outmatched_or_done(u_node)) {
479               q2list.pop();
480               continue;
481             }
482             marker.increment_tag();
483             deg = deg0;
484
485             adj_iter nu = adjacent_vertices(u_node, G).first;
486             vertex_t neighbor = *nu;
487             if (neighbor == u_node) {
488               ++nu;
489               neighbor = *nu;
490             }
491             if (numbering.is_numbered(neighbor)) {
492               adj_iter i, ie;
493               for (tie(i,ie) = adjacent_vertices(neighbor, G);
494                    i != ie; ++i) {
495                 const vertex_t i_node = *i;
496                 if (i_node == u_node || supernode_size[i_node] == 0)
497                   continue;
498                 if (marker.is_tagged(i_node)) {
499                   if (degree_lists_marker.need_update(i_node)) {
500                     if ( out_degree(i_node, G) == 2 ) { // is indistinguishable
501                       supernode_size[u_node] += supernode_size[i_node];
502                       supernode_size[i_node] = 0;
503                       numbering.indistinguishable(i_node, u_node);
504                       marker.mark_done(i_node);
505                       degree_lists_marker.mark(i_node);
506                     } else                        // is outmatched
507                       degree_lists_marker.mark(i_node);
508                   }
509                 } else {
510                   marker.mark_tagged(i_node);
511                   deg += supernode_size[i_node];
512                 }
513               }
514             } else
515               deg += supernode_size[neighbor];
516
517             deg -= supernode_size[u_node];
518             degree[u_node] = deg; //update degree
519             degreelists[deg].push(u_node);
520             //u_id has been pushed back into degreelists
521             degree_lists_marker.unmark(u_node);
522             if (min_degree > deg) 
523               min_degree = deg;
524             q2list.pop();
525           } // while (!q2list.empty())
526
527           while (!qxlist.empty()) {
528             const size_type u_id = qxlist.top();
529             const vertex_t u_node = get(index_vertex_map, u_id);
530
531             // if u_id is outmatched by others, no need to update degree
532             if (degree_lists_marker.outmatched_or_done(u_node)) {
533               qxlist.pop();
534               continue;
535             }
536             marker.increment_tag();
537             deg = deg0;
538             adj_iter i, ie;
539             for (tie(i, ie) = adjacent_vertices(u_node, G); i != ie; ++i) {
540               vertex_t i_node = *i;
541               if (marker.is_tagged(i_node)) 
542                 continue;
543               marker.mark_tagged(i_node);
544
545               if (numbering.is_numbered(i_node)) {
546                 adj_iter j, je;
547                 for (tie(j, je) = adjacent_vertices(i_node, G); j != je; ++j) {
548                   const vertex_t j_node = *j;
549                   if (marker.is_not_tagged(j_node)) {
550                     marker.mark_tagged(j_node);
551                     deg += supernode_size[j_node];
552                   }
553                 }
554               } else
555                 deg += supernode_size[i_node];
556             } // for adjacent vertices of u_node
557             deg -= supernode_size[u_node];
558             degree[u_node] = deg;
559             degreelists[deg].push(u_node);
560             // u_id has been pushed back into degreelists
561             degree_lists_marker.unmark(u_node); 
562             if (min_degree > deg)
563               min_degree = deg;
564             qxlist.pop();
565           } // while (!qxlist.empty()) {
566
567           marker.set_tag_as_multiple_tag();
568           llist.pop();
569         } // while (! llist.empty())
570
571       } // update()
572
573
574       void build_permutation(InversePermutationMap next,
575                              PermutationMap prev) 
576       {
577         // collect the permutation info
578         size_type i;
579         for (i = 0; i < n; ++i) {
580           diff_t size = supernode_size[get(index_vertex_map, i)];
581           if ( size <= 0 ) {
582             prev[i] = next[i];
583             supernode_size[get(index_vertex_map, i)]
584               = next[i] + 1;  // record the supernode info
585           } else
586             prev[i] = - next[i];
587         }
588         for (i = 1; i < n + 1; ++i) {
589           if ( prev[i-1] > 0 )
590             continue;
591           diff_t parent = i;
592           while ( prev[parent - 1] < 0 ) {
593             parent = - prev[parent - 1];
594           }
595
596           diff_t root = parent;
597           diff_t num = prev[root - 1] + 1;
598           next[i-1] = - num;
599           prev[root-1] = num;
600
601           parent = i;
602           diff_t next_node = - prev[parent - 1];
603           while (next_node > 0) {
604             prev[parent-1] = - root;
605             parent = next_node;
606             next_node = - prev[parent - 1];
607           }
608         }
609         for (i = 0; i < n; i++) {
610           diff_t num = - next[i] - 1;
611           next[i] = num;
612           prev[num] = i;
613         }
614       } // build_permutation()
615     };
616
617   } //namespace detail
618
619
620   // MMD algorithm
621   // 
622   //The implementation presently includes the enhancements for mass
623   //elimination, incomplete degree update, multiple elimination, and
624   //external degree.
625   //
626   //Important Note: This implementation requires the BGL graph to be
627   //directed.  Therefore, nonzero entry (i, j) in a symmetrical matrix
628   //A coresponds to two directed edges (i->j and j->i).
629   //
630   //see Alan George and Joseph W. H. Liu, The Evolution of the Minimum
631   //Degree Ordering Algorithm, SIAM Review, 31, 1989, Page 1-19
632   template<class Graph, class DegreeMap, 
633            class InversePermutationMap, 
634            class PermutationMap,
635            class SuperNodeMap, class VertexIndexMap>
636   void minimum_degree_ordering
637     (Graph& G, 
638      DegreeMap degree, 
639      InversePermutationMap inverse_perm, 
640      PermutationMap perm, 
641      SuperNodeMap supernode_size, 
642      int delta, 
643      VertexIndexMap vertex_index_map)
644   {
645     detail::mmd_impl<Graph,DegreeMap,InversePermutationMap,
646       PermutationMap, SuperNodeMap, VertexIndexMap> 
647       impl(G, num_vertices(G), delta, degree, inverse_perm, 
648            perm, supernode_size, vertex_index_map);
649     impl.do_mmd();
650     impl.build_permutation(inverse_perm, perm);
651   }
652
653 } // namespace boost
654
655 #endif // MINIMUM_DEGREE_ORDERING_HPP