| // |
| //======================================================================= |
| // Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch) |
| // ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st) |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| // |
| |
| #ifndef BOOST_GRAPH_SLOAN_HPP |
| #define BOOST_GRAPH_SLOAN_HPP |
| |
| #define WEIGHT1 1 //default weight for the distance in the Sloan algorithm |
| #define WEIGHT2 2 //default weight for the degree in the Sloan algorithm |
| |
| #include <boost/config.hpp> |
| #include <vector> |
| #include <queue> |
| #include <algorithm> |
| #include <limits> |
| #include <boost/pending/queue.hpp> |
| #include <boost/graph/graph_traits.hpp> |
| #include <boost/graph/breadth_first_search.hpp> |
| #include <boost/graph/properties.hpp> |
| #include <boost/pending/indirect_cmp.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <boost/graph/visitors.hpp> |
| #include <boost/graph/adjacency_list.hpp> |
| #include <boost/graph/cuthill_mckee_ordering.hpp> |
| |
| |
| //////////////////////////////////////////////////////////// |
| // |
| //Sloan-Algorithm for graph reordering |
| //(optimzes profile and wavefront, not primiraly bandwidth |
| // |
| //////////////////////////////////////////////////////////// |
| |
| namespace boost { |
| |
| ///////////////////////////////////////////////////////////////////////// |
| // Function that returns the maximum depth of |
| // a rooted level strucutre (RLS) |
| // |
| ///////////////////////////////////////////////////////////////////////// |
| template<class Distance> |
| unsigned RLS_depth(Distance& d) |
| { |
| unsigned h_s = 0; |
| typename Distance::iterator iter; |
| |
| for (iter = d.begin(); iter != d.end(); ++iter) |
| { |
| if(*iter > h_s) |
| { |
| h_s = *iter; |
| } |
| } |
| |
| return h_s; |
| } |
| |
| |
| |
| ///////////////////////////////////////////////////////////////////////// |
| // Function that returns the width of the largest level of |
| // a rooted level strucutre (RLS) |
| // |
| ///////////////////////////////////////////////////////////////////////// |
| template<class Distance, class my_int> |
| unsigned RLS_max_width(Distance& d, my_int depth) |
| { |
| |
| //Searching for the maximum width of a level |
| std::vector<unsigned> dummy_width(depth+1, 0); |
| std::vector<unsigned>::iterator my_it; |
| typename Distance::iterator iter; |
| unsigned w_max = 0; |
| |
| for (iter = d.begin(); iter != d.end(); ++iter) |
| { |
| dummy_width[*iter]++; |
| } |
| |
| for(my_it = dummy_width.begin(); my_it != dummy_width.end(); ++my_it) |
| { |
| if(*my_it > w_max) w_max = *my_it; |
| } |
| |
| return w_max; |
| |
| } |
| |
| |
| ///////////////////////////////////////////////////////////////////////// |
| // Function for finding a good starting node for Sloan algorithm |
| // |
| // This is to find a good starting node. "good" is in the sense |
| // of the ordering generated. |
| ///////////////////////////////////////////////////////////////////////// |
| template <class Graph, class ColorMap, class DegreeMap> |
| typename graph_traits<Graph>::vertex_descriptor |
| sloan_start_end_vertices(Graph& G, |
| typename graph_traits<Graph>::vertex_descriptor &s, |
| ColorMap color, |
| DegreeMap degree) |
| { |
| typedef typename property_traits<DegreeMap>::value_type Degree; |
| typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
| typedef typename std::vector< typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter; |
| typedef typename graph_traits<Graph>::vertices_size_type size_type; |
| |
| typedef typename property_map<Graph, vertex_index_t>::const_type VertexID; |
| |
| s = *(vertices(G).first); |
| Vertex e = s; |
| Vertex i; |
| unsigned my_degree = get(degree, s ); |
| unsigned dummy, h_i, h_s, w_i, w_e; |
| bool new_start = true; |
| unsigned maximum_degree = 0; |
| |
| //Creating a std-vector for storing the distance from the start vertex in dist |
| std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(G), 0); |
| |
| //Wrap a property_map_iterator around the std::iterator |
| boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, G)); |
| |
| //Creating a property_map for the indices of a vertex |
| typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, G); |
| |
| //Creating a priority queue |
| typedef indirect_cmp<DegreeMap, std::greater<Degree> > Compare; |
| Compare comp(degree); |
| std::priority_queue<Vertex, std::vector<Vertex>, Compare> degree_queue(comp); |
| |
| //step 1 |
| //Scan for the vertex with the smallest degree and the maximum degree |
| typename graph_traits<Graph>::vertex_iterator ui, ui_end; |
| for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) |
| { |
| dummy = get(degree, *ui); |
| |
| if(dummy < my_degree) |
| { |
| my_degree = dummy; |
| s = *ui; |
| } |
| |
| if(dummy > maximum_degree) |
| { |
| maximum_degree = dummy; |
| } |
| } |
| //end 1 |
| |
| do{ |
| new_start = false; //Setting the loop repetition status to false |
| |
| //step 2 |
| //initialize the the disance std-vector with 0 |
| for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0; |
| |
| //generating the RLS (rooted level structure) |
| breadth_first_search |
| (G, s, visitor |
| ( |
| make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) ) |
| ) |
| ); |
| |
| //end 2 |
| |
| //step 3 |
| //calculating the depth of the RLS |
| h_s = RLS_depth(dist); |
| |
| //step 4 |
| //pushing one node of each degree in an ascending manner into degree_queue |
| std::vector<bool> shrink_trace(maximum_degree, false); |
| for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) |
| { |
| dummy = get(degree, *ui); |
| |
| if( (dist[index_map[*ui]] == h_s ) && ( !shrink_trace[ dummy ] ) ) |
| { |
| degree_queue.push(*ui); |
| shrink_trace[ dummy ] = true; |
| } |
| } |
| |
| //end 3 & 4 |
| |
| |
| // step 5 |
| // Initializing w |
| w_e = (std::numeric_limits<unsigned>::max)(); |
| //end 5 |
| |
| |
| //step 6 |
| //Testing for termination |
| while( !degree_queue.empty() ) |
| { |
| i = degree_queue.top(); //getting the node with the lowest degree from the degree queue |
| degree_queue.pop(); //ereasing the node with the lowest degree from the degree queue |
| |
| //generating a RLS |
| for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0; |
| |
| breadth_first_search |
| (G, i, boost::visitor |
| ( |
| make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) ) |
| ) |
| ); |
| |
| //Calculating depth and width of the rooted level |
| h_i = RLS_depth(dist); |
| w_i = RLS_max_width(dist, h_i); |
| |
| //Testing for termination |
| if( (h_i > h_s) && (w_i < w_e) ) |
| { |
| h_s = h_i; |
| s = i; |
| while(!degree_queue.empty()) degree_queue.pop(); |
| new_start = true; |
| } |
| else if(w_i < w_e) |
| { |
| w_e = w_i; |
| e = i; |
| } |
| } |
| //end 6 |
| |
| }while(new_start); |
| |
| return e; |
| } |
| |
| ////////////////////////////////////////////////////////////////////////// |
| // Sloan algorithm with a given starting Vertex. |
| // |
| // This algorithm requires user to provide a starting vertex to |
| // compute Sloan ordering. |
| ////////////////////////////////////////////////////////////////////////// |
| template <class Graph, class OutputIterator, |
| class ColorMap, class DegreeMap, |
| class PriorityMap, class Weight> |
| OutputIterator |
| sloan_ordering(Graph& g, |
| typename graph_traits<Graph>::vertex_descriptor s, |
| typename graph_traits<Graph>::vertex_descriptor e, |
| OutputIterator permutation, |
| ColorMap color, |
| DegreeMap degree, |
| PriorityMap priority, |
| Weight W1, |
| Weight W2) |
| { |
| //typedef typename property_traits<DegreeMap>::value_type Degree; |
| typedef typename property_traits<PriorityMap>::value_type Degree; |
| typedef typename property_traits<ColorMap>::value_type ColorValue; |
| typedef color_traits<ColorValue> Color; |
| typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
| typedef typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter; |
| typedef typename graph_traits<Graph>::vertices_size_type size_type; |
| |
| typedef typename property_map<Graph, vertex_index_t>::const_type VertexID; |
| |
| |
| //Creating a std-vector for storing the distance from the end vertex in it |
| typename std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(g), 0); |
| |
| //Wrap a property_map_iterator around the std::iterator |
| boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, g)); |
| |
| breadth_first_search |
| (g, e, visitor |
| ( |
| make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) ) |
| ) |
| ); |
| |
| //Creating a property_map for the indices of a vertex |
| typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, g); |
| |
| //Sets the color and priority to their initial status |
| unsigned cdeg; |
| typename graph_traits<Graph>::vertex_iterator ui, ui_end; |
| for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) |
| { |
| put(color, *ui, Color::white()); |
| cdeg=get(degree, *ui)+1; |
| put(priority, *ui, W1*dist[index_map[*ui]]-W2*cdeg ); |
| } |
| |
| //Priority list |
| typedef indirect_cmp<PriorityMap, std::greater<Degree> > Compare; |
| Compare comp(priority); |
| std::list<Vertex> priority_list; |
| |
| //Some more declarations |
| typename graph_traits<Graph>::out_edge_iterator ei, ei_end, ei2, ei2_end; |
| Vertex u, v, w; |
| |
| put(color, s, Color::green()); //Sets the color of the starting vertex to gray |
| priority_list.push_front(s); //Puts s into the priority_list |
| |
| while ( !priority_list.empty() ) |
| { |
| priority_list.sort(comp); //Orders the elements in the priority list in an ascending manner |
| |
| u = priority_list.front(); //Accesses the last element in the priority list |
| priority_list.pop_front(); //Removes the last element in the priority list |
| |
| if(get(color, u) == Color::green() ) |
| { |
| //for-loop over all out-edges of vertex u |
| for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) |
| { |
| v = target(*ei, g); |
| |
| put( priority, v, get(priority, v) + W2 ); //updates the priority |
| |
| if (get(color, v) == Color::white() ) //test if the vertex is inactive |
| { |
| put(color, v, Color::green() ); //giving the vertex a preactive status |
| priority_list.push_front(v); //writing the vertex in the priority_queue |
| } |
| } |
| } |
| |
| //Here starts step 8 |
| *permutation++ = u; //Puts u to the first position in the permutation-vector |
| put(color, u, Color::black() ); //Gives u an inactive status |
| |
| //for loop over all the adjacent vertices of u |
| for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { |
| |
| v = target(*ei, g); |
| |
| if (get(color, v) == Color::green() ) { //tests if the vertex is inactive |
| |
| put(color, v, Color::red() ); //giving the vertex an active status |
| put(priority, v, get(priority, v)+W2); //updates the priority |
| |
| //for loop over alll adjacent vertices of v |
| for (boost::tie(ei2, ei2_end) = out_edges(v, g); ei2 != ei2_end; ++ei2) { |
| w = target(*ei2, g); |
| |
| if(get(color, w) != Color::black() ) { //tests if vertex is postactive |
| |
| put(priority, w, get(priority, w)+W2); //updates the priority |
| |
| if(get(color, w) == Color::white() ){ |
| |
| put(color, w, Color::green() ); // gives the vertex a preactive status |
| priority_list.push_front(w); // puts the vertex into the priority queue |
| |
| } //end if |
| |
| } //end if |
| |
| } //end for |
| |
| } //end if |
| |
| } //end for |
| |
| } //end while |
| |
| |
| return permutation; |
| } |
| |
| ///////////////////////////////////////////////////////////////////////////////////////// |
| // Same algorithm as before, but without the weights given (taking default weights |
| template <class Graph, class OutputIterator, |
| class ColorMap, class DegreeMap, |
| class PriorityMap> |
| OutputIterator |
| sloan_ordering(Graph& g, |
| typename graph_traits<Graph>::vertex_descriptor s, |
| typename graph_traits<Graph>::vertex_descriptor e, |
| OutputIterator permutation, |
| ColorMap color, |
| DegreeMap degree, |
| PriorityMap priority) |
| { |
| return sloan_ordering(g, s, e, permutation, color, degree, priority, WEIGHT1, WEIGHT2); |
| } |
| |
| |
| ////////////////////////////////////////////////////////////////////////// |
| // Sloan algorithm without a given starting Vertex. |
| // |
| // This algorithm finds a good starting vertex itself to |
| // compute Sloan-ordering. |
| ////////////////////////////////////////////////////////////////////////// |
| |
| |
| |
| template < class Graph, class OutputIterator, |
| class Color, class Degree, |
| class Priority, class Weight> |
| inline OutputIterator |
| sloan_ordering(Graph& G, |
| OutputIterator permutation, |
| Color color, |
| Degree degree, |
| Priority priority, |
| Weight W1, |
| Weight W2 ) |
| { |
| typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; |
| |
| Vertex s, e; |
| e = sloan_start_end_vertices(G, s, color, degree); |
| |
| return sloan_ordering(G, s, e, permutation, color, degree, priority, W1, W2); |
| } |
| |
| ///////////////////////////////////////////////////////////////////////////////////////// |
| // Same as before, but without given weights (default weights are taken instead) |
| template < class Graph, class OutputIterator, |
| class Color, class Degree, |
| class Priority > |
| inline OutputIterator |
| sloan_ordering(Graph& G, |
| OutputIterator permutation, |
| Color color, |
| Degree degree, |
| Priority priority) |
| { |
| return sloan_ordering(G, permutation, color, degree, priority, WEIGHT1, WEIGHT2); |
| } |
| |
| |
| } // namespace boost |
| |
| |
| #endif // BOOST_GRAPH_SLOAN_HPP |