ceph/src/boost/libs/graph/doc/cuthill_mckee_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 <Head>
  11 <Title>Boost Graph Library: Cuthill-Mckee Ordering</Title>
  12 </Head>
  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>cuthill_mckee_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 log(m)|V|)</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&gt;
  46   OutputIterator
  47   cuthill_mckee_ordering(const IncidenceGraph&amp; g,
  48                          typename graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor s,
  49                          OutputIterator inverse_permutation,
  50                          ColorMap color, DegreeMap degree)
  51
  52   (2)
  53   template &lt;class VertexListGraph, class OutputIterator&gt;
  54   OutputIterator
  55   cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation);
  56
  57   template &lt;class VertexListGraph, class OutputIterator, class VertexIndexMap&gt;
  58   OutputIterator
  59   cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation,
  60                          VertexIndexMap index_map);
  61
  62   template &lt;class VertexListGraph, class OutputIterator,
  63             class ColorMap, class DegreeMap&gt;
  64   OutputIterator
  65   cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation,
  66                          ColorMap color, DegreeMap degree)
  67
  68   (3)
  69   template &lt;class IncidenceGraph, class OutputIterator,
  70             class ColorMap, class DegreeMap&gt;
  71   OutputIterator
  72   cuthill_mckee_ordering(const IncidenceGraph&amp; g,
  73                          std::deque&lt; typename
  74                          graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor &gt; vertex_queue,
  75                          OutputIterator inverse_permutation,
  76                          ColorMap color, DegreeMap degree)
  77 </pre>
  78
  79 The goal of the Cuthill-Mckee (and reverse Cuthill-Mckee) ordering
  80 algorithm[<A
  81 HREF="bibliography.html#george81:__sparse_pos_def">14</A>, <A
  82 HREF="bibliography.html#cuthill69:reducing_bandwith">43</A>, <a
  83 href="bibliography.html#liu75:anal_cm_rcm">44</a>, <a
  84 href="bibliography.html#george71:fem">45</a> ] is to reduce the <a
  85 href="./bandwidth.html">bandwidth</a> of a graph by reordering the
  86 indices assigned to each vertex.  The Cuthill-Mckee ordering algorithm
  87 works by a local minimization of the i-th bandwidths. The vertices are
  88 basically assigned a breadth-first search order, except that at each
  89 step, the adjacent vertices are placed in the queue in order of
  90 increasing degree.
  91
  92 <p>
  93 Version 1 of the algorithm lets the user choose the ``starting
  94 vertex'', version 2 finds a good starting vertex using the
  95 pseudo-peripheral pair heuristic (among each component), while version 3
  96 contains the starting nodes for each vertex in the deque.  The choice of the
  97 ``starting vertex'' can have a significant effect on the quality of the
  98 ordering.  For versions 2 and 3, <tt>find_starting_vertex</tt> will be called
  99 for each component in the graph, increasing run time significantly.
 100 </p>
 101
 102 <p>
 103 The output of the algorithm are the vertices in the new ordering.
 104 Depending on what kind of output iterator you use, you can get either
 105 the Cuthill-Mckee ordering or the reverse Cuthill-McKee ordering.  For
 106 example, if you store the output into a vector using the vector's
 107 reverse iterator, then you get the reverse Cuthill-McKee ordering.
 108 </p>
 109
 110 <pre>
 111   std::vector&lt;vertex_descriptor&gt; inv_perm(num_vertices(G));
 112   cuthill_mckee_ordering(G, inv_perm.rbegin(), ...);
 113 </pre>
 114
 115 <p>
 116 Either way, storing the output into a vector gives you the
 117 permutation from the new ordering to the old ordering.
 118 </p>
 119
 120 <pre>
 121   inv_perm[new_index[u]] == u
 122 </pre>
 123
 124 <p>
 125 Often times, it is the opposite permutation that you want, the
 126 permutation from the old index to the new index. This can easily be
 127 computed in the following way.
 128 </p>
 129
 130 <pre>
 131   for (size_type i = 0; i != inv_perm.size(); ++i)
 132     perm[old_index[inv_perm[i]]] = i;
 133 </pre>
 134
 135
 136
 137 <h3>Parameters</h3>
 138
 139 For version 1:
 140
 141 <ul>
 142
 143 <li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(IN) <br>
 144   An undirected graph. The graph's type must be a model of <a
 145   href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
 146   <b>Python</b>: The parameter is named <tt>graph</tt>.
 147
 148 <li> <tt>vertex_descriptor s</tt> &nbsp(IN) <br>
 149   The starting vertex.<br>
 150   <b>Python</b>: Unsupported parameter.
 151
 152 <li> <tt>OutputIterator inverse_permutation</tt> &nbsp(OUT) <br>
 153   The new vertex ordering. The vertices are written to the <a
 154   href="http://www.sgi.com/tech/stl/OutputIterator.html">output
 155   iterator</a> in their new order.<br>
 156   <b>Python</b>: This parameter is unused in Python. The new vertex
 157   ordering is returned as a Python <tt>list</tt>.
 158
 159 <li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
 160   Used internally to keep track of the progress of the algorithm
 161   (to avoid visiting the same vertex twice).<br>
 162   <b>Python</b>: Unsupported parameter.
 163
 164 <li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
 165   This must map vertices to their degree.<br>
 166   <b>Python</b>: Unsupported parameter.
 167 </ul>
 168
 169
 170 For version 2:
 171
 172 <ul>
 173
 174 <li> <tt>VertexListGraph&amp; g</tt> &nbsp;(IN) <br>
 175   An undirected graph. The graph's type must be a model of <a
 176                                                               href="./VertexListGraph.html">VertexListGraph</a> and <a href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
 177   <b>Python</b>: The parameter is named <tt>graph</tt>.
 178
 179 <li> <tt><a href="http://www.sgi.com/tech/stl/OutputIterator.html">
 180   OutputIterator</a> inverse_permutation</tt> &nbsp(OUT) <br>
 181   The new vertex ordering. The vertices are written to the
 182   output iterator in their new order.<br>
 183   <b>Python</b>: This parameter is unused in Python. The new vertex
 184   ordering is returned as a Python <tt>list</tt>.
 185
 186 <li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
 187   Used internally to keep track of the progress of the algorithm
 188   (to avoid visiting the same vertex twice).<br>
 189   <b>Python</b>: Unsupported parameter.
 190
 191 <li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
 192   This must map vertices to their degree.<br>
 193   <b>Python</b>: Unsupported parameter.
 194 </ul>
 195
 196
 197 For version 3:
 198
 199 <ul>
 200
 201 <li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(IN) <br>
 202   An undirected graph. The graph's type must be a model of <a
 203   href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
 204   <b>Python</b>: The parameter is named <tt>graph</tt>.
 205
 206 <li> <tt> std::deque&lt; typename graph_traits&lt;Graph&gt;::vertex_descriptor &gt; vertex_queue </tt> &nbsp(IN) <br>
 207   The deque containing the starting vertices for each component.<br>
 208   <b>Python</b>: Unsupported parameter.
 209
 210 <li> <tt>OutputIterator inverse_permutation</tt> &nbsp(OUT) <br>
 211   The new vertex ordering. The vertices are written to the <a
 212   href="http://www.sgi.com/tech/stl/OutputIterator.html">output
 213   iterator</a> in their new order.<br>
 214   <b>Python</b>: This parameter is unused in Python. The new vertex
 215   ordering is returned as a Python <tt>list</tt>.
 216
 217 <li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
 218   Used internally to keep track of the progress of the algorithm
 219   (to avoid visiting the same vertex twice).<br>
 220   <b>Python</b>: Unsupported parameter.
 221
 222 <li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
 223   This must map vertices to their degree.<br>
 224   <b>Python</b>: Unsupported parameter.
 225 </ul>
 226
 227
 228
 229 <h3>Example</h3>
 230
 231 See <a
 232 href="../example/cuthill_mckee_ordering.cpp"><tt>example/cuthill_mckee_ordering.cpp</tt></a>.
 233
 234 <h3>See Also</h3>
 235
 236 <a href="./bandwidth.html">bandwidth</tt></a>,
 237 and <tt>degree_property_map</tt> in <tt>boost/graph/properties.hpp</tt>.
 238
 239 <br>
 240 <HR>
 241 <TABLE>
 242 <TR valign=top>
 243 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 244 <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>)
 245 </TD></TR></TABLE>
 246
 247 </BODY>
 248 </HTML>