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

Revision 857, 4.2 KB checked in by igarcia, 19 years ago (diff)
Line 
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
26namespace 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
Note: See TracBrowser for help on using the repository browser.