Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / smallest_last_ordering.hpp
1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9 #ifndef BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
10 #define BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
11 /*
12    The smallest-last ordering is defined for the loopless graph G with
13    vertices a(j), j = 1,2,...,n where a(j) is the j-th column of A and
14    with edge (a(i),a(j)) if and only if columns i and j have a
15    non-zero in the same row position.  The smallest-last ordering is
16    determined recursively by letting list(k), k = n,...,1 be a column
17    with least degree in the subgraph spanned by the un-ordered
18    columns.
19  */
20 #include <vector>
21 #include <algorithm>
22 #include <boost/config.hpp>
23 #include <boost/graph/graph_traits.hpp>
24 #include <boost/pending/bucket_sorter.hpp>
25
26 namespace boost {
27
28   template <class VertexListGraph, class Order, class Degree, class Marker>
29   void 
30   smallest_last_vertex_ordering(const VertexListGraph& G, Order order, 
31                                 Degree degree, Marker marker) {
32     typedef typename graph_traits<VertexListGraph> GraphTraits;
33     typedef typename GraphTraits::vertex_descriptor Vertex;
34     //typedef typename GraphTraits::size_type size_type;
35     typedef std::size_t size_type;
36     
37     const size_type num = num_vertices(G);
38     
39     typedef typename vertex_property_map<VertexListGraph, vertex_index_t>::type ID;
40     typedef bucket_sorter<size_type, Vertex, Degree, ID> BucketSorter;
41     
42     BucketSorter degree_bucket_sorter(num, num, degree,  
43                                       get_vertex_property(G, vertex_index));
44
45     smallest_last_vertex_ordering(G, order, degree, marker, degree_bucket_sorter);
46   }
47
48   template <class VertexListGraph, class Order, class Degree, 
49             class Marker, class BucketSorter>
50   void 
51   smallest_last_vertex_ordering(const VertexListGraph& G, Order order, 
52                                 Degree degree, Marker marker,
53                                 BucketSorter& degree_buckets) {
54     typedef typename graph_traits<VertexListGraph> GraphTraits;
55     typedef typename GraphTraits::vertex_descriptor Vertex;
56     //typedef typename GraphTraits::size_type size_type;
57     typedef std::size_t size_type;
58
59     const size_type num = num_vertices(G);
60     
61     typename GraphTraits::vertex_iterator v, vend;
62     for (boost::tie(v, vend) = vertices(G); v != vend; ++v) {
63       put(marker, *v, num);
64       put(degree, *v, out_degree(*v, G));
65       degree_buckets.push(*v);
66     }
67  
68     size_type minimum_degree = 1;
69     size_type current_order = num - 1;
70     
71     while ( 1 ) {
72       typedef typename BucketSorter::stack MDStack;
73       MDStack minimum_degree_stack = degree_buckets[minimum_degree];
74       while (minimum_degree_stack.empty())
75         minimum_degree_stack = degree_buckets[++minimum_degree];
76       
77       Vertex node = minimum_degree_stack.top();
78       put(order, current_order, node);
79       
80       if ( current_order == 0 ) //find all vertices
81         break;
82       
83       minimum_degree_stack.pop();
84       put(marker, node, 0); //node has been ordered.
85       
86       typename GraphTraits::adjacency_iterator v, vend;
87       for (boost::tie(v,vend) = adjacent_vertices(node, G); v != vend; ++v)
88         
89         if ( get(marker,*v) > current_order ) { //*v is unordered vertex
90           put(marker, *v, current_order);  //mark the columns adjacent to node
91           
92           //It is possible minimum degree goes down
93           //Here we keep tracking it.
94           put(degree, *v, get(degree, *v) - 1); 
95           BOOST_USING_STD_MIN();
96           minimum_degree = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_degree, get(degree, *v)); 
97           
98           //update the position of *v in the bucket sorter
99           degree_buckets.update(*v);
100         }
101
102       current_order--;
103     }
104     
105     //at this point, order[i] = v_i;
106   }
107   
108 }
109
110 #endif
111