1<HTML> 2<!-- 3 ~~ Copyright (c) Jeremy Siek 2000 4 ~~ 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8--> 9 10 11<Head> 12<Title>Boost Graph Library: King Ordering</Title> 13<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 14 ALINK="#ff0000"> 15<IMG SRC="../../../boost.png" 16 ALT="C++ Boost" width="277" height="86"> 17 18<BR Clear> 19 20<H1> 21<img src="figs/python.gif" alt="(Python)"/> 22<TT>king_ordering</TT> 23</H1> 24 25 26<P> 27<DIV ALIGN="LEFT"> 28<TABLE CELLPADDING=3 border> 29<TR><TH ALIGN="LEFT"><B>Graphs:</B></TH> 30<TD ALIGN="LEFT">undirected</TD> 31</TR> 32<TR><TH ALIGN="LEFT"><B>Properties:</B></TH> 33<TD ALIGN="LEFT">color, degree</TD> 34</TR> 35<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH> 36<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> 37</TR> 38</TABLE> 39</DIV> 40 41 42<pre> 43 (1) 44 template <class IncidenceGraph, class OutputIterator, 45 class ColorMap, class DegreeMap, class VertexIndexMap> 46 OutputIterator 47 king_ordering(const IncidenceGraph& g, 48 typename graph_traits<Graph>::vertex_descriptor s, 49 OutputIterator inverse_permutation, 50 ColorMap color, DegreeMap degree, VertexIndexMap index_map); 51 52 (2) 53 template <class IncidenceGraph, class OutputIterator> 54 OutputIterator 55 king_ordering(const IncidenceGraph& g, OutputIterator inverse_permutation); 56 57 template <class IncidenceGraph, class OutputItrator, class VertexIndexMap> 58 OutputIterator 59 king_ordering(const IncidenceGraph& g, OutputIterator inverse_permutation, 60 VertexIndexMap index_map); 61 62 template <class VertexListGraph, class OutputIterator, 63 class ColorMap, class DegreeMap, class VertexIndexMap> 64 OutputIterator 65 king_ordering(const VertexListGraph& G, OutputIterator inverse_permutation, 66 ColorMap color, DegreeMap degree, VertexIndexMap index_map); 67 68 (3) 69 template <class IncidenceGraph, class OutputIterator, 70 class ColorMap, class DegreeMap, class VertexIndexMap> 71 OutputIterator 72 king_ordering(const IncidenceGraph& g, 73 std::deque< typename 74 graph_traits<Graph>::vertex_descriptor > vertex_queue, 75 OutputIterator permutation, 76 ColorMap color, DegreeMap degree, VertexIndexMap index_map); 77</pre> 78 79<!-- King, I.P. An automatic reordering scheme for simultaneous equations derived from network analysis. Int. J. Numer. Methods Engrg. 2 (1970), 523-533 --> 80 81The goal of the King ordering 82algorithm [<a href="bibliography.html#king70">62</a>]is to reduce the <a 83href="./bandwidth.html">bandwidth</a> of a graph by reordering the 84indices assigned to each vertex. The King ordering algorithm 85works by a local minimization of the i-th bandwidths. The vertices are 86basically assigned a breadth-first search order, except that at each 87step, the adjacent vertices are placed in the queue in order of 88increasing pseudo-degree, where pseudo-degree is defined as the number of 89outgoing edges with white endpoints (vertices yet to be examined). 90 91<p> 92Version 1 of the algorithm lets the user choose the ``starting 93vertex'', version 2 finds a good starting vertex using the 94pseudo-peripheral pair heuristic (among each component), while version 3 95contains the starting nodes for each vertex in the deque. The choice of the ``starting 96vertex'' can have a significant effect on the quality of the ordering. 97</p> 98 99<p> 100The output of the algorithm are the vertices in the new ordering. 101Storing the output into a vector gives you the 102permutation from the new ordering to the old ordering. 103 104<pre> 105 inv_perm[new_index[u]] == u 106</pre> 107 108<p> 109Often times, it is the opposite permutation that you want, the 110permutation from the old index to the new index. This can easily be 111computed in the following way. 112</p> 113 114<pre> 115 for (size_type i = 0; i != inv_perm.size(); ++i) 116 perm[old_index[inv_perm[i]]] = i; 117</pre> 118 119 120 121<h3>Parameters</h3> 122 123For version 1: 124 125<ul> 126 127<li> <tt>IncidenceGraph& g</tt> (IN) <br> 128 An undirected graph. The graph's type must be a model of <a 129 href="./IncidenceGraph.html">IncidenceGraph</a>.<br> 130 <b>Python</b>: The parameter is named <tt>graph</tt>. 131 132<li> <tt>vertex_descriptor s</tt>  (IN) <br> 133 The starting vertex.<br> 134 <b>Python</b>: Unsupported parameter. 135 136<li> <tt>OutputIterator permutation</tt>  (OUT) <br> 137 The new vertex ordering. The vertices are written to the <a 138 href="http://www.boost.org/sgi/stl/OutputIterator.html">output 139 iterator</a> in their new order. <br> 140 <b>Python</b>: This parameter is unused in Python. The new vertex 141 ordering is returned as a Python <tt>list</tt>. 142 143 144<li> <tt>ColorMap color_map</tt>  (WORK) <br> 145 Used internally to keep track of the progress of the algorithm 146 (to avoid visiting the same vertex twice).<br> 147 <b>Python</b>: Unsupported parameter. 148 149<li> <tt>DegreeMap degree_map</tt>  (IN) <br> 150 This must map vertices to their degree.<br> 151 <b>Python</b>: Unsupported parameter. 152 153</ul> 154 155 156For version 2: 157 158<ul> 159 160<li> <tt>VertexListGraph& g</tt> (IN) <br> 161 An undirected graph. The graph's type must be a model of <a 162 href="./VertexListGraph.html">VertexListGraph</a>.<br> 163 <b>Python</b>: The name of this parameter is <tt>graph</tt>. 164 165<li> <tt><a href="http://www.boost.org/sgi/stl/OutputIterator.html"> 166 OutputIterator</a> permutation</tt>  (OUT) <br> 167 The new vertex ordering. The vertices are written to the 168 output iterator in their new order.<br> 169 <b>Python</b>: This parameter is unused in Python. The new vertex 170 ordering is returned as a Python <tt>list</tt>. 171 172<li> <tt>ColorMap color_map</tt>  (WORK) <br> 173 Used internally to keep track of the progress of the algorithm 174 (to avoid visiting the same vertex twice).<br> 175 <b>Python</b>: Unsupported parameter. 176 177<li> <tt>DegreeMap degree_map</tt>  (IN) <br> 178 This must map vertices to their degree.<br> 179 <b>Python</b>: Unsupported parameter. 180</ul> 181 182 183For version 3: 184 185<ul> 186 187<li> <tt>IncidenceGraph& g</tt> (IN) <br> 188 An undirected graph. The graph's type must be a model of <a 189 href="./IncidenceGraph.html">IncidenceGraph</a>.<br> 190 <b>Python</b>: The parameter is named <tt>graph</tt>. 191 192<li> <tt> std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue </tt>  (IN) <br> 193 The deque containing the starting vertices for each component.<br> 194 <b>Python</b>: This parameter is unused in Python. The new vertex 195 ordering is returned as a Python <tt>list</tt>. 196 197<li> <tt>OutputIterator permutation</tt>  (OUT) <br> 198 The new vertex ordering. The vertices are written to the <a 199 href="http://www.boost.org/sgi/stl/OutputIterator.html">output 200 iterator</a> in their new order.<br> 201 <b>Python</b>: This parameter is unused in Python. The new vertex 202 ordering is returned as a Python <tt>list</tt>. 203 204<li> <tt>ColorMap color_map</tt>  (WORK) <br> 205 Used internally to keep track of the progress of the algorithm 206 (to avoid visiting the same vertex twice).<br> 207 <b>Python</b>: Unsupported parameter. 208 209<li> <tt>DegreeMap degree_map</tt>  (IN) <br> 210 This must map vertices to their degree.<br> 211 <b>Python</b>: Unsupported parameter. 212</ul> 213 214 215 216<h3>Example</h3> 217 218See <a 219href="../example/king_ordering.cpp"><tt>example/king_ordering.cpp</tt></a>. 220 221<h3>See Also</h3> 222 223<a href="./bandwidth.html">bandwidth</tt></a>, 224and <tt>degree_property_map</tt> in <tt>boost/graph/properties.hpp</tt>. 225 226<br> 227<HR> 228<TABLE> 229<TR valign=top> 230<TD nowrap>Copyright © 2000-2001</TD><TD> 231<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>) 232</TD></TR></TABLE> 233 234</BODY> 235</HTML> 236
