225 lines
10 KiB
HTML
225 lines
10 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: Sloan 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 SRC="../../../boost.png"
|
||
ALT="C++ Boost" width="277" height="86"> <BR>
|
||
<H1><A name=sec:bfs></a><tt>sloan_ordering</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, current_degree, priority</TD>
|
||
</TR>
|
||
<TR>
|
||
<TH align=left><B>Complexity:</B></TH>
|
||
<TD align=left>time: <I>O(log(m)|E|)</I> where <I>m = max { degree(v) | v
|
||
in V }</I> </TD></TR></TBODY></TABLE></DIV>
|
||
<PRE> (1)
|
||
template <class Graph, class OutputIterator,
|
||
class ColorMap, class DegreeMap,
|
||
class PriorityMap, class Weight>
|
||
OutputIterator
|
||
sloan_ordering(Graph& g,
|
||
typename graph_traits<Graph>::vertex_descriptor s,
|
||
typename graph_traits<Graph>::vertex_descriptor e,
|
||
OutputIterator permutation,
|
||
ColorMap color,
|
||
DegreeMap degree,
|
||
PriorityMap priority,
|
||
Weight W1,
|
||
Weight W2 )
|
||
|
||
(2)
|
||
template <class Graph, class OutputIterator,
|
||
class ColorMap, class DegreeMap,
|
||
class PriorityMap, class Weight>
|
||
OutputIterator
|
||
sloan_ordering(Graph& g,
|
||
OutputIterator permutation,
|
||
ColorMap color,
|
||
DegreeMap degree,
|
||
PriorityMap priority,
|
||
Weight W1,
|
||
Weight W2 )
|
||
|
||
|
||
(3)
|
||
template <class Graph, class OutputIterator,
|
||
class ColorMap, class DegreeMap,
|
||
class PriorityMap>
|
||
OutputIterator
|
||
sloan_ordering(Graph& g,
|
||
typename graph_traits<Graph>::vertex_descriptor s,
|
||
typename graph_traits<Graph>::vertex_descriptor e,
|
||
OutputIterator permutation,
|
||
ColorMap color,
|
||
DegreeMap degree,
|
||
PriorityMap priority )
|
||
|
||
|
||
(4)
|
||
template <class Graph, class OutputIterator,
|
||
class ColorMap, class DegreeMap,
|
||
class PriorityMap>
|
||
OutputIterator
|
||
sloan_ordering(Graph& g,
|
||
OutputIterator permutation,
|
||
ColorMap color,
|
||
DegreeMap degree,
|
||
PriorityMap priority )</PRE>
|
||
<p>The goal of the Sloan ordering algorithm[1, 2] is to reduce the profile and
|
||
the wavefront of a graph by reordering the indices assigned to each vertex.
|
||
The Sloan algorithm needs a start and an end vertex. These vertices can be asigned
|
||
manually. But there is also an algorithm sloan_starting_nodes that provides
|
||
usually quite good start and end vertices. Each vertex is asigned with a priority.
|
||
This priority is a weighted sum of the distance of the vector to the end vertex
|
||
(a global criterion) and is called the current degree of vertex. This current
|
||
degree basically reflects the status of the renumbering in the neighborhood
|
||
of a vertex (a local criterion). Therefore the Sloan algorithm (in contrast
|
||
to-McKee) takes into account local as well as global criteria for the renumbering
|
||
sequence. One can play around with the relative weights, but the default values
|
||
proposed by Sloan (weight1/weight2=1/2) turn out to be pretty good in most cases.
|
||
</p>
|
||
<P>Version 1 of the algorithm lets the user choose the start- and end-vertex whereas
|
||
version 2 finds a good starting vertex using the already mentioned sloan_starting_node
|
||
algorithm. The choice of these vertices can have a significant effect on the
|
||
quality of the ordering. Version 3 and 4 are identical to version 1 and 2 respectively,
|
||
except that for the weights the standard weights W1=1 and W2=2 are used.
|
||
<P>The output of the algorithm are the vertices in the new ordering. Depending
|
||
on what kind of output iterator you use, you can get either the Sloan ordering
|
||
or the reverse Sloan ordering. For example, if you store the output into a vector
|
||
using the vector's reverse iterator, then you get the reverse Sloan ordering.
|
||
<PRE> std::vector<vertex_descriptor> inv_perm(num_vertices(G));
|
||
sloan_ordering(G, inv_perm.rbegin());
|
||
</PRE>
|
||
<P>Either way, storing the output into a vector gives you the permutation from
|
||
the new ordering to the old ordering. <PRE> inv_perm[new_index[u]] == u
|
||
</PRE>
|
||
<P>Sometimes, it is the opposite permutation that you want, the permutation from
|
||
the old index to the new index. This can easily be computed in the following
|
||
way.
|
||
<PRE> for (size_type i = 0; i != inv_perm.size(); ++i)
|
||
perm[old_index[inv_perm[i]]] = i;
|
||
</PRE>
|
||
<p>Usually you need the reversed ordering with the Cuthill-McKee algorithm and
|
||
the direct ordering with the Sloan algorithm.</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="./IncidenceGraph.html">IncidenceGraph</a>.
|
||
<LI><TT>vertex_descriptor s</TT> (IN) <BR>
|
||
The starting vertex.
|
||
<LI><tt>vertex_descriptor e</tt> (IN)<br>
|
||
The ending vertex<br>
|
||
<LI><TT>OutputIterator permutation</TT> (OUT) <BR>
|
||
The new vertex ordering. The vertices are written to the <a
|
||
href="http://www.boost.org/sgi/stl/OutputIterator.html">output iterator</a> in
|
||
their new order.
|
||
<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>PriorityMap priority_map</tt> (IN)<br>
|
||
Used internally to store the priority for renumbering of each vertex. </LI>
|
||
<LI><TT>DegreeMap degree_map</TT> (IN) <BR>
|
||
This must map vertices to their degree. </LI>
|
||
<LI><tt>Weight W1 & W2</tt> (IN) <br>
|
||
Heuristical weights for the Sloan algorithm. </LI>
|
||
</UL>
|
||
<p>For version 2: </p>
|
||
<ul>
|
||
<li><tt>Graph& g</tt> (IN) <br>
|
||
An undirected graph. The graph's type must be a model of <a
|
||
href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
|
||
<li><tt>OutputIterator permutation</tt> (OUT) <br>
|
||
The new vertex ordering. The vertices are written to the <a
|
||
href="http://www.boost.org/sgi/stl/OutputIterator.html">output iterator</a> in
|
||
their new order.
|
||
<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>PriorityMap priority_map</tt> (IN)<br>
|
||
Used internally to store the priority for renumbering of each vertex. </li>
|
||
<li><tt>DegreeMap degree_map</tt> (IN) <br>
|
||
This must map vertices to their degree. </li>
|
||
<li><tt>Weight W1 & W2</tt> (IN) <br>
|
||
Heuristical weights for the Sloan algorithm. </li>
|
||
</ul>
|
||
<p>For version 3: </p>
|
||
<ul>
|
||
<li><tt>Graph& g</tt> (IN) <br>
|
||
An undirected graph. The graph's type must be a model of <a
|
||
href="./IncidenceGraph.html">IncidenceGraph</a>.
|
||
<li><tt>vertex_descriptor s</tt> (IN) <br>
|
||
The starting vertex.
|
||
<li><tt>vertex_descriptor e</tt> (IN)<br>
|
||
The ending vertex<br>
|
||
<li><tt>OutputIterator permutation</tt> (OUT) <br>
|
||
The new vertex ordering. The vertices are written to the <a
|
||
href="http://www.boost.org/sgi/stl/OutputIterator.html">output iterator</a> in
|
||
their new order.
|
||
<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>PriorityMap priority_map</tt> (IN)<br>
|
||
Used internally to store the priority for renumbering of each vertex. </li>
|
||
<li><tt>DegreeMap degree_map</tt> (IN) <br>
|
||
This must map vertices to their degree. </li>
|
||
</ul>
|
||
<p>For version 4: </p>
|
||
<ul>
|
||
<li><tt>Graph& g</tt> (IN) <br>
|
||
An undirected graph. The graph's type must be a model of <a
|
||
href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
|
||
<li><tt>OutputIterator permutation</tt> (OUT) <br>
|
||
The new vertex ordering. The vertices are written to the <a
|
||
href="http://www.boost.org/sgi/stl/OutputIterator.html">output iterator</a> in
|
||
their new order.
|
||
<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>PriorityMap priority_map</tt> (IN)<br>
|
||
Used internally to store the priority for renumbering of each vertex. </li>
|
||
<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="../example/sloan_ordering.cpp"><TT>example/sloan_ordering.cpp</TT></A>.
|
||
<H3>See Also</H3>
|
||
<p><a href="./sloan_start_end_vertices.htm">sloan_start_end_vertices</a>,
|
||
<A
|
||
href="./bandwidth.html">bandwidth</a>, <a href="./profile.htm">profile</a>, <a href="./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="718">
|
||
<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>
|