boost_1_45_0/libs/graph/doc/king_ordering.html - nest-learning-thermostat/5.0/boost - Git at Google

 <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 &lt;class IncidenceGraph, class OutputIterator,
             class ColorMap, class DegreeMap, class VertexIndexMap&gt;
   OutputIterator
   king_ordering(const IncidenceGraph&amp; g,
                 typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
                 OutputIterator inverse_permutation,
                 ColorMap color, DegreeMap degree, VertexIndexMap index_map);

   (2)
   template &lt;class IncidenceGraph, class OutputIterator&gt;
   OutputIterator
   king_ordering(const IncidenceGraph&amp; g, OutputIterator inverse_permutation);

   template &lt;class IncidenceGraph, class OutputItrator, class VertexIndexMap&gt;
   OutputIterator
   king_ordering(const IncidenceGraph&amp; g, OutputIterator inverse_permutation,
                 VertexIndexMap index_map);

   template &lt;class VertexListGraph, class OutputIterator,
             class ColorMap, class DegreeMap, class VertexIndexMap&gt;
   OutputIterator
   king_ordering(const VertexListGraph&amp; G, OutputIterator inverse_permutation,
                 ColorMap color, DegreeMap degree, VertexIndexMap index_map);

   (3)
   template &lt;class IncidenceGraph, class OutputIterator,
             class ColorMap, class DegreeMap, class VertexIndexMap&gt;
   OutputIterator
   king_ordering(const IncidenceGraph&amp; g,
     		std::deque&lt; typename
 		graph_traits&lt;Graph&gt;::vertex_descriptor &gt; 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&amp; g</tt> &nbsp;(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> &nbsp(IN) <br>
   The starting vertex.<br>
   <b>Python</b>: Unsupported parameter.

 <li> <tt>OutputIterator permutation</tt> &nbsp(OUT) <br>
   The new vertex ordering. The vertices are written to the <a
   href="http://www.sgi.com/tech/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> &nbsp(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> &nbsp(IN) <br>
   This must map vertices to their degree.<br>
   <b>Python</b>: Unsupported parameter.

 </ul>


 For version 2:

 <ul>

 <li> <tt>VertexListGraph&amp; g</tt> &nbsp;(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.sgi.com/tech/stl/OutputIterator.html">
   OutputIterator</a> permutation</tt> &nbsp(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> &nbsp(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> &nbsp(IN) <br>
   This must map vertices to their degree.<br>
   <b>Python</b>: Unsupported parameter.
 </ul>


 For version 3:

 <ul>

 <li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(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&lt; typename graph_traits&lt;Graph&gt;::vertex_descriptor &gt; vertex_queue </tt> &nbsp(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> &nbsp(OUT) <br>
   The new vertex ordering. The vertices are written to the <a
   href="http://www.sgi.com/tech/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> &nbsp(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> &nbsp(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 &copy; 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>
	<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> &nbsp(IN) <br>
	The starting vertex.<br>
	<b>Python</b>: Unsupported parameter.

	<li> <tt>OutputIterator permutation</tt> &nbsp(OUT) <br>
	The new vertex ordering. The vertices are written to the <a
	href="http://www.sgi.com/tech/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> &nbsp(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> &nbsp(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.sgi.com/tech/stl/OutputIterator.html">
	OutputIterator</a> permutation</tt> &nbsp(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> &nbsp(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> &nbsp(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> &nbsp(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> &nbsp(OUT) <br>
	The new vertex ordering. The vertices are written to the <a
	href="http://www.sgi.com/tech/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> &nbsp(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> &nbsp(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>