123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224 |
- <!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 © 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>
|