[ceph.git] / ceph / src / boost / libs / graph / doc / cuthill_mckee_ordering.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: Cuthill-Mckee Ordering</Title>
</Head>
<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>cuthill_mckee_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 log(m)|V|)</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&gt;
  OutputIterator
  cuthill_mckee_ordering(const IncidenceGraph&amp; g,
                         typename graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor s,
                         OutputIterator inverse_permutation, 
                         ColorMap color, DegreeMap degree)

  (2)
  template &lt;class VertexListGraph, class OutputIterator&gt;
  OutputIterator
  cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation); 

  template &lt;class VertexListGraph, class OutputIterator, class VertexIndexMap&gt;
  OutputIterator
  cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation, 
                         VertexIndexMap index_map); 
 
  template &lt;class VertexListGraph, class OutputIterator, 
            class ColorMap, class DegreeMap&gt;
  OutputIterator
  cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation, 
                         ColorMap color, DegreeMap degree)
                         
  (3)
  template &lt;class IncidenceGraph, class OutputIterator,
            class ColorMap, class DegreeMap&gt;
  OutputIterator
  cuthill_mckee_ordering(const IncidenceGraph&amp; g,
    			 std::deque&lt; typename
			 graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor &gt; vertex_queue,
                         OutputIterator inverse_permutation, 
                         ColorMap color, DegreeMap degree)
</pre>

The goal of the Cuthill-Mckee (and reverse Cuthill-Mckee) ordering
algorithm[<A
HREF="bibliography.html#george81:__sparse_pos_def">14</A>, <A
HREF="bibliography.html#cuthill69:reducing_bandwith">43</A>, <a
href="bibliography.html#liu75:anal_cm_rcm">44</a>, <a
href="bibliography.html#george71:fem">45</a> ] is to reduce the <a
href="./bandwidth.html">bandwidth</a> of a graph by reordering the
indices assigned to each vertex.  The Cuthill-Mckee 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 degree.

<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.  For versions 2 and 3, <tt>find_starting_vertex</tt> will be called 
for each component in the graph, increasing run time significantly.
</p>

<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 Cuthill-Mckee ordering or the reverse Cuthill-McKee ordering.  For
example, if you store the output into a vector using the vector's
reverse iterator, then you get the reverse Cuthill-McKee ordering.
</p>

<pre>
  std::vector&lt;vertex_descriptor&gt; inv_perm(num_vertices(G));
  cuthill_mckee_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.
</p>

<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 inverse_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> and <a href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
  <b>Python</b>: The parameter is named <tt>graph</tt>.

<li> <tt><a href="http://www.sgi.com/tech/stl/OutputIterator.html">
  OutputIterator</a> inverse_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>: Unsupported parameter.

<li> <tt>OutputIterator inverse_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/cuthill_mckee_ordering.cpp"><tt>example/cuthill_mckee_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>
Commit	Line	Data
7c673cae FG	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	<Head>
	11	<Title>Boost Graph Library: Cuthill-Mckee Ordering</Title>
	12	</Head>
	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>cuthill_mckee_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 log(m)\|V\|)</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>
	46	OutputIterator
	47	cuthill_mckee_ordering(const IncidenceGraph& g,
	48	typename graph_traits<IncidenceGraph>::vertex_descriptor s,
	49	OutputIterator inverse_permutation,
	50	ColorMap color, DegreeMap degree)
	51
	52	(2)
	53	template <class VertexListGraph, class OutputIterator>
	54	OutputIterator
	55	cuthill_mckee_ordering(const VertexListGraph& g, OutputIterator inverse_permutation);
	56
	57	template <class VertexListGraph, class OutputIterator, class VertexIndexMap>
	58	OutputIterator
	59	cuthill_mckee_ordering(const VertexListGraph& g, OutputIterator inverse_permutation,
	60	VertexIndexMap index_map);
	61
	62	template <class VertexListGraph, class OutputIterator,
	63	class ColorMap, class DegreeMap>
	64	OutputIterator
