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