3 <!-- Copyright (c) Jeremy Siek 2000
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)
11 <Title>Boost Graph Library: Cuthill-Mckee Ordering
</Title>
13 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
15 <IMG SRC=
"../../../boost.png"
16 ALT=
"C++ Boost" width=
"277" height=
"86">
21 <img src=
"figs/python.gif" alt=
"(Python)"/>
22 <TT>cuthill_mckee_ordering
</TT>
28 <TABLE CELLPADDING=
3 border
>
29 <TR><TH ALIGN=
"LEFT"><B>Graphs:
</B></TH>
30 <TD ALIGN=
"LEFT">undirected
</TD>
32 <TR><TH ALIGN=
"LEFT"><B>Properties:
</B></TH>
33 <TD ALIGN=
"LEFT">color, degree
</TD>
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>
44 template
<class IncidenceGraph, class OutputIterator,
45 class ColorMap, class DegreeMap
>
47 cuthill_mckee_ordering(const IncidenceGraph
& g,
48 typename graph_traits
<IncidenceGraph
>::vertex_descriptor s,
49 OutputIterator inverse_permutation,
50 ColorMap color, DegreeMap degree)
53 template
<class VertexListGraph, class OutputIterator
>
55 cuthill_mckee_ordering(const VertexListGraph
& g, OutputIterator inverse_permutation);
57 template
<class VertexListGraph, class OutputIterator, class VertexIndexMap
>
59 cuthill_mckee_ordering(const VertexListGraph
& g, OutputIterator inverse_permutation,
60 VertexIndexMap index_map);
62 template
<class VertexListGraph, class OutputIterator,
63 class ColorMap, class DegreeMap
>
65 cuthill_mckee_ordering(const VertexListGraph
& g, OutputIterator inverse_permutation,
66 ColorMap color, DegreeMap degree)
69 template
<class IncidenceGraph, class OutputIterator,
70 class ColorMap, class DegreeMap
>
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)
79 The goal of the Cuthill-Mckee (and reverse Cuthill-Mckee) ordering
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
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.
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.
111 std::vector
<vertex_descriptor
> inv_perm(num_vertices(G));
112 cuthill_mckee_ordering(G, inv_perm.rbegin(), ...);
116 Either way, storing the output into a vector gives you the
117 permutation from the new ordering to the old ordering.
121 inv_perm[new_index[u]] == u
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.
131 for (size_type i =
0; i != inv_perm.size(); ++i)
132 perm[old_index[inv_perm[i]]] = i;
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>.
148 <li> <tt>vertex_descriptor s
</tt>  (IN)
<br>
149 The starting vertex.
<br>
150 <b>Python
</b>: Unsupported parameter.
152 <li> <tt>OutputIterator inverse_permutation
</tt>  (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>.
159 <li> <tt>ColorMap color_map
</tt>  (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.
164 <li> <tt>DegreeMap degree_map
</tt>  (IN)
<br>
165 This must map vertices to their degree.
<br>
166 <b>Python
</b>: Unsupported parameter.
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>.
179 <li> <tt><a href=
"http://www.sgi.com/tech/stl/OutputIterator.html">
180 OutputIterator
</a> inverse_permutation
</tt>  (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>.
186 <li> <tt>ColorMap color_map
</tt>  (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.
191 <li> <tt>DegreeMap degree_map
</tt>  (IN)
<br>
192 This must map vertices to their degree.
<br>
193 <b>Python
</b>: Unsupported parameter.
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>.
206 <li> <tt> std::deque
< typename graph_traits
<Graph
>::vertex_descriptor
> vertex_queue
</tt>  (IN)
<br>
207 The deque containing the starting vertices for each component.
<br>
208 <b>Python
</b>: Unsupported parameter.
210 <li> <tt>OutputIterator inverse_permutation
</tt>  (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>.
217 <li> <tt>ColorMap color_map
</tt>  (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.
222 <li> <tt>DegreeMap degree_map
</tt>  (IN)
<br>
223 This must map vertices to their degree.
<br>
224 <b>Python
</b>: Unsupported parameter.
232 href=
"../example/cuthill_mckee_ordering.cpp"><tt>example/cuthill_mckee_ordering.cpp
</tt></a>.
236 <a href=
"./bandwidth.html">bandwidth
</tt></a>,
237 and
<tt>degree_property_map
</tt> in
<tt>boost/graph/properties.hpp
</tt>.
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>)