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 */
main(int,char * [])32 int 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(edges[i].first, edges[i].second, G);
62
63 graph_traits< Graph >::vertex_iterator ui, ui_end;
64
65 property_map< Graph, vertex_degree_t >::type deg = get(vertex_degree, G);
66 for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
67 deg[*ui] = degree(*ui, G);
68
69 property_map< Graph, vertex_index_t >::type index_map
70 = get(vertex_index, G);
71
72 std::cout << "original bandwidth: " << bandwidth(G) << std::endl;
73
74 std::vector< Vertex > inv_perm(num_vertices(G));
75 std::vector< size_type > perm(num_vertices(G));
76 {
77 Vertex s = vertex(6, G);
78 // reverse cuthill_mckee_ordering
79 cuthill_mckee_ordering(G, s, inv_perm.rbegin(), get(vertex_color, G),
80 get(vertex_degree, 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,
92 make_iterator_property_map(
93 &perm[0], index_map, perm[0]))
94 << std::endl;
95 }
96 {
97 Vertex s = vertex(0, G);
98 // reverse cuthill_mckee_ordering
99 cuthill_mckee_ordering(G, s, inv_perm.rbegin(), get(vertex_color, G),
100 get(vertex_degree, 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,
112 make_iterator_property_map(
113 &perm[0], index_map, perm[0]))
114 << std::endl;
115 }
116
117 {
118 // reverse cuthill_mckee_ordering
119 cuthill_mckee_ordering(G, 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,
132 make_iterator_property_map(
133 &perm[0], index_map, perm[0]))
134 << std::endl;
135 }
136 return 0;
137 }
138