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> > > Graph; |
---|
39 | typedef graph_traits<Graph>::vertex_descriptor Vertex; |
---|
40 | typedef graph_traits<Graph>::vertices_size_type size_type; |
---|
41 | |
---|
42 | typedef std::pair<std::size_t, std::size_t> Pair; |
---|
43 | Pair edges[14] = { Pair(0,3), //a-d |
---|
44 | Pair(0,5), //a-f |
---|
45 | Pair(1,2), //b-c |
---|
46 | Pair(1,4), //b-e |
---|
47 | Pair(1,6), //b-g |
---|
48 | Pair(1,9), //b-j |
---|
49 | Pair(2,3), //c-d |
---|
50 | Pair(2,4), //c-e |
---|
51 | Pair(3,5), //d-f |
---|
52 | Pair(3,8), //d-i |
---|
53 | Pair(4,6), //e-g |
---|
54 | Pair(5,6), //f-g |
---|
55 | Pair(5,7), //f-h |
---|
56 | Pair(6,7) }; //g-h |
---|
57 | |
---|
58 | Graph G(10); |
---|
59 | for (int i = 0; i < 14; ++i) |
---|
60 | add_edge(edges[i].first, edges[i].second, G); |
---|
61 | |
---|
62 | graph_traits<Graph>::vertex_iterator ui, ui_end; |
---|
63 | |
---|
64 | property_map<Graph,vertex_degree_t>::type deg = get(vertex_degree, G); |
---|
65 | for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) |
---|
66 | deg[*ui] = degree(*ui, G); |
---|
67 | |
---|
68 | property_map<Graph, vertex_index_t>::type |
---|
69 | index_map = get(vertex_index, G); |
---|
70 | |
---|
71 | std::cout << "original bandwidth: " << bandwidth(G) << std::endl; |
---|
72 | |
---|
73 | std::vector<Vertex> inv_perm(num_vertices(G)); |
---|
74 | std::vector<size_type> perm(num_vertices(G)); |
---|
75 | { |
---|
76 | Vertex s = vertex(6, G); |
---|
77 | //king_ordering |
---|
78 | king_ordering(G, s, inv_perm.rbegin(), get(vertex_color, G), |
---|
79 | get(vertex_degree, G)); |
---|
80 | cout << "King ordering starting at: " << s << endl; |
---|
81 | cout << " "; |
---|
82 | for (std::vector<Vertex>::const_iterator i = inv_perm.begin(); |
---|
83 | i != inv_perm.end(); ++i) |
---|
84 | cout << index_map[*i] << " "; |
---|
85 | cout << endl; |
---|
86 | |
---|
87 | for (size_type c = 0; c != inv_perm.size(); ++c) |
---|
88 | perm[index_map[inv_perm[c]]] = c; |
---|
89 | std::cout << " bandwidth: " |
---|
90 | << bandwidth(G, make_iterator_property_map(&perm[0], index_map, perm[0])) |
---|
91 | << std::endl; |
---|
92 | } |
---|
93 | { |
---|
94 | Vertex s = vertex(0, G); |
---|
95 | //king_ordering |
---|
96 | king_ordering(G, s, inv_perm.rbegin(), get(vertex_color, G), |
---|
97 | get(vertex_degree, G)); |
---|
98 | cout << "King ordering starting at: " << s << endl; |
---|
99 | cout << " "; |
---|
100 | for (std::vector<Vertex>::const_iterator i=inv_perm.begin(); |
---|
101 | i != inv_perm.end(); ++i) |
---|
102 | cout << index_map[*i] << " "; |
---|
103 | cout << endl; |
---|
104 | |
---|
105 | for (size_type c = 0; c != inv_perm.size(); ++c) |
---|
106 | perm[index_map[inv_perm[c]]] = c; |
---|
107 | std::cout << " bandwidth: " |
---|
108 | << bandwidth(G, make_iterator_property_map(&perm[0], index_map, perm[0])) |
---|
109 | << std::endl; |
---|
110 | } |
---|
111 | |
---|
112 | { |
---|
113 | //king_ordering |
---|
114 | king_ordering(G, inv_perm.rbegin(), get(vertex_color, G), |
---|
115 | make_degree_map(G)); |
---|
116 | |
---|
117 | cout << "King ordering:" << endl; |
---|
118 | cout << " "; |
---|
119 | for (std::vector<Vertex>::const_iterator i=inv_perm.begin(); |
---|
120 | i != inv_perm.end(); ++i) |
---|
121 | cout << index_map[*i] << " "; |
---|
122 | cout << endl; |
---|
123 | |
---|
124 | for (size_type c = 0; c != inv_perm.size(); ++c) |
---|
125 | perm[index_map[inv_perm[c]]] = c; |
---|
126 | std::cout << " bandwidth: " |
---|
127 | << bandwidth(G, make_iterator_property_map(&perm[0], index_map, perm[0])) |
---|
128 | << std::endl; |
---|
129 | } |
---|
130 | return 0; |
---|
131 | } |
---|