ceph/src/boost/libs/graph/doc/king_ordering.html

   1 <HTML>
   2 <!--
   3   ~~ Copyright (c) Jeremy Siek 2000
   4   ~~
   5      Distributed under the Boost Software License, Version 1.0.
   6      (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8 -->
   9
  10
  11 <Head>
  12 <Title>Boost Graph Library: King Ordering</Title>
  13 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  14         ALINK="#ff0000">
  15 <IMG SRC="../../../boost.png"
  16      ALT="C++ Boost" width="277" height="86">
  17
  18 <BR Clear>
  19
  20 <H1>
  21 <img src="figs/python.gif" alt="(Python)"/>
  22 <TT>king_ordering</TT>
  23 </H1>
  24
  25
  26 <P>
  27 <DIV ALIGN="LEFT">
  28 <TABLE CELLPADDING=3 border>
  29 <TR><TH ALIGN="LEFT"><B>Graphs:</B></TH>
  30 <TD ALIGN="LEFT">undirected</TD>
  31 </TR>
  32 <TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
  33 <TD ALIGN="LEFT">color, degree</TD>
  34 </TR>
  35 <TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
  36 <TD ALIGN="LEFT">time: <i>O(m<sup>2</sup>log(m)|E|)</i> where <i>m = max { degree(v) | v in V }</i> </TD>
  37 </TR>
  38 </TABLE>
  39 </DIV>
  40
  41
  42 <pre>
  43   (1)
  44   template &lt;class IncidenceGraph, class OutputIterator,
  45             class ColorMap, class DegreeMap, class VertexIndexMap&gt;
  46   OutputIterator
  47   king_ordering(const IncidenceGraph&amp; g,
  48                 typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
  49                 OutputIterator inverse_permutation,
  50                 ColorMap color, DegreeMap degree, VertexIndexMap index_map);
  51
  52   (2)
  53   template &lt;class IncidenceGraph, class OutputIterator&gt;
  54   OutputIterator
  55   king_ordering(const IncidenceGraph&amp; g, OutputIterator inverse_permutation);
  56
  57   template &lt;class IncidenceGraph, class OutputItrator, class VertexIndexMap&gt;
  58   OutputIterator
  59   king_ordering(const IncidenceGraph&amp; g, OutputIterator inverse_permutation,
  60                 VertexIndexMap index_map);
  61
  62   template &lt;class VertexListGraph, class OutputIterator,
  63             class ColorMap, class DegreeMap, class VertexIndexMap&gt;
  64   OutputIterator
  65   king_ordering(const VertexListGraph&amp; G, OutputIterator inverse_permutation,
  66                 ColorMap color, DegreeMap degree, VertexIndexMap index_map);
  67
  68   (3)
  69   template &lt;class IncidenceGraph, class OutputIterator,
  70             class ColorMap, class DegreeMap, class VertexIndexMap&gt;
  71   OutputIterator
  72   king_ordering(const IncidenceGraph&amp; g,
  73                 std::deque&lt; typename
  74                 graph_traits&lt;Graph&gt;::vertex_descriptor &gt; vertex_queue,
  75                 OutputIterator permutation,
  76                 ColorMap color, DegreeMap degree, VertexIndexMap index_map);
  77 </pre>
  78
  79 <!-- King, I.P. An automatic reordering scheme for simultaneous equations derived from network analysis. Int. J. Numer. Methods Engrg. 2 (1970), 523-533 -->
  80
  81 The goal of the King ordering
  82 algorithm [<a href="bibliography.html#king70">62</a>]is to reduce the <a
  83 href="./bandwidth.html">bandwidth</a> of a graph by reordering the
  84 indices assigned to each vertex.  The King ordering algorithm
  85 works by a local minimization of the i-th bandwidths. The vertices are
  86 basically assigned a breadth-first search order, except that at each
  87 step, the adjacent vertices are placed in the queue in order of
  88 increasing pseudo-degree, where pseudo-degree is defined as the number of
  89 outgoing edges with white endpoints (vertices yet to be examined).
  90
  91 <p>
  92 Version 1 of the algorithm lets the user choose the ``starting
  93 vertex'', version 2 finds a good starting vertex using the
  94 pseudo-peripheral pair heuristic (among each component), while version 3
  95 contains the starting nodes for each vertex in the deque.  The choice of the ``starting
  96 vertex'' can have a significant effect on the quality of the ordering.
  97 </p>
  98
  99 <p>
 100 The output of the algorithm are the vertices in the new ordering.
 101 Storing the output into a vector gives you the
 102 permutation from the new ordering to the old ordering.
 103
 104 <pre>
 105   inv_perm[new_index[u]] == u
 106 </pre>
 107
 108 <p>
 109 Often times, it is the opposite permutation that you want, the
 110 permutation from the old index to the new index. This can easily be
 111 computed in the following way.
 112 </p>
 113
 114 <pre>
 115   for (size_type i = 0; i != inv_perm.size(); ++i)
 116     perm[old_index[inv_perm[i]]] = i;
 117 </pre>
 118
 119
 120
 121 <h3>Parameters</h3>
 122
 123 For version 1:
 124
 125 <ul>
 126
 127 <li> <tt>IncidenceGraph&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>.<br>
 130   <b>Python</b>: The parameter is named <tt>graph</tt>.
 131
 132 <li> <tt>vertex_descriptor s</tt> &nbsp(IN) <br>
 133   The starting vertex.<br>
 134   <b>Python</b>: Unsupported parameter.
 135
 136 <li> <tt>OutputIterator permutation</tt> &nbsp(OUT) <br>
 137   The new vertex ordering. The vertices are written to the <a
 138   href="http://www.sgi.com/tech/stl/OutputIterator.html">output
 139   iterator</a> in their new order. <br>
 140   <b>Python</b>: This parameter is unused in Python. The new vertex
 141   ordering is returned as a Python <tt>list</tt>.
 142
 143
 144 <li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
 145   Used internally to keep track of the progress of the algorithm
 146   (to avoid visiting the same vertex twice).<br>
 147   <b>Python</b>: Unsupported parameter.
 148
 149 <li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
 150   This must map vertices to their degree.<br>
 151   <b>Python</b>: Unsupported parameter.
 152
 153 </ul>
 154
 155
 156 For version 2:
 157
 158 <ul>
 159
 160 <li> <tt>VertexListGraph&amp; g</tt> &nbsp;(IN) <br>
 161   An undirected graph. The graph's type must be a model of <a
 162   href="./VertexListGraph.html">VertexListGraph</a>.<br>
 163   <b>Python</b>: The name of this parameter is <tt>graph</tt>.
 164
 165 <li> <tt><a href="http://www.sgi.com/tech/stl/OutputIterator.html">
 166   OutputIterator</a> permutation</tt> &nbsp(OUT) <br>
 167   The new vertex ordering. The vertices are written to the
 168   output iterator in their new order.<br>
 169   <b>Python</b>: This parameter is unused in Python. The new vertex
 170   ordering is returned as a Python <tt>list</tt>.
 171
 172 <li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
 173   Used internally to keep track of the progress of the algorithm
 174   (to avoid visiting the same vertex twice).<br>
 175   <b>Python</b>: Unsupported parameter.
 176
 177 <li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
 178   This must map vertices to their degree.<br>
 179   <b>Python</b>: Unsupported parameter.
 180 </ul>
 181
 182
 183 For version 3:
 184
 185 <ul>
 186
 187 <li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(IN) <br>
 188   An undirected graph. The graph's type must be a model of <a
 189   href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
 190   <b>Python</b>: The parameter is named <tt>graph</tt>.
 191
 192 <li> <tt> std::deque&lt; typename graph_traits&lt;Graph&gt;::vertex_descriptor &gt; vertex_queue </tt> &nbsp(IN) <br>
 193   The deque containing the starting vertices for each component.<br>
 194   <b>Python</b>: This parameter is unused in Python. The new vertex
 195   ordering is returned as a Python <tt>list</tt>.
 196
 197 <li> <tt>OutputIterator permutation</tt> &nbsp(OUT) <br>
 198   The new vertex ordering. The vertices are written to the <a
 199   href="http://www.sgi.com/tech/stl/OutputIterator.html">output
 200   iterator</a> in their new order.<br>
 201   <b>Python</b>: This parameter is unused in Python. The new vertex
 202   ordering is returned as a Python <tt>list</tt>.
 203
 204 <li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
 205   Used internally to keep track of the progress of the algorithm
 206   (to avoid visiting the same vertex twice).<br>
 207   <b>Python</b>: Unsupported parameter.
 208
 209 <li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
 210   This must map vertices to their degree.<br>
 211   <b>Python</b>: Unsupported parameter.
 212 </ul>
 213
 214
 215
 216 <h3>Example</h3>
 217
 218 See <a
 219 href="../example/king_ordering.cpp"><tt>example/king_ordering.cpp</tt></a>.
 220
 221 <h3>See Also</h3>
 222
 223 <a href="./bandwidth.html">bandwidth</tt></a>,
 224 and <tt>degree_property_map</tt> in <tt>boost/graph/properties.hpp</tt>.
 225
 226 <br>
 227 <HR>
 228 <TABLE>
 229 <TR valign=top>
 230 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 231 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
 232 </TD></TR></TABLE>
 233
 234 </BODY>
 235 </HTML>