Hello, I'm a fairly new Boost user, so please forgive me if I'm completely out of whack here. I'm presently using Boost's reverse Cuthill-Mckee ordering to reduce the bandwidth of some very large symmetric, positive definite sparse matrices that I'm investigating. Generally, the cuthill_mckee_ordering() has worked quite well, although a short while ago, I began noticing that it occasionally gave an invalid ordering (i.e., the permutations spit out by the algorithm would have multiple vertexes all the same, which, when used to permute my matrices, would destroy my problem). It took me a while to figure out what was going on, but I've finally distilled a small enough example that exhibits the problem. Consider the following matrix: Matrix: 6x6 [ [3.66667,0,-0.5,0,0,0], [0,2.66667,0,-0.222222,0,0], [-0.5,0,1.66667,0,0,-0.222222], [0,-0.222222,0,3.33333,-2.22222,0], [0,0,0,-2.22222,4.66667,0], [0,0,-0.222222,0,0,4.66667] ] Using fairly straightforward code, I loop through the non-zeros, and add edges to an undirected Boost graph (basically the same as the cuthill_mckee_ordering.cpp example in the docs). Here is the graph that gets created for the above problem, in Graphviz format: graph G { 0; 1; 2; 3; 4; 5; 0--0 ; 0--2 ; 1--1 ; 1--3 ; 2--2 ; 2--5 ; 3--3 ; 3--4 ; 4--4 ; 5--5 ; } And, if I run this example using the cuthill_mckee_ordering technique (or if I modify cuthill_mckee_ordering.cpp to use these vertices and edges), I get the following permutation (using the pseudo-peripheral heuristic): Inv_perm: 0 0 0 0 2 5 You can see, from the Graphviz output, that this graph has two disconnected sets of vertices, which is where I think the problem lies. It may be a problem in my understanding of how to setup the Boost graph, or perhaps a problem in the reordering technique. You'll notice that, in my example, I've eliminated the duplicate edges (such as 2-5 being the same as 5-2) -- I've tried adding them in, too, but it hasn't changed the result. I've noticed that, if one of my matrices produces a graph in which there are no disconnected sets of vertices, the RCM ordering works fine. It's only when the graph is disconnected in this fashion that the ordering fails. I've also noticed that, when using this kind of disconnected graph, if I sometimes select a random starting vertex (instead of the pseudo-peripheral pair heuristic), the cuthill_mckee_ordering segfaults. I've attached some sample code below that seems to exhibit the problem. I'm certainly open to the possibility that it's a problem in my understanding of how to use the library. Also, my Boost version is: 1.30.2 (Redhat RPM) Any thoughts would be appreciated. regards, Kris ============================================================== (borrowed and slightly modified from cuthill_mckee_ordering.cpp) #include <boost/config.hpp> #include <vector> #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/cuthill_mckee_ordering.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/bandwidth.hpp> int main( int, char *[] ) { using namespace boost; using namespace std; typedef adjacency_list < vecS, vecS, undirectedS, property < vertex_color_t, default_color_type, property < vertex_degree_t, int > > > Graph; typedef graph_traits < Graph >::vertex_descriptor Vertex; typedef graph_traits < Graph >::vertices_size_type size_type; typedef std::pair < std::size_t, std::size_t > Pair; //graph G {0;1;2;3;4;5;0--0 ;0--2 ;1--1 ;1--3 ;2--2 ;2--5 ;3--3 ;3--4 ;4--4 ;5--5 ;} Pair edges[] = { Pair( 0, 0 ), Pair( 0, 2 ), Pair( 1, 1 ), Pair( 1, 3 ), Pair( 2, 2 ), Pair( 2, 5 ), Pair( 3, 3 ), Pair( 3, 4 ), Pair( 4, 4 ), Pair( 5, 5 )}; Graph G( 6 ); for( int i = 0; i < 10; ++i ) { std::cout << edges[i].first << ", " << edges[i].second << std::endl; add_edge( edges[i].first, edges[i].second, G ); } graph_traits < Graph >::vertex_iterator ui, ui_end; property_map < Graph, vertex_degree_t >::type deg = get( vertex_degree, G ); for( boost::tie( ui, ui_end ) = vertices( G ); ui != ui_end; ++ui ) { deg[*ui] = degree( *ui, G ); } property_map < Graph, vertex_index_t >::type index_map = get( vertex_index, G ); std::cout << "original bandwidth: " << bandwidth( G ) << std::endl; std::vector < Vertex > inv_perm( num_vertices( G ) ); std::vector < size_type > perm( num_vertices( G ) ); // reverse cuthill_mckee_ordering cuthill_mckee_ordering( G, inv_perm.rbegin(), get( vertex_color, G ), make_degree_map( G ) ); cout << "Reverse Cuthill-McKee ordering:" << endl; cout << " "; for( std::vector < Vertex >::const_iterator i = inv_perm.begin(); i != inv_perm.end(); ++i ) { cout << index_map[*i] << " "; } cout << endl; for( size_type c = 0; c != inv_perm.size(); ++c ) { perm[index_map[inv_perm[c]]] = c; } std::cout << " bandwidth: " << bandwidth( G, make_iterator_property_map( &perm[0], index_map, perm[0] ) ) << std::endl; return 0; }