1//=======================================================================
2// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4// Doug Gregor, D. Kevin McGrath
5//
6// Distributed under the Boost Software License, Version 1.0.
7// (See accompanying file LICENSE_1_0.txt or copy at
8// http://www.boost.org/LICENSE_1_0.txt)
9//=======================================================================
10
11#include <boost/config.hpp>
12#include <vector>
13#include <iostream>
14#include <boost/graph/adjacency_list.hpp>
15#include <boost/graph/cuthill_mckee_ordering.hpp>
16#include <boost/graph/properties.hpp>
17#include <boost/graph/bandwidth.hpp>
18
19/*
20 Sample Output
21 original bandwidth: 8
22 Reverse Cuthill-McKee ordering starting at: 6
23 8 3 0 9 2 5 1 4 7 6
24 bandwidth: 4
25 Reverse Cuthill-McKee ordering starting at: 0
26 9 1 4 6 7 2 8 5 3 0
27 bandwidth: 4
28 Reverse Cuthill-McKee ordering:
29 0 8 5 7 3 6 4 2 1 9
30 bandwidth: 4
31 */
32int main(int, char*[])
33{
34 using namespace boost;
35 using namespace std;
36 typedef adjacency_list< vecS, vecS, undirectedS,
37 property< vertex_color_t, default_color_type,
38 property< vertex_degree_t, int > > >
39 Graph;
40 typedef graph_traits< Graph >::vertex_descriptor Vertex;
41 typedef graph_traits< Graph >::vertices_size_type size_type;
42
43 typedef std::pair< std::size_t, std::size_t > Pair;
44 Pair edges[14] = { Pair(0, 3), // a-d
45 Pair(0, 5), // a-f
46 Pair(1, 2), // b-c
47 Pair(1, 4), // b-e
48 Pair(1, 6), // b-g
49 Pair(1, 9), // b-j
50 Pair(2, 3), // c-d
51 Pair(2, 4), // c-e
52 Pair(3, 5), // d-f
53 Pair(3, 8), // d-i
54 Pair(4, 6), // e-g
55 Pair(5, 6), // f-g
56 Pair(5, 7), // f-h
57 Pair(6, 7) }; // g-h
58
59 Graph G(10);
60 for (int i = 0; i < 14; ++i)
61 add_edge(u: edges[i].first, v: edges[i].second, g_&: G);
62
63 graph_traits< Graph >::vertex_iterator ui, ui_end;
64
65 property_map< Graph, vertex_degree_t >::type deg = get(p: vertex_degree, g&: G);
66 for (boost::tie(t0&: ui, t1&: ui_end) = vertices(g_: G); ui != ui_end; ++ui)
67 deg[*ui] = degree(u: *ui, g_: G);
68
69 property_map< Graph, vertex_index_t >::type index_map
70 = get(p: vertex_index, g&: G);
71
72 std::cout << "original bandwidth: " << bandwidth(g: G) << std::endl;
73
74 std::vector< Vertex > inv_perm(num_vertices(g_: G));
75 std::vector< size_type > perm(num_vertices(g_: G));
76 {
77 Vertex s = vertex(n: 6, G);
78 // reverse cuthill_mckee_ordering
79 cuthill_mckee_ordering(g: G, s, permutation: inv_perm.rbegin(), color: get(p: vertex_color, g&: G),
80 degree: get(p: vertex_degree, g&: G));
81 cout << "Reverse Cuthill-McKee ordering starting at: " << s << endl;
82 cout << " ";
83 for (std::vector< Vertex >::const_iterator i = inv_perm.begin();
84 i != inv_perm.end(); ++i)
85 cout << index_map[*i] << " ";
86 cout << endl;
87
88 for (size_type c = 0; c != inv_perm.size(); ++c)
89 perm[index_map[inv_perm[c]]] = c;
90 std::cout << " bandwidth: "
91 << bandwidth(g: G,
92 index: make_iterator_property_map(
93 iter: &perm[0], id: index_map, perm[0]))
94 << std::endl;
95 }
96 {
97 Vertex s = vertex(n: 0, G);
98 // reverse cuthill_mckee_ordering
99 cuthill_mckee_ordering(g: G, s, permutation: inv_perm.rbegin(), color: get(p: vertex_color, g&: G),
100 degree: get(p: vertex_degree, g&: G));
101 cout << "Reverse Cuthill-McKee ordering starting at: " << s << endl;
102 cout << " ";
103 for (std::vector< Vertex >::const_iterator i = inv_perm.begin();
104 i != inv_perm.end(); ++i)
105 cout << index_map[*i] << " ";
106 cout << endl;
107
108 for (size_type c = 0; c != inv_perm.size(); ++c)
109 perm[index_map[inv_perm[c]]] = c;
110 std::cout << " bandwidth: "
111 << bandwidth(g: G,
112 index: make_iterator_property_map(
113 iter: &perm[0], id: index_map, perm[0]))
114 << std::endl;
115 }
116
117 {
118 // reverse cuthill_mckee_ordering
119 cuthill_mckee_ordering(G, permutation: inv_perm.rbegin());
120
121 cout << "Reverse Cuthill-McKee ordering:" << endl;
122 cout << " ";
123 for (std::vector< Vertex >::const_iterator i = inv_perm.begin();
124 i != inv_perm.end(); ++i)
125 cout << index_map[*i] << " ";
126 cout << endl;
127
128 for (size_type c = 0; c != inv_perm.size(); ++c)
129 perm[index_map[inv_perm[c]]] = c;
130 std::cout << " bandwidth: "
131 << bandwidth(g: G,
132 index: make_iterator_property_map(
133 iter: &perm[0], id: index_map, perm[0]))
134 << std::endl;
135 }
136 return 0;
137}
138

source code of boost/libs/graph/test/cuthill_mckee_ordering.cpp