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