87 lines
3.8 KiB
HTML
87 lines
3.8 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
|
||
<!-- saved from url=(0063)http://www.boost.org/libs/graph/doc/cuthill_mckee_ordering.html -->
|
||
<HTML><HEAD><TITLE>Boost Graph Library: Cuthill-Mckee Ordering</TITLE>
|
||
<META http-equiv=Content-Type content="text/html; charset=windows-1252"><!--
|
||
-- Copyright (c) Jeremy Siek 2000
|
||
--
|
||
-- Distributed under the Boost Software License, Version 1.0.
|
||
-- (See accompanying file LICENSE_1_0.txt or copy at
|
||
-- http://www.boost.org/LICENSE_1_0.txt)
|
||
-->
|
||
<META content="MSHTML 6.00.2715.400" name=GENERATOR></HEAD>
|
||
<BODY text=#000000 vLink=#551a8b aLink=#ff0000 link=#0000ee bgColor=#ffffff><IMG
|
||
height=86 alt="C++ Boost"
|
||
src="../../../boost.png" width=277>
|
||
<BR>
|
||
<H1><A name=sec:bfs></a><tt>sloan_start_end_vertices</tt></H1>
|
||
<P>
|
||
<DIV align=left>
|
||
<TABLE cellPadding=3 border=1>
|
||
<TBODY>
|
||
<TR>
|
||
<TH align=left><B>Graphs:</B></TH>
|
||
<TD align=left>undirected</TD></TR>
|
||
<TR>
|
||
<TH align=left><B>Properties:</B></TH>
|
||
<TD align=left>color, degree</TD>
|
||
</TR>
|
||
<TR>
|
||
<TH align=left><B>Complexity:</B></TH>
|
||
<TD align=left> </TD>
|
||
</TR></TBODY></TABLE></DIV>
|
||
<PRE> (1)
|
||
template <class Graph, class ColorMap, class DegreeMap>
|
||
typename graph_traits<Graph>::vertex_descriptor
|
||
sloan_start_end_vertices(Graph& G,
|
||
typename graph_traits<Graph>::vertex_descriptor &s,
|
||
ColorMap color,
|
||
DegreeMap degree )
|
||
</PRE>
|
||
<p>The goal of the sloan_start_end_vertices algorithm[1, 2] is to find good start-
|
||
and end-vertices for the profile and wavefront reduction algorithm sloan_ordering.
|
||
The algorithm is similar to pseudo_peripheral_pair and also based on breadth_first_search.
|
||
With this breadth_first_search function a so-called rooted level structure (RLS)
|
||
is formed, where the vertices with the same distance to the starting vertex
|
||
are grouped together. The maximum number of vertices in one group is called
|
||
the width of the RLS. Sloan_start_end_vertices tries to find a pseudoperipheral
|
||
pair with a minimum RLS-width.</p>
|
||
<H3>Parameters</H3>
|
||
For version 1:
|
||
<UL>
|
||
<LI><TT>Graph& g</TT> (IN) <BR>
|
||
An undirected graph. The graph's type must be a model of <A
|
||
href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">IncidenceGraph</A>.
|
||
<LI><TT>vertex_descriptor s</TT> (IN) <BR>
|
||
The starting vertex.
|
||
<LI><TT>ColorMap color_map</TT> (WORK) <BR>
|
||
Used internally to keep track of the progress of the algorithm (to avoid visiting
|
||
the same vertex twice).
|
||
<LI><TT>DegreeMap degree_map</TT> (IN) <BR>
|
||
This must map vertices to their degree. </LI>
|
||
</UL>
|
||
<p> </p>
|
||
<H3>Example</H3>
|
||
See <A
|
||
href="http://www.boost.org/libs/graph/example/cuthill_mckee_ordering.cpp"><TT>example/sloan_ordering.cpp</TT></A>.
|
||
<H3>See Also</H3>
|
||
<p><a href="http://www.boost.org/libs/graph/doc/sloan_start_end_vertices.htm">sloan_start_end_vertices</a>,
|
||
<A
|
||
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>,
|
||
<a href="http://www.boost.org/libs/graph/doc/wavefront.htm">wavefront</a> and
|
||
<TT>degree_property_map</TT> in <TT>boost/graph/properties.hpp</TT>. </p>
|
||
<p>[1] S. W. Sloan, <i>An algorithm for profile and wavefront reduction of sparse
|
||
matrices</i>, Int. j. numer. methods eng., <b>23</b>, 239 - 251 (1986)</p>
|
||
<p>[2] S. W. Sloan, <i>A fortran program for profile and wavefront reduction</i>,
|
||
Int. j. numer. methods eng., <b>28</b>, 2651 - 2679 (1989)<BR>
|
||
</p>
|
||
<HR>
|
||
|
||
<TABLE width="663">
|
||
<TBODY>
|
||
<TR vAlign=top>
|
||
<TD noWrap>Copyright <20> 2001-2002</TD>
|
||
<TD>Marc Wintermantel, ETH Zurich(<A
|
||
href="mailto:wintermantel@imes.mavt.ethz.ch">wintermantel@imes.mavt.ethz.ch</a>)
|
||
</TD>
|
||
</TR></TBODY></TABLE></BODY></HTML>
|