Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/sloan_ordering.htm @ 14

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

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