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
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 //=======================================================================
11 #include <boost/config.hpp>
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>
22 Reverse Cuthill-McKee ordering starting at: 6
25 Reverse Cuthill-McKee ordering starting at: 0
28 Reverse Cuthill-McKee ordering:
32 int main(int , char* [])
34 using namespace boost
;
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
;
42 typedef std::pair
<std::size_t, std::size_t> Pair
;
43 Pair edges
[14] = { Pair(0,3), //a-d
59 for (int i
= 0; i
< 14; ++i
)
60 add_edge(edges
[i
].first
, edges
[i
].second
, G
);
62 graph_traits
<Graph
>::vertex_iterator ui
, ui_end
;
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
);
68 property_map
<Graph
, vertex_index_t
>::type
69 index_map
= get(vertex_index
, G
);
71 std::cout
<< "original bandwidth: " << bandwidth(G
) << std::endl
;
73 std::vector
<Vertex
> inv_perm(num_vertices(G
));
74 std::vector
<size_type
> perm(num_vertices(G
));
76 Vertex s
= vertex(6, G
);
78 king_ordering(G
, s
, inv_perm
.rbegin(), get(vertex_color
, G
),
79 get(vertex_degree
, G
), get(vertex_index
, G
));
80 cout
<< "King ordering starting at: " << s
<< endl
;
82 for (std::vector
<Vertex
>::const_iterator i
= inv_perm
.begin();
83 i
!= inv_perm
.end(); ++i
)
84 cout
<< index_map
[*i
] << " ";
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]))
94 Vertex s
= vertex(0, G
);
96 king_ordering(G
, s
, inv_perm
.rbegin(), get(vertex_color
, G
),
97 get(vertex_degree
, G
), get(vertex_index
, G
));
98 cout
<< "King ordering starting at: " << s
<< endl
;
100 for (std::vector
<Vertex
>::const_iterator i
=inv_perm
.begin();
101 i
!= inv_perm
.end(); ++i
)
102 cout
<< index_map
[*i
] << " ";
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]))
114 king_ordering(G
, inv_perm
.rbegin(), get(vertex_color
, G
),
115 make_degree_map(G
), get(vertex_index
, G
));
117 cout
<< "King ordering:" << endl
;
119 for (std::vector
<Vertex
>::const_iterator i
=inv_perm
.begin();
120 i
!= inv_perm
.end(); ++i
)
121 cout
<< index_map
[*i
] << " ";
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]))