[Boost-users] Problems with Reverse Cuthill-Mckee?

From: Kris Vorwerk (vorwerk_at_[hidden])
Date: 2004-01-11 11:28:48

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;
}