Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/sloan_ordering.htm @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 10.2 KB
Line 
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 &lt;class Graph, class OutputIterator,
33                  class ColorMap, class DegreeMap,
34                  class PriorityMap, class Weight&gt;
35  OutputIterator
36  sloan_ordering(Graph&amp; g,
37                 typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
38                 typename graph_traits&lt;Graph&gt;::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 &lt;class Graph, class OutputIterator,
48                  class ColorMap, class DegreeMap,
49                  class PriorityMap, class Weight&gt;
50  OutputIterator
51  sloan_ordering(Graph&amp; 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 &lt;class Graph, class OutputIterator,
62                  class ColorMap, class DegreeMap,
63                  class PriorityMap&gt;
64  OutputIterator
65  sloan_ordering(Graph&amp; g,
66                 typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
67                 typename graph_traits&lt;Graph&gt;::vertex_descriptor e,
68                 OutputIterator permutation,
69                 ColorMap color,
70                 DegreeMap degree,
71                 PriorityMap priority )
72
73
74(4)
75 template &lt;class Graph, class OutputIterator,
76                  class ColorMap, class DegreeMap,
77                  class PriorityMap&gt;
78  OutputIterator
79  sloan_ordering(Graph&amp; 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&lt;vertex_descriptor&gt; 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
110the 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>
121For version 1:
122<UL>
123  <LI><TT>Graph&amp; g</TT> &nbsp;(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> &nbsp;(IN) <BR>
127    The starting vertex.
128  <LI><tt>vertex_descriptor e</tt>&nbsp;(IN)<br>
129    The ending vertex<br>
130  <LI><TT>OutputIterator permutation</TT> &nbsp;(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> &nbsp;(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> &nbsp;(IN)<br>
138    Used internally to store the priority for renumbering of each vertex. </LI>
139  <LI><TT>DegreeMap degree_map</TT> &nbsp;(IN) <BR>
140    This must map vertices to their degree. </LI>
141  <LI><tt>Weight W1 &amp; W2</tt> &nbsp;(IN) <br>
142    Heuristical weights for the Sloan algorithm. </LI>
143</UL>
144<p>For version 2: </p>
145<ul>
146  <li><tt>Graph&amp; g</tt> &nbsp;(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> &nbsp;(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> &nbsp;(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> &nbsp;(IN)<br>
157    Used internally to store the priority for renumbering of each vertex. </li>
158  <li><tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>
159    This must map vertices to their degree. </li>
160  <li><tt>Weight W1 &amp; W2</tt> &nbsp;(IN) <br>
161    Heuristical weights for the Sloan algorithm. </li>
162</ul>
163<p>For version 3: </p>
164<ul>
165  <li><tt>Graph&amp; g</tt> &nbsp;(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> &nbsp;(IN) <br>
169    The starting vertex.
170  <li><tt>vertex_descriptor e</tt>&nbsp;(IN)<br>
171    The ending vertex<br>
172  <li><tt>OutputIterator permutation</tt> &nbsp;(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> &nbsp;(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> &nbsp;(IN)<br>
180    Used internally to store the priority for renumbering of each vertex. </li>
181  <li><tt>DegreeMap degree_map</tt> &nbsp;(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&amp; g</tt> &nbsp;(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> &nbsp;(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> &nbsp;(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> &nbsp;(IN)<br>
197    Used internally to store the priority for renumbering of each vertex. </li>
198  <li><tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>
199    This must map vertices to their degree. </li>
200</ul>
201<p>&nbsp;</p>
202<H3>Example</H3>
203See <A 
204href="../example/sloan_ordering.cpp"><TT>example/sloan_ordering.cpp</TT></A>.
205<H3>See Also</H3>
206<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:>,
207  <A 
208href="./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    <TD noWrap>Copyright © 2001-2002</TD>
221    <TD>Marc Wintermantel, ETH Zurich (<A 
222      href="mailto:wintermantel@imes.mavt.ethz.ch">wintermantel@imes.mavt.ethz.ch</a>)
223    </TD>
224  </TR></TBODY></TABLE></BODY></HTML>
Note: See TracBrowser for help on using the repository browser.