ceph/src/boost/libs/graph/doc/sloan_start_end_vertices.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: Cuthill-Mckee 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><IMG
  13 height=86 alt="C++ Boost"
  14 src="../../../boost.png" width=277>
  15 <BR>
  16 <H1><A name=sec:bfs></a><tt>sloan_start_end_vertices</tt></H1>
  17 <P>
  18 <DIV align=left>
  19 <TABLE cellPadding=3 border=1>
  20   <TBODY>
  21   <TR>
  22     <TH align=left><B>Graphs:</B></TH>
  23     <TD align=left>undirected</TD></TR>
  24   <TR>
  25     <TH align=left><B>Properties:</B></TH>
  26       <TD align=left>color, degree</TD>
  27     </TR>
  28   <TR>
  29     <TH align=left><B>Complexity:</B></TH>
  30       <TD align=left>&nbsp;</TD>
  31     </TR></TBODY></TABLE></DIV>
  32 <PRE>  (1)
  33   template &lt;class Graph, class ColorMap, class DegreeMap&gt;
  34   typename graph_traits&lt;Graph&gt;::vertex_descriptor
  35   sloan_start_end_vertices(Graph&amp; G,
  36                            typename graph_traits&lt;Graph&gt;::vertex_descriptor &amp;s,
  37                            ColorMap color,
  38                            DegreeMap degree )
  39 </PRE>
  40 <p>The goal of the sloan_start_end_vertices algorithm[1, 2] is to find good start-
  41   and end-vertices for the profile and wavefront reduction algorithm sloan_ordering.
  42   The algorithm is similar to pseudo_peripheral_pair and also based on breadth_first_search.
  43   With this breadth_first_search function a so-called rooted level structure (RLS)
  44   is formed, where the vertices with the same distance to the starting vertex
  45   are grouped together. The maximum number of vertices in one group is called
  46   the width of the RLS. Sloan_start_end_vertices tries to find a pseudoperipheral
  47   pair with a minimum RLS-width.</p>
  48 <H3>Parameters</H3>
  49 For version 1:
  50 <UL>
  51   <LI><TT>Graph&amp; g</TT> &nbsp;(IN) <BR>
  52     An undirected graph. The graph's type must be a model of <A
  53   href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">IncidenceGraph</A>.
  54   <LI><TT>vertex_descriptor s</TT> &nbsp;(IN) <BR>
  55     The starting vertex.
  56   <LI><TT>ColorMap color_map</TT> &nbsp;(WORK) <BR>
  57     Used internally to keep track of the progress of the algorithm (to avoid visiting
  58     the same vertex twice).
  59   <LI><TT>DegreeMap degree_map</TT> &nbsp;(IN) <BR>
  60     This must map vertices to their degree. </LI>
  61 </UL>
  62 <p>&nbsp;</p>
  63 <H3>Example</H3>
  64 See <A
  65 href="http://www.boost.org/libs/graph/example/cuthill_mckee_ordering.cpp"><TT>example/sloan_ordering.cpp</TT></A>.
  66 <H3>See Also</H3>
  67 <p><a href="http://www.boost.org/libs/graph/doc/sloan_start_end_vertices.htm">sloan_start_end_vertices</a>,
  68   <A
  69 href="http://www.boost.org/libs/graph/doc/bandwidth.html">bandwidth</A>, <a href="http://www.boost.org/libs/graph/doc/profile.htm">profile</a>,
  70   <a href="http://www.boost.org/libs/graph/doc/wavefront.htm">wavefront</a> and
  71   <TT>degree_property_map</TT> in <TT>boost/graph/properties.hpp</TT>. </p>
  72 <p>[1] S. W. Sloan, <i>An algorithm for profile and wavefront reduction of sparse
  73   matrices</i>, Int. j. numer. methods eng., <b>23</b>, 239 - 251 (1986)</p>
  74 <p>[2] S. W. Sloan, <i>A fortran program for profile and wavefront reduction</i>,
  75   Int. j. numer. methods eng., <b>28</b>, 2651 - 2679 (1989)<BR>
  76 </p>
  77 <HR>
  78
  79 <TABLE width="663">
  80   <TBODY>
  81   <TR vAlign=top>
  82     <TD noWrap>Copyright © 2001-2002</TD>
  83     <TD>Marc Wintermantel, ETH Zurich(<A
  84       href="mailto:wintermantel@imes.mavt.ethz.ch">wintermantel@imes.mavt.ethz.ch</a>)
  85     </TD>
  86   </TR></TBODY></TABLE></BODY></HTML>