Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/king_ordering.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 7.7 KB
Line 
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 &lt;class IncidenceGraph, class OutputIterator,
45            class ColorMap, class DegreeMap, class VertexIndexMap&gt;
46  OutputIterator
47  king_ordering(const IncidenceGraph&amp; g,
48                typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
49                OutputIterator inverse_permutation,
50                ColorMap color, DegreeMap degree, VertexIndexMap index_map);
51
52  (2)
53  template &lt;class IncidenceGraph, class OutputIterator&gt;
54  OutputIterator
55  king_ordering(const IncidenceGraph&amp; g, OutputIterator inverse_permutation);
56
57  template &lt;class IncidenceGraph, class OutputItrator, class VertexIndexMap&gt;
58  OutputIterator
59  king_ordering(const IncidenceGraph&amp; g, OutputIterator inverse_permutation,
60                VertexIndexMap index_map);
61
62  template &lt;class VertexListGraph, class OutputIterator,
63            class ColorMap, class DegreeMap, class VertexIndexMap&gt;
64  OutputIterator
65  king_ordering(const VertexListGraph&amp; G, OutputIterator inverse_permutation,
66                ColorMap color, DegreeMap degree, VertexIndexMap index_map);
67                         
68  (3)
69  template &lt;class IncidenceGraph, class OutputIterator,
70            class ColorMap, class DegreeMap, class VertexIndexMap&gt;
71  OutputIterator
72  king_ordering(const IncidenceGraph&amp; g,
73                std::deque&lt; typename
74                graph_traits&lt;Graph&gt;::vertex_descriptor &gt; 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&amp; g</tt> &nbsp;(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> &nbsp(IN) <br>
133  The starting vertex.<br>
134  <b>Python</b>: Unsupported parameter.
135
136<li> <tt>OutputIterator permutation</tt> &nbsp(OUT) <br> 
137  The new vertex ordering. The vertices are written to the <a
138  href="http://www.sgi.com/tech/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> &nbsp(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> &nbsp(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&amp; g</tt> &nbsp;(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.sgi.com/tech/stl/OutputIterator.html">
166  OutputIterator</a> permutation</tt> &nbsp(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> &nbsp(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> &nbsp(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&amp; g</tt> &nbsp;(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&lt; typename graph_traits&lt;Graph&gt;::vertex_descriptor &gt; vertex_queue </tt> &nbsp(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> &nbsp(OUT) <br> 
198  The new vertex ordering. The vertices are written to the <a
199  href="http://www.sgi.com/tech/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> &nbsp(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> &nbsp(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 &copy; 2000-2001</TD><TD>
231<A HREF="../../../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> 
Note: See TracBrowser for help on using the repository browser.