ceph/src/boost/libs/graph/doc/sloan_ordering.htm

   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
 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&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>
 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     <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>