65	cuthill_mckee_ordering(const VertexListGraph& g, OutputIterator inverse_permutation,
66	ColorMap color, DegreeMap degree)
67
68	(3)
69	template <class IncidenceGraph, class OutputIterator,
70	class ColorMap, class DegreeMap>
71	OutputIterator
72	cuthill_mckee_ordering(const IncidenceGraph& g,
73	std::deque< typename
74	graph_traits<IncidenceGraph>::vertex_descriptor > vertex_queue,
75	OutputIterator inverse_permutation,
76	ColorMap color, DegreeMap degree)
77	</pre>
78
79	The goal of the Cuthill-Mckee (and reverse Cuthill-Mckee) ordering
80	algorithm[<A
81	HREF="bibliography.html#george81:__sparse_pos_def">14</A>, <A
82	HREF="bibliography.html#cuthill69:reducing_bandwith">43</A>, <a
83	href="bibliography.html#liu75:anal_cm_rcm">44</a>, <a
84	href="bibliography.html#george71:fem">45</a> ] is to reduce the <a
85	href="./bandwidth.html">bandwidth</a> of a graph by reordering the
86	indices assigned to each vertex. The Cuthill-Mckee ordering algorithm
87	works by a local minimization of the i-th bandwidths. The vertices are
88	basically assigned a breadth-first search order, except that at each
89	step, the adjacent vertices are placed in the queue in order of
90	increasing degree.
91
92	<p>
93	Version 1 of the algorithm lets the user choose the ``starting
94	vertex'', version 2 finds a good starting vertex using the
95	pseudo-peripheral pair heuristic (among each component), while version 3
96	contains the starting nodes for each vertex in the deque. The choice of the
97	``starting vertex'' can have a significant effect on the quality of the
98	ordering. For versions 2 and 3, <tt>find_starting_vertex</tt> will be called
99	for each component in the graph, increasing run time significantly.
100	</p>
101
102	<p>
103	The output of the algorithm are the vertices in the new ordering.
104	Depending on what kind of output iterator you use, you can get either
105	the Cuthill-Mckee ordering or the reverse Cuthill-McKee ordering. For
106	example, if you store the output into a vector using the vector's
107	reverse iterator, then you get the reverse Cuthill-McKee ordering.
108	</p>
109
110	<pre>
111	std::vector<vertex_descriptor> inv_perm(num_vertices(G));
112	cuthill_mckee_ordering(G, inv_perm.rbegin(), ...);
113	</pre>
114
115	<p>
116	Either way, storing the output into a vector gives you the
117	permutation from the new ordering to the old ordering.
118	</p>
119
120	<pre>
121	inv_perm[new_index[u]] == u
122	</pre>
123
124	<p>
125	Often times, it is the opposite permutation that you want, the
126	permutation from the old index to the new index. This can easily be
127	computed in the following way.
128	</p>
129
130	<pre>
131	for (size_type i = 0; i != inv_perm.size(); ++i)
132	perm[old_index[inv_perm[i]]] = i;
133	</pre>
134
135
136
137	<h3>Parameters</h3>
138
139	For version 1:
140
141	<ul>
142
143	<li> <tt>IncidenceGraph& g</tt>  (IN) <br>
144	An undirected graph. The graph's type must be a model of <a
145	href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
146	<b>Python</b>: The parameter is named <tt>graph</tt>.
147
148	<li> <tt>vertex_descriptor s</tt> &nbsp(IN) <br>
149	The starting vertex.<br>
150	<b>Python</b>: Unsupported parameter.
151
152	<li> <tt>OutputIterator inverse_permutation</tt> &nbsp(OUT) <br>
153	The new vertex ordering. The vertices are written to the <a
154	href="http://www.sgi.com/tech/stl/OutputIterator.html">output
155	iterator</a> in their new order.<br>
156	<b>Python</b>: This parameter is unused in Python. The new vertex
157	ordering is returned as a Python <tt>list</tt>.
158
159	<li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
160	Used internally to keep track of the progress of the algorithm
161	(to avoid visiting the same vertex twice).<br>
162	<b>Python</b>: Unsupported parameter.
163
164	<li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
165	This must map vertices to their degree.<br>
166	<b>Python</b>: Unsupported parameter.
167	</ul>
168
169
170	For version 2:
171
172	<ul>
173
174	<li> <tt>VertexListGraph& g</tt>  (IN) <br>
175	An undirected graph. The graph's type must be a model of <a
176	href="./VertexListGraph.html">VertexListGraph</a> and <a href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
177	<b>Python</b>: The parameter is named <tt>graph</tt>.
178
179	<li> <tt><a href="http://www.sgi.com/tech/stl/OutputIterator.html">
180	OutputIterator</a> inverse_permutation</tt> &nbsp(OUT) <br>
181	The new vertex ordering. The vertices are written to the
182	output iterator in their new order.<br>
183	<b>Python</b>: This parameter is unused in Python. The new vertex
184	ordering is returned as a Python <tt>list</tt>.
185
186	<li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
187	Used internally to keep track of the progress of the algorithm
188	(to avoid visiting the same vertex twice).<br>
189	<b>Python</b>: Unsupported parameter.
190
191	<li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
192	This must map vertices to their degree.<br>
193	<b>Python</b>: Unsupported parameter.
194	</ul>
195
196
197	For version 3:
198
199	<ul>
200
201	<li> <tt>IncidenceGraph& g</tt>  (IN) <br>
202	An undirected graph. The graph's type must be a model of <a
203	href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
204	<b>Python</b>: The parameter is named <tt>graph</tt>.
205
206	<li> <tt> std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue </tt> &nbsp(IN) <br>
207	The deque containing the starting vertices for each component.<br>
208	<b>Python</b>: Unsupported parameter.
209
210	<li> <tt>OutputIterator inverse_permutation</tt> &nbsp(OUT) <br>
211	The new vertex ordering. The vertices are written to the <a
212	href="http://www.sgi.com/tech/stl/OutputIterator.html">output
213	iterator</a> in their new order.<br>
214	<b>Python</b>: This parameter is unused in Python. The new vertex
215	ordering is returned as a Python <tt>list</tt>.
216
217	<li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
218	Used internally to keep track of the progress of the algorithm
219	(to avoid visiting the same vertex twice).<br>
220	<b>Python</b>: Unsupported parameter.
221
222	<li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
223	This must map vertices to their degree.<br>
224	<b>Python</b>: Unsupported parameter.
225	</ul>
226
227
228
229	<h3>Example</h3>
230
231	See <a
232	href="../example/cuthill_mckee_ordering.cpp"><tt>example/cuthill_mckee_ordering.cpp</tt></a>.
233
234	<h3>See Also</h3>
235
236	<a href="./bandwidth.html">bandwidth</tt></a>,
237	and <tt>degree_property_map</tt> in <tt>boost/graph/properties.hpp</tt>.
238
239	<br>
240	<HR>
241	<TABLE>
242	<TR valign=top>
243	<TD nowrap>Copyright © 2000-2001</TD><TD>
244	<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>)
245	</TD></TR></TABLE>
246
247	</BODY>
248	</HTML>