]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | |
f67539c2 | 23 | 8 3 0 9 2 5 1 4 7 6 |
7c673cae FG |
24 | bandwidth: 4 |
25 | Reverse Cuthill-McKee ordering starting at: 0 | |
f67539c2 | 26 | 9 1 4 6 7 2 8 5 3 0 |
7c673cae FG |
27 | bandwidth: 4 |
28 | Reverse Cuthill-McKee ordering: | |
f67539c2 | 29 | 0 8 5 7 3 6 4 2 1 9 |
7c673cae FG |
30 | bandwidth: 4 |
31 | */ | |
f67539c2 | 32 | int main(int, char*[]) |
7c673cae | 33 | { |
f67539c2 TL |
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; | |
7c673cae | 42 | |
f67539c2 TL |
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 | |
7c673cae | 58 | |
f67539c2 TL |
59 | Graph G(10); |
60 | for (int i = 0; i < 14; ++i) | |
61 | add_edge(edges[i].first, edges[i].second, G); | |
7c673cae | 62 | |
f67539c2 | 63 | graph_traits< Graph >::vertex_iterator ui, ui_end; |
7c673cae | 64 | |
f67539c2 TL |
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); | |
7c673cae | 68 | |
f67539c2 TL |
69 | property_map< Graph, vertex_index_t >::type index_map |
70 | = get(vertex_index, G); | |
7c673cae | 71 | |
f67539c2 | 72 | std::cout << "original bandwidth: " << bandwidth(G) << std::endl; |
7c673cae | 73 | |
f67539c2 TL |
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 | // king_ordering | |
79 | king_ordering(G, s, inv_perm.rbegin(), get(vertex_color, G), | |
80 | get(vertex_degree, G), get(vertex_index, 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; | |
7c673cae | 87 | |
f67539c2 TL |
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 | // king_ordering | |
99 | king_ordering(G, s, inv_perm.rbegin(), get(vertex_color, G), | |
100 | get(vertex_degree, G), get(vertex_index, 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; | |
7c673cae | 107 | |
f67539c2 TL |
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 | } | |
7c673cae | 116 | |
f67539c2 TL |
117 | { |
118 | // king_ordering | |
119 | king_ordering(G, 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, | |
132 | make_iterator_property_map( | |
133 | &perm[0], index_map, perm[0])) | |
134 | << std::endl; | |
135 | } | |
136 | return 0; | |
7c673cae | 137 | } |