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

Revision 857, 16.5 KB checked in by igarcia, 19 years ago (diff)
Line 
1//
2//=======================================================================
3// Copyright 2002 Marc Wintermantel (wintermantel@imes.mavt.ethz.ch)
4// ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st)
5//
6// This file is part of the Boost Graph Library
7//
8// You should have received a copy of the License Agreement for the
9// Boost Graph Library along with the software; see the file LICENSE.
10// If not, contact Office of Research, University of Notre Dame, Notre
11// Dame, IN 46556.
12//
13// Permission to modify the code and to distribute modified code is
14// granted, provided the text of this NOTICE is retained, a notice that
15// the code was modified is included with the above COPYRIGHT NOTICE and
16// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
17// file is distributed with the modified code.
18//
19// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
20// By way of example, but not limitation, Licensor MAKES NO
21// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
22// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
23// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
24// OR OTHER RIGHTS.
25//=======================================================================
26//
27
28#ifndef BOOST_GRAPH_SLOAN_HPP
29#define BOOST_GRAPH_SLOAN_HPP
30
31#define WEIGHT1 1               //default weight for the distance in the Sloan algorithm
32#define WEIGHT2 2               //default weight for the degree in the Sloan algorithm
33#define MAXINT 2147483647       //Maximum value for a 32bit integer
34
35#include <boost/config.hpp>
36#include <vector>
37#include <queue>
38#include <boost/pending/queue.hpp>
39#include <boost/graph/graph_traits.hpp>
40#include <boost/graph/breadth_first_search.hpp>
41#include <boost/graph/properties.hpp>
42#include <boost/pending/indirect_cmp.hpp>
43#include <boost/property_map.hpp>
44#include <algorithm>
45#include <utility>
46#include <boost/graph/visitors.hpp>
47#include <boost/graph/adjacency_list.hpp>
48#include <boost/graph/cuthill_mckee_ordering.hpp>
49
50
51////////////////////////////////////////////////////////////
52//
53//Sloan-Algorithm for graph reordering
54//(optimzes profile and wavefront, not primiraly bandwidth
55//
56////////////////////////////////////////////////////////////
57
58namespace boost {
59       
60  /////////////////////////////////////////////////////////////////////////
61  // Function that returns the maximum depth of
62  // a rooted level strucutre (RLS)
63  //
64  /////////////////////////////////////////////////////////////////////////
65  template<class Distance>
66  unsigned RLS_depth(Distance& d)
67  {
68    unsigned h_s = 0;
69    typename Distance::iterator iter;
70   
71    for (iter = d.begin(); iter != d.end(); ++iter)
72      {
73        if(*iter > h_s)
74          {
75            h_s = *iter;
76          }
77      }
78   
79    return h_s;
80  }
81
82
83   
84  /////////////////////////////////////////////////////////////////////////
85  // Function that returns the width of the largest level of
86  // a rooted level strucutre (RLS)
87  //
88  /////////////////////////////////////////////////////////////////////////
89  template<class Distance, class my_int>
90  unsigned RLS_max_width(Distance& d, my_int depth)
91  {
92   
93      //Searching for the maximum width of a level
94      std::vector<unsigned> dummy_width(depth+1, 0);
95      std::vector<unsigned>::iterator my_it;
96      typename Distance::iterator iter;
97      unsigned w_max = 0;
98     
99      for (iter = d.begin(); iter != d.end(); ++iter)
100      {
101          dummy_width[*iter]++;
102      }
103     
104      for(my_it = dummy_width.begin(); my_it != dummy_width.end(); ++my_it)
105      {
106          if(*my_it > w_max) w_max = *my_it;
107      }
108     
109      return w_max;
110     
111  }
112   
113
114  /////////////////////////////////////////////////////////////////////////
115  // Function for finding a good starting node for Sloan algorithm
116  //
117  // This is to find a good starting node. "good" is in the sense
118  // of the ordering generated.
119  /////////////////////////////////////////////////////////////////////////
120  template <class Graph, class ColorMap, class DegreeMap>
121  typename graph_traits<Graph>::vertex_descriptor
122  sloan_start_end_vertices(Graph& G,
123                           typename graph_traits<Graph>::vertex_descriptor &s,
124                           ColorMap color,
125                           DegreeMap degree)
126  {
127    typedef typename property_traits<DegreeMap>::value_type Degree;
128    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
129    typedef typename std::vector< typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
130    typedef typename graph_traits<Graph>::vertices_size_type size_type;
131   
132    typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;
133   
134    s = *(vertices(G).first);
135    Vertex e = s;
136    Vertex i;
137    unsigned my_degree = get(degree, s );
138    unsigned dummy, h_i, h_s, w_i, w_e;
139    bool new_start = true;
140    unsigned maximum_degree = 0;
141   
142    //Creating a std-vector for storing the distance from the start vertex in dist
143    std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(G), 0);
144
145    //Wrap a property_map_iterator around the std::iterator
146    boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, G));
147   
148    //Creating a property_map for the indices of a vertex
149    typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, G);
150   
151    //Creating a priority queue
152    typedef indirect_cmp<DegreeMap, std::greater<Degree> > Compare;
153    Compare comp(degree);
154    std::priority_queue<Vertex, std::vector<Vertex>, Compare> degree_queue(comp);
155   
156    //step 1
157    //Scan for the vertex with the smallest degree and the maximum degree
158    typename graph_traits<Graph>::vertex_iterator ui, ui_end;
159    for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
160    {
161      dummy = get(degree, *ui);
162     
163      if(dummy < my_degree)
164      {
165        my_degree = dummy;
166        s = *ui;
167      }
168     
169      if(dummy > maximum_degree)
170      {
171        maximum_degree = dummy;
172      }
173    }
174    //end 1
175   
176    do{ 
177      new_start = false;     //Setting the loop repetition status to false
178     
179      //step 2
180      //initialize the the disance std-vector with 0
181      for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
182     
183      //generating the RLS (rooted level structure)
184      breadth_first_search
185        (G, s, visitor
186         (
187           make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
188           )
189          );
190     
191      //end 2
192     
193      //step 3
194      //calculating the depth of the RLS
195      h_s = RLS_depth(dist);
196     
197      //step 4
198      //pushing one node of each degree in an ascending manner into degree_queue
199      std::vector<bool> shrink_trace(maximum_degree, false);
200      for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
201      {
202        dummy = get(degree, *ui);
203       
204        if( (dist[index_map[*ui]] == h_s ) && ( !shrink_trace[ dummy ] ) )
205        {
206          degree_queue.push(*ui);
207          shrink_trace[ dummy ] = true;
208        }
209      }
210     
211      //end 3 & 4
212
213     
214      //step 5
215      //Initializing w
216      w_e = MAXINT;
217      //end 5
218     
219     
220      //step 6
221      //Testing for termination
222      while( !degree_queue.empty() )
223      {
224        i = degree_queue.top();       //getting the node with the lowest degree from the degree queue
225        degree_queue.pop();           //ereasing the node with the lowest degree from the degree queue
226       
227        //generating a RLS         
228        for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
229       
230        breadth_first_search
231          (G, i, boost::visitor
232           (
233             make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
234             )
235            );
236       
237        //Calculating depth and width of the rooted level
238        h_i = RLS_depth(dist);
239        w_i = RLS_max_width(dist, h_i);
240       
241        //Testing for termination
242        if( (h_i > h_s) && (w_i < w_e) )
243        {
244          h_s = h_i;
245          s = i;
246          while(!degree_queue.empty()) degree_queue.pop();
247          new_start = true;         
248        }
249        else if(w_i < w_e)
250        {
251          w_e = w_i;
252          e = i;
253        }
254      }
255      //end 6
256       
257    }while(new_start);
258   
259    return e;
260  }
261
262  //////////////////////////////////////////////////////////////////////////
263  // Sloan algorithm with a given starting Vertex.
264  //
265  // This algorithm requires user to provide a starting vertex to
266  // compute Sloan ordering.
267  //////////////////////////////////////////////////////////////////////////
268  template <class Graph, class OutputIterator,
269            class ColorMap, class DegreeMap,
270            class PriorityMap, class Weight>
271  OutputIterator
272  sloan_ordering(Graph& g,
273                 typename graph_traits<Graph>::vertex_descriptor s,
274                 typename graph_traits<Graph>::vertex_descriptor e,
275                 OutputIterator permutation,
276                 ColorMap color,
277                 DegreeMap degree,
278                 PriorityMap priority,
279                 Weight W1,
280                 Weight W2)
281  {
282    //typedef typename property_traits<DegreeMap>::value_type Degree;
283    typedef typename property_traits<PriorityMap>::value_type Degree;
284    typedef typename property_traits<ColorMap>::value_type ColorValue;
285    typedef color_traits<ColorValue> Color;
286    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
287    typedef typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
288    typedef typename graph_traits<Graph>::vertices_size_type size_type;
289
290    typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;
291
292   
293    //Creating a std-vector for storing the distance from the end vertex in it
294    typename std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(g), 0);
295   
296    //Wrap a property_map_iterator around the std::iterator
297    boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, g));
298   
299    breadth_first_search
300      (g, e, visitor
301       (
302           make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
303        )
304       );
305   
306    //Creating a property_map for the indices of a vertex
307    typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, g);
308   
309    //Sets the color and priority to their initial status
310    unsigned cdeg;   
311    typename graph_traits<Graph>::vertex_iterator ui, ui_end;
312    for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
313    {
314        put(color, *ui, Color::white());
315        cdeg=get(degree, *ui)+1;
316        put(priority, *ui, W1*dist[index_map[*ui]]-W2*cdeg ); 
317    }
318   
319    //Priority list
320    typedef indirect_cmp<PriorityMap, std::greater<Degree> > Compare;
321    Compare comp(priority);
322    std::list<Vertex> priority_list;
323
324    //Some more declarations
325    typename graph_traits<Graph>::out_edge_iterator ei, ei_end, ei2, ei2_end;
326    Vertex u, v, w;
327
328    put(color, s, Color::green());      //Sets the color of the starting vertex to gray
329    priority_list.push_front(s);                 //Puts s into the priority_list
330   
331    while ( !priority_list.empty() )
332    { 
333      priority_list.sort(comp);         //Orders the elements in the priority list in an ascending manner
334     
335      u = priority_list.front();           //Accesses the last element in the priority list
336      priority_list.pop_front();               //Removes the last element in the priority list
337     
338      if(get(color, u) == Color::green() )
339      {
340        //for-loop over all out-edges of vertex u
341        for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
342        {
343          v = target(*ei, g);
344         
345          put( priority, v, get(priority, v) + W2 ); //updates the priority
346         
347          if (get(color, v) == Color::white() )      //test if the vertex is inactive
348          {
349            put(color, v, Color::green() );        //giving the vertex a preactive status
350            priority_list.push_front(v);                     //writing the vertex in the priority_queue
351          }           
352        }
353      }
354     
355      //Here starts step 8
356      *permutation++ = u;                      //Puts u to the first position in the permutation-vector
357      put(color, u, Color::black() );          //Gives u an inactive status
358     
359      //for loop over all the adjacent vertices of u
360      for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
361       
362        v = target(*ei, g);     
363       
364        if (get(color, v) == Color::green() ) {      //tests if the vertex is inactive
365         
366          put(color, v, Color::red() );        //giving the vertex an active status
367          put(priority, v, get(priority, v)+W2);  //updates the priority       
368         
369          //for loop over alll adjacent vertices of v
370          for (tie(ei2, ei2_end) = out_edges(v, g); ei2 != ei2_end; ++ei2) {
371            w = target(*ei2, g);
372           
373            if(get(color, w) != Color::black() ) {     //tests if vertex is postactive
374             
375              put(priority, w, get(priority, w)+W2);  //updates the priority
376             
377              if(get(color, w) == Color::white() ){
378               
379                put(color, w, Color::green() );   // gives the vertex a preactive status
380                priority_list.push_front(w);           // puts the vertex into the priority queue
381               
382              } //end if
383             
384            } //end if
385           
386          } //end for
387         
388        } //end if
389       
390      } //end for
391     
392    } //end while
393   
394   
395    return permutation;
396  } 
397 
398  /////////////////////////////////////////////////////////////////////////////////////////
399  // Same algorithm as before, but without the weights given (taking default weights
400  template <class Graph, class OutputIterator,
401            class ColorMap, class DegreeMap,
402            class PriorityMap>
403  OutputIterator
404  sloan_ordering(Graph& g,
405                 typename graph_traits<Graph>::vertex_descriptor s,
406                 typename graph_traits<Graph>::vertex_descriptor e,
407                 OutputIterator permutation,
408                 ColorMap color,
409                 DegreeMap degree,
410                 PriorityMap priority)
411  {
412    return sloan_ordering(g, s, e, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
413  }
414
415
416  //////////////////////////////////////////////////////////////////////////
417  // Sloan algorithm without a given starting Vertex.
418  //
419  // This algorithm finds a good starting vertex itself to
420  // compute Sloan-ordering.
421  //////////////////////////////////////////////////////////////////////////
422 
423
424
425  template < class Graph, class OutputIterator,
426             class Color, class Degree,
427             class Priority, class Weight>
428  inline OutputIterator
429  sloan_ordering(Graph& G,
430                 OutputIterator permutation,
431                 Color color,
432                 Degree degree,
433                 Priority priority,
434                 Weight W1,
435                 Weight W2 )
436  {
437    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
438   
439    Vertex s, e;
440    e = sloan_start_end_vertices(G, s, color, degree);
441   
442    return sloan_ordering(G, s, e, permutation, color, degree, priority, W1, W2);
443  }
444
445  /////////////////////////////////////////////////////////////////////////////////////////
446  // Same as before, but without given weights (default weights are taken instead)
447  template < class Graph, class OutputIterator,
448             class Color, class Degree,
449             class Priority >
450  inline OutputIterator
451  sloan_ordering(Graph& G,
452                 OutputIterator permutation,
453                 Color color,
454                 Degree degree,
455                 Priority priority)
456  {
457    return sloan_ordering(G, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
458  }
459 
460 
461} // namespace boost
462
463
464#endif // BOOST_GRAPH_SLOAN_HPP
Note: See TracBrowser for help on using the repository browser.