1 //
2 //=======================================================================
3 // Copyright 2002 Marc Wintermantel (wintermantel@imes.mavt.ethz.ch)
4 // ETH Zurich, Center of Structure Technologies
5 // (https://web.archive.org/web/20050307090307/http://www.structures.ethz.ch/)
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
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
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
main(int,char * [])63 int main(int, char*[])
64 {
65 cout << endl;
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));
127
128 {
129
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 }
183
184 /////////////////////////////////////////////////
185 // Version including finding a good starting point
186 /////////////////////////////////////////////////
187
188 {
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;
227 }
228
229 cout << endl;
230 cout << "###############################" << endl;
231 cout << "### sloan-ordering finished ###" << endl;
232 cout << "###############################" << endl << endl;
233 return 0;
234 }
235