123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235 |
- <HTML>
- <!--
- ~~ 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)
- -->
-
-
- <Head>
- <Title>Boost Graph Library: King Ordering</Title>
- <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <BR Clear>
- <H1>
- <img src="figs/python.gif" alt="(Python)"/>
- <TT>king_ordering</TT>
- </H1>
- <P>
- <DIV ALIGN="LEFT">
- <TABLE CELLPADDING=3 border>
- <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">time: <i>O(m<sup>2</sup>log(m)|E|)</i> where <i>m = max { degree(v) | v in V }</i> </TD>
- </TR>
- </TABLE>
- </DIV>
- <pre>
- (1)
- template <class IncidenceGraph, class OutputIterator,
- class ColorMap, class DegreeMap, class VertexIndexMap>
- OutputIterator
- king_ordering(const IncidenceGraph& g,
- typename graph_traits<Graph>::vertex_descriptor s,
- OutputIterator inverse_permutation,
- ColorMap color, DegreeMap degree, VertexIndexMap index_map);
- (2)
- template <class IncidenceGraph, class OutputIterator>
- OutputIterator
- king_ordering(const IncidenceGraph& g, OutputIterator inverse_permutation);
- template <class IncidenceGraph, class OutputItrator, class VertexIndexMap>
- OutputIterator
- king_ordering(const IncidenceGraph& g, OutputIterator inverse_permutation,
- VertexIndexMap index_map);
- template <class VertexListGraph, class OutputIterator,
- class ColorMap, class DegreeMap, class VertexIndexMap>
- OutputIterator
- king_ordering(const VertexListGraph& G, OutputIterator inverse_permutation,
- ColorMap color, DegreeMap degree, VertexIndexMap index_map);
-
- (3)
- template <class IncidenceGraph, class OutputIterator,
- class ColorMap, class DegreeMap, class VertexIndexMap>
- OutputIterator
- king_ordering(const IncidenceGraph& g,
- std::deque< typename
- graph_traits<Graph>::vertex_descriptor > vertex_queue,
- OutputIterator permutation,
- ColorMap color, DegreeMap degree, VertexIndexMap index_map);
- </pre>
- <!-- King, I.P. An automatic reordering scheme for simultaneous equations derived from network analysis. Int. J. Numer. Methods Engrg. 2 (1970), 523-533 -->
- The goal of the King ordering
- algorithm [<a href="bibliography.html#king70">62</a>]is to reduce the <a
- href="./bandwidth.html">bandwidth</a> of a graph by reordering the
- indices assigned to each vertex. The King ordering algorithm
- works by a local minimization of the i-th bandwidths. The vertices are
- basically assigned a breadth-first search order, except that at each
- step, the adjacent vertices are placed in the queue in order of
- increasing pseudo-degree, where pseudo-degree is defined as the number of
- outgoing edges with white endpoints (vertices yet to be examined).
- <p>
- Version 1 of the algorithm lets the user choose the ``starting
- vertex'', version 2 finds a good starting vertex using the
- pseudo-peripheral pair heuristic (among each component), while version 3
- contains the starting nodes for each vertex in the deque. The choice of the ``starting
- vertex'' can have a significant effect on the quality of the ordering.
- </p>
- <p>
- The output of the algorithm are the vertices in the new ordering.
- 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>
- Often times, 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.
- </p>
- <pre>
- for (size_type i = 0; i != inv_perm.size(); ++i)
- perm[old_index[inv_perm[i]]] = i;
- </pre>
- <h3>Parameters</h3>
- For version 1:
- <ul>
- <li> <tt>IncidenceGraph& g</tt> (IN) <br>
- An undirected graph. The graph's type must be a model of <a
- href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
- <b>Python</b>: The parameter is named <tt>graph</tt>.
- <li> <tt>vertex_descriptor s</tt>  (IN) <br>
- The starting vertex.<br>
- <b>Python</b>: Unsupported parameter.
- <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. <br>
- <b>Python</b>: This parameter is unused in Python. The new vertex
- ordering is returned as a Python <tt>list</tt>.
-
- <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).<br>
- <b>Python</b>: Unsupported parameter.
- <li> <tt>DegreeMap degree_map</tt>  (IN) <br>
- This must map vertices to their degree.<br>
- <b>Python</b>: Unsupported parameter.
- </ul>
- For version 2:
- <ul>
- <li> <tt>VertexListGraph& g</tt> (IN) <br>
- An undirected graph. The graph's type must be a model of <a
- href="./VertexListGraph.html">VertexListGraph</a>.<br>
- <b>Python</b>: The name of this parameter is <tt>graph</tt>.
- <li> <tt><a href="http://www.boost.org/sgi/stl/OutputIterator.html">
- OutputIterator</a> permutation</tt>  (OUT) <br>
- The new vertex ordering. The vertices are written to the
- output iterator in their new order.<br>
- <b>Python</b>: This parameter is unused in Python. The new vertex
- ordering is returned as a Python <tt>list</tt>.
- <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).<br>
- <b>Python</b>: Unsupported parameter.
- <li> <tt>DegreeMap degree_map</tt>  (IN) <br>
- This must map vertices to their degree.<br>
- <b>Python</b>: Unsupported parameter.
- </ul>
- For version 3:
- <ul>
- <li> <tt>IncidenceGraph& g</tt> (IN) <br>
- An undirected graph. The graph's type must be a model of <a
- href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
- <b>Python</b>: The parameter is named <tt>graph</tt>.
- <li> <tt> std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue </tt>  (IN) <br>
- The deque containing the starting vertices for each component.<br>
- <b>Python</b>: This parameter is unused in Python. The new vertex
- ordering is returned as a Python <tt>list</tt>.
- <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.<br>
- <b>Python</b>: This parameter is unused in Python. The new vertex
- ordering is returned as a Python <tt>list</tt>.
- <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).<br>
- <b>Python</b>: Unsupported parameter.
- <li> <tt>DegreeMap degree_map</tt>  (IN) <br>
- This must map vertices to their degree.<br>
- <b>Python</b>: Unsupported parameter.
- </ul>
- <h3>Example</h3>
- See <a
- href="../example/king_ordering.cpp"><tt>example/king_ordering.cpp</tt></a>.
- <h3>See Also</h3>
- <a href="./bandwidth.html">bandwidth</tt></a>,
- and <tt>degree_property_map</tt> in <tt>boost/graph/properties.hpp</tt>.
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2000-2001</TD><TD>
- <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>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|