1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0063)http://www.boost.org/libs/graph/doc/cuthill_mckee_ordering.html -->
<HTML><HEAD><TITLE>Boost Graph Library: Sloan Ordering</TITLE>
<META http-equiv=Content-Type content="text/html; charset=windows-1252"><!--
-- Copyright (c) Jeremy Siek 2000
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Silicon Graphics makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
-->
<META content="MSHTML 6.00.2715.400" name=GENERATOR></HEAD>
<BODY text=#000000 vLink=#551a8b aLink=#ff0000 link=#0000ee bgColor=#ffffff>
<IMG SRC="../../../boost.png"
ALT="C++ Boost" width="277" height="86"> <BR>
<H1><A name=sec:bfs></a><tt>sloan_ordering</tt></H1>
<P>
<DIV align=left>
<TABLE cellPadding=3 border=1>
<TBODY>
<TR>
<TH align=left><B>Graphs:</B></TH>
<TD align=left>undirected</TD></TR>
<TR>
<TH align=left><B>Properties:</B></TH>
<TD align=left>color, degree, current_degree, priority</TD>
</TR>
<TR>
<TH align=left><B>Complexity:</B></TH>
<TD align=left>time: <I>O(log(m)|E|)</I> where <I>m = max { degree(v) | v
in V }</I> </TD></TR></TBODY></TABLE></DIV>
<PRE> (1)
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 )
(2)
template <class Graph, class OutputIterator,
class ColorMap, class DegreeMap,
class PriorityMap, class Weight>
OutputIterator
sloan_ordering(Graph& g,
OutputIterator permutation,
ColorMap color,
DegreeMap degree,
PriorityMap priority,
Weight W1,
Weight W2 )
(3)
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 )
(4)
template <class Graph, class OutputIterator,
class ColorMap, class DegreeMap,
class PriorityMap>
OutputIterator
sloan_ordering(Graph& g,
OutputIterator permutation,
ColorMap color,
DegreeMap degree,
PriorityMap priority )</PRE>
<p>The goal of the Sloan ordering algorithm[1, 2] is to reduce the profile and
the wavefront of a graph by reordering the indices assigned to each vertex.
The Sloan algorithm needs a start and an end vertex. These vertices can be asigned
manually. But there is also an algorithm sloan_starting_nodes that provides
usually quite good start and end vertices. Each vertex is asigned with a priority.
This priority is a weighted sum of the distance of the vector to the end vertex
(a global criterium) and is called the current degree of vertex. This current
degree basically reflects the status of the renumbering in the neighborhood
of a vertex (a local criterium). Therefore the Sloan algorithm (in contrast
to-McKee) takes into account local as well as global criteria for the renumbering
sequence. One can play around with the relative weights, but the default values
proposed by Sloan (weight1/weight2=1/2) turn out to be pretty good in most cases.
</p>
<P>Version 1 of the algorithm lets the user choose the start- and end-vertex whereas
version 2 finds a good starting vertex using the already mentioned sloan_starting_node
algorithm. The choice of these vertices can have a significant effect on the
quality of the ordering. Version 3 and 4 are identical to version 1 and 2 respectively,
except that for the weights the standard weights W1=1 and W2=2 are used.
<P>The output of the algorithm are the vertices in the new ordering. Depending
on what kind of output iterator you use, you can get either the Sloan ordering
or the reverse Sloan ordering. For example, if you store the output into a vector
using the vector's reverse iterator, then you get the reverse Sloan ordering.
<PRE> std::vector<vertex_descriptor> inv_perm(num_vertices(G));
sloan_ordering(G, inv_perm.rbegin());
</PRE>
<P>Either way, storing the output into a vector gives you the permutation from
the new ordering to the old ordering. <PRE> inv_perm[new_index[u]] == u
</PRE>
<P>Sometimes, it is the opposite permutation that you want, the permutation from
the old index to the new index. This can easily be computed in the following
way.
<PRE> for (size_type i = 0; i != inv_perm.size(); ++i)
perm[old_index[inv_perm[i]]] = i;
</PRE>
<p>Usually you need the reversed ordering with the Cuthill-McKee algorithm and
the direct ordering with the Sloan algorithm.</p>
<H3>Parameters</H3>
For version 1:
<UL>
<LI><TT>Graph& g</TT> (IN) <BR>
An undirected graph. The graph's type must be a model of <A
href="./IncidenceGraph.html">IncidenceGraph</a>.
<LI><TT>vertex_descriptor s</TT> (IN) <BR>
The starting vertex.
<LI><tt>vertex_descriptor e</tt> (IN)<br>
The ending vertex<br>
<LI><TT>OutputIterator permutation</TT> (OUT) <BR>
The new vertex ordering. The vertices are written to the <a
href="http://www.sgi.com/tech/stl/OutputIterator.html">output iterator</a> in
their new order.
<LI><TT>ColorMap color_map</TT> (WORK) <BR>
Used internally to keep track of the progress of the algorithm (to avoid visiting
the same vertex twice).
<LI><tt>PriorityMap priority_map</tt> (IN)<br>
Used internally to store the priority for renumbering of each vertex. </LI>
<LI><TT>DegreeMap degree_map</TT> (IN) <BR>
This must map vertices to their degree. </LI>
<LI><tt>Weight W1 & W2</tt> (IN) <br>
Heuristical weights for the Sloan algorithm. </LI>
</UL>
<p>For version 2: </p>
<ul>
<li><tt>Graph& g</tt> (IN) <br>
An undirected graph. The graph's type must be a model of <a
href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
<li><tt>OutputIterator permutation</tt> (OUT) <br>
The new vertex ordering. The vertices are written to the <a
href="http://www.sgi.com/tech/stl/OutputIterator.html">output iterator</a> in
their new order.
<li><tt>ColorMap color_map</tt> (WORK) <br>
Used internally to keep track of the progress of the algorithm (to avoid visiting
the same vertex twice).
<li><tt>PriorityMap priority_map</tt> (IN)<br>
Used internally to store the priority for renumbering of each vertex. </li>
<li><tt>DegreeMap degree_map</tt> (IN) <br>
This must map vertices to their degree. </li>
<li><tt>Weight W1 & W2</tt> (IN) <br>
Heuristical weights for the Sloan algorithm. </li>
</ul>
<p>For version 3: </p>
<ul>
<li><tt>Graph& g</tt> (IN) <br>
An undirected graph. The graph's type must be a model of <a
href="./IncidenceGraph.html">IncidenceGraph</a>.
<li><tt>vertex_descriptor s</tt> (IN) <br>
The starting vertex.
<li><tt>vertex_descriptor e</tt> (IN)<br>
The ending vertex<br>
<li><tt>OutputIterator permutation</tt> (OUT) <br>
The new vertex ordering. The vertices are written to the <a
href="http://www.sgi.com/tech/stl/OutputIterator.html">output iterator</a> in
their new order.
<li><tt>ColorMap color_map</tt> (WORK) <br>
Used internally to keep track of the progress of the algorithm (to avoid visiting
the same vertex twice).
<li><tt>PriorityMap priority_map</tt> (IN)<br>
Used internally to store the priority for renumbering of each vertex. </li>
<li><tt>DegreeMap degree_map</tt> (IN) <br>
This must map vertices to their degree. </li>
</ul>
<p>For version 4: </p>
<ul>
<li><tt>Graph& g</tt> (IN) <br>
An undirected graph. The graph's type must be a model of <a
href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
<li><tt>OutputIterator permutation</tt> (OUT) <br>
The new vertex ordering. The vertices are written to the <a
href="http://www.sgi.com/tech/stl/OutputIterator.html">output iterator</a> in
their new order.
<li><tt>ColorMap color_map</tt> (WORK) <br>
Used internally to keep track of the progress of the algorithm (to avoid visiting
the same vertex twice).
<li><tt>PriorityMap priority_map</tt> (IN)<br>
Used internally to store the priority for renumbering of each vertex. </li>
<li><tt>DegreeMap degree_map</tt> (IN) <br>
This must map vertices to their degree. </li>
</ul>
<p> </p>
<H3>Example</H3>
See <A
href="../example/sloan_ordering.cpp"><TT>example/sloan_ordering.cpp</TT></A>.
<H3>See Also</H3>
<p><http://www.boost.org/libs/graph/doc/sloan_start_end_vertices.htm><a href="./sloan_start_end_vertices.htm">sloan_start_end_vertices</a></http:>,
<A
href="./bandwidth.html">bandwidth</a>, <a href="./profile.htm">profile</a>, <a href="./wavefront.htm">wavefront</a>
and <TT>degree_property_map</TT> in <TT>boost/graph/properties.hpp</TT>. </p>
<p>[1] S. W. Sloan, <i>An algorithm for profile and wavefront reduction of sparse
matrices</i>, Int. j. numer. methods eng., <b>23</b>, 239 - 251 (1986)</p>
<p>[2] S. W. Sloan, <i>A fortran program for profile and wavefront reduction</i>,
Int. j. numer. methods eng., <b>28</b>, 2651 - 2679 (1989)<BR>
</p>
<HR>
<TABLE width="718">
<TBODY>
<TR vAlign=top>
<TD noWrap>Copyright 2001-2002</TD>
<TD>Marc Wintermantel, ETH Zurich (<A
href="mailto:wintermantel@imes.mavt.ethz.ch">wintermantel@imes.mavt.ethz.ch</a>)
</TD>
</TR></TBODY></TABLE></BODY></HTML>
|
