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/king_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 | */ |
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(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 | // king_ordering |
79 | king_ordering(g: G, s, permutation: inv_perm.rbegin(), color: get(p: vertex_color, g&: G), |
80 | degree: get(p: vertex_degree, g&: G), index_map: get(p: vertex_index, g&: G)); |
81 | cout << "King 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 | // king_ordering |
99 | king_ordering(g: G, s, permutation: inv_perm.rbegin(), color: get(p: vertex_color, g&: G), |
100 | degree: get(p: vertex_degree, g&: G), index_map: get(p: vertex_index, g&: G)); |
101 | cout << "King 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 | // king_ordering |
119 | king_ordering(G, permutation: inv_perm.rbegin()); |
120 | |
121 | cout << "King 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 | |