]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // |
2 | //======================================================================= | |
3 | // Copyright 2002 Marc Wintermantel (wintermantel@imes.mavt.ethz.ch) | |
92f5a8d4 TL |
4 | // ETH Zurich, Center of Structure Technologies |
5 | // (https://web.archive.org/web/20050307090307/http://www.structures.ethz.ch/) | |
7c673cae FG |
6 | // |
7 | // Distributed under the Boost Software License, Version 1.0. | |
8 | // (See accompanying file LICENSE_1_0.txt or copy at | |
9 | // http://www.boost.org/LICENSE_1_0.txt) | |
10 | //======================================================================= | |
11 | // | |
12 | ||
7c673cae FG |
13 | #include <boost/config.hpp> |
14 | #include <vector> | |
15 | #include <iostream> | |
16 | #include <boost/graph/adjacency_list.hpp> | |
17 | #include <boost/graph/sloan_ordering.hpp> | |
18 | #include <boost/graph/properties.hpp> | |
19 | #include <boost/graph/bandwidth.hpp> | |
20 | #include <boost/graph/profile.hpp> | |
21 | #include <boost/graph/wavefront.hpp> | |
22 | ||
7c673cae FG |
23 | using std::cout; |
24 | using std::endl; | |
25 | ||
26 | /* | |
27 | Sample Output | |
28 | ##################################### | |
29 | ### First light of sloan-ordering ### | |
30 | ##################################### | |
31 | ||
32 | original bandwidth: 8 | |
33 | original profile: 42 | |
34 | original max_wavefront: 7 | |
35 | original aver_wavefront: 4.2 | |
36 | original rms_wavefront: 4.58258 | |
37 | ||
38 | Starting vertex: 0 | |
39 | Pseudoperipheral vertex: 9 | |
40 | Pseudoperipheral radius: 4 | |
41 | ||
42 | Sloan ordering starting at: 0 | |
43 | 0 8 3 7 5 2 4 6 1 9 | |
44 | bandwidth: 4 | |
45 | profile: 28 | |
46 | max_wavefront: 4 | |
47 | aver_wavefront: 2.8 | |
48 | rms_wavefront: 2.93258 | |
49 | ||
50 | Sloan ordering without a start-vertex: | |
51 | 8 0 3 7 5 2 4 6 1 9 | |
52 | bandwidth: 4 | |
53 | profile: 27 | |
54 | max_wavefront: 4 | |
55 | aver_wavefront: 2.7 | |
56 | rms_wavefront: 2.84605 | |
57 | ||
58 | ############################### | |
59 | ### sloan-ordering finished ### | |
60 | ############################### | |
61 | */ | |
62 | ||
f67539c2 | 63 | int main(int, char*[]) |
7c673cae | 64 | { |
7c673cae | 65 | cout << endl; |
f67539c2 TL |
66 | cout << "#####################################" << endl; |
67 | cout << "### First light of sloan-ordering ###" << endl; | |
68 | cout << "#####################################" << endl << endl; | |
69 | ||
70 | using namespace boost; | |
71 | using namespace std; | |
72 | ||
73 | // Defining the graph type | |
74 | typedef adjacency_list< setS, vecS, undirectedS, | |
75 | property< vertex_color_t, default_color_type, | |
76 | property< vertex_degree_t, int, | |
77 | property< vertex_priority_t, double > > > > | |
78 | Graph; | |
79 | ||
80 | typedef graph_traits< Graph >::vertex_descriptor Vertex; | |
81 | typedef graph_traits< Graph >::vertices_size_type size_type; | |
82 | ||
83 | typedef std::pair< std::size_t, std::size_t > Pair; | |
84 | ||
85 | Pair edges[14] = { Pair(0, 3), // a-d | |
86 | Pair(0, 5), // a-f | |
87 | Pair(1, 2), // b-c | |
88 | Pair(1, 4), // b-e | |
89 | Pair(1, 6), // b-g | |
90 | Pair(1, 9), // b-j | |
91 | Pair(2, 3), // c-d | |
92 | Pair(2, 4), // c-e | |
93 | Pair(3, 5), // d-f | |
94 | Pair(3, 8), // d-i | |
95 | Pair(4, 6), // e-g | |
96 | Pair(5, 6), // f-g | |
97 | Pair(5, 7), // f-h | |
98 | Pair(6, 7) }; // g-h | |
99 | ||
100 | // Creating a graph and adding the edges from above into it | |
101 | Graph G(10); | |
102 | for (int i = 0; i < 14; ++i) | |
103 | add_edge(edges[i].first, edges[i].second, G); | |
104 | ||
105 | // Creating two iterators over the vertices | |
106 | graph_traits< Graph >::vertex_iterator ui, ui_end; | |
107 | ||
108 | // Creating a property_map with the degrees of the degrees of each vertex | |
109 | property_map< Graph, vertex_degree_t >::type deg = get(vertex_degree, G); | |
110 | for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) | |
111 | deg[*ui] = degree(*ui, G); | |
112 | ||
113 | // Creating a property_map for the indices of a vertex | |
114 | property_map< Graph, vertex_index_t >::type index_map | |
115 | = get(vertex_index, G); | |
116 | ||
117 | std::cout << "original bandwidth: " << bandwidth(G) << std::endl; | |
118 | std::cout << "original profile: " << profile(G) << std::endl; | |
119 | std::cout << "original max_wavefront: " << max_wavefront(G) << std::endl; | |
120 | std::cout << "original aver_wavefront: " << aver_wavefront(G) << std::endl; | |
121 | std::cout << "original rms_wavefront: " << rms_wavefront(G) << std::endl; | |
122 | ||
123 | // Creating a vector of vertices | |
124 | std::vector< Vertex > sloan_order(num_vertices(G)); | |
125 | // Creating a vector of size_type | |
126 | std::vector< size_type > perm(num_vertices(G)); | |
7c673cae | 127 | |
f67539c2 | 128 | { |
7c673cae | 129 | |
f67539c2 TL |
130 | // Setting the start node |
131 | Vertex s = vertex(0, G); | |
132 | int ecc; // defining a variable for the pseudoperipheral radius | |
133 | ||
134 | // Calculating the pseudoeperipheral node and radius | |
135 | Vertex e = pseudo_peripheral_pair( | |
136 | G, s, ecc, get(vertex_color, G), get(vertex_degree, G)); | |
137 | ||
138 | cout << endl; | |
139 | cout << "Starting vertex: " << s << endl; | |
140 | cout << "Pseudoperipheral vertex: " << e << endl; | |
141 | cout << "Pseudoperipheral radius: " << ecc << endl << endl; | |
142 | ||
143 | // Sloan ordering | |
144 | sloan_ordering(G, s, e, sloan_order.begin(), get(vertex_color, G), | |
145 | get(vertex_degree, G), get(vertex_priority, G)); | |
146 | ||
147 | cout << "Sloan ordering starting at: " << s << endl; | |
148 | cout << " "; | |
149 | ||
150 | for (std::vector< Vertex >::const_iterator i = sloan_order.begin(); | |
151 | i != sloan_order.end(); ++i) | |
152 | cout << index_map[*i] << " "; | |
153 | cout << endl; | |
154 | ||
155 | for (size_type c = 0; c != sloan_order.size(); ++c) | |
156 | perm[index_map[sloan_order[c]]] = c; | |
157 | std::cout << " bandwidth: " | |
158 | << bandwidth(G, | |
159 | make_iterator_property_map( | |
160 | &perm[0], index_map, perm[0])) | |
161 | << std::endl; | |
162 | std::cout << " profile: " | |
163 | << profile(G, | |
164 | make_iterator_property_map( | |
165 | &perm[0], index_map, perm[0])) | |
166 | << std::endl; | |
167 | std::cout << " max_wavefront: " | |
168 | << max_wavefront(G, | |
169 | make_iterator_property_map( | |
170 | &perm[0], index_map, perm[0])) | |
171 | << std::endl; | |
172 | std::cout << " aver_wavefront: " | |
173 | << aver_wavefront(G, | |
174 | make_iterator_property_map( | |
175 | &perm[0], index_map, perm[0])) | |
176 | << std::endl; | |
177 | std::cout << " rms_wavefront: " | |
178 | << rms_wavefront(G, | |
179 | make_iterator_property_map( | |
180 | &perm[0], index_map, perm[0])) | |
181 | << std::endl; | |
182 | } | |
7c673cae FG |
183 | |
184 | ///////////////////////////////////////////////// | |
f67539c2 | 185 | // Version including finding a good starting point |
7c673cae | 186 | ///////////////////////////////////////////////// |
f67539c2 | 187 | |
7c673cae | 188 | { |
f67539c2 TL |
189 | // sloan_ordering |
190 | sloan_ordering(G, sloan_order.begin(), get(vertex_color, G), | |
191 | make_degree_map(G), get(vertex_priority, G)); | |
192 | ||
193 | cout << endl << "Sloan ordering without a start-vertex:" << endl; | |
194 | cout << " "; | |
195 | for (std::vector< Vertex >::const_iterator i = sloan_order.begin(); | |
196 | i != sloan_order.end(); ++i) | |
197 | cout << index_map[*i] << " "; | |
198 | cout << endl; | |
199 | ||
200 | for (size_type c = 0; c != sloan_order.size(); ++c) | |
201 | perm[index_map[sloan_order[c]]] = c; | |
202 | std::cout << " bandwidth: " | |
203 | << bandwidth(G, | |
204 | make_iterator_property_map( | |
205 | &perm[0], index_map, perm[0])) | |
206 | << std::endl; | |
207 | std::cout << " profile: " | |
208 | << profile(G, | |
209 | make_iterator_property_map( | |
210 | &perm[0], index_map, perm[0])) | |
211 | << std::endl; | |
212 | std::cout << " max_wavefront: " | |
213 | << max_wavefront(G, | |
214 | make_iterator_property_map( | |
215 | &perm[0], index_map, perm[0])) | |
216 | << std::endl; | |
217 | std::cout << " aver_wavefront: " | |
218 | << aver_wavefront(G, | |
219 | make_iterator_property_map( | |
220 | &perm[0], index_map, perm[0])) | |
221 | << std::endl; | |
222 | std::cout << " rms_wavefront: " | |
223 | << rms_wavefront(G, | |
224 | make_iterator_property_map( | |
225 | &perm[0], index_map, perm[0])) | |
226 | << std::endl; | |
7c673cae | 227 | } |
7c673cae | 228 | |
f67539c2 TL |
229 | cout << endl; |
230 | cout << "###############################" << endl; | |
231 | cout << "### sloan-ordering finished ###" << endl; | |
232 | cout << "###############################" << endl << endl; | |
233 | return 0; | |
7c673cae | 234 | } |