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

From: Kris Vorwerk (vorwerk_at_[hidden])
Date: 2004-01-14 18:03:53

> I wish I had time to look at your problem and solution... alas I'm swamped
> with work on iterator adaptor stuff for the C++ standard TR.

No prob -- I totally understand :)  (In fact, I'm swamped with trying to
get my grad school stuff working, which is why I've resorted to
hacking together code to make Boost work for me :)

The following is rough and not very elegant, but it seems to work, I
believe.  (Well, it sort of works.  I will explain what I mean after the
code, below.)

// BEGIN CODE SNIPPET -------------------------------------------
// This is just the code that I changed... (The detail code 
// remains the same.)

namespace boost {

  // Reverse Cuthill-McKee algorithm with a given starting Vertex.
  //
  // This algorithm requires user to provide a starting vertex to
  // compute RCM ordering.

  template <class Graph, class OutputIterator,
            class ColorMap, class DegreeMap>
  OutputIterator
  cuthill_mckee_ordering(Graph& g,
                  std::deque< typename
graph_traits<Graph>::vertex_descriptor >
vertex_queue,
                         OutputIterator inverse_permutation, 
                         ColorMap color, DegreeMap degree)
  {
    typedef typename property_traits<DegreeMap>::value_type DS;
    typedef typename property_traits<ColorMap>::value_type ColorValue;
    typedef color_traits<ColorValue> Color;
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

    typename graph_traits<Graph>::vertex_iterator ui, ui_end;
    for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
      put(color, *ui, Color::white());

    typedef indirect_cmp<DegreeMap, std::greater<DS> > Compare;
    Compare comp(degree);

    boost::queue<Vertex> bfs_queue;
    std::priority_queue<Vertex, std::vector<Vertex>, Compare> 
      degree_queue(comp);
    Vertex u, v;

    // The vertex_queue contains the starting vertices that we will
consider in
    // our RCM ordering.  There should be one starting vertex for each
disjoint
    // forest in the graph.
    while( !vertex_queue.empty() ) {
            Vertex s = vertex_queue.front();
            vertex_queue.pop_front();

            // Like BFS, except the adjacent vertices are visited in
increasing
            // order of degree.
            put(color, s, Color::gray());
            bfs_queue.push(s);
            while (! bfs_queue.empty()) {
              u = bfs_queue.top(); bfs_queue.pop();
              *inverse_permutation++ = u;
              typename graph_traits<Graph>::out_edge_iterator ei,
ei_end;
              for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end;
++ei) {
                v = target(*ei, g);
                if (get(color, v) == Color::white()) {
                  put(color, v, Color::gray());
                  degree_queue.push(v);
                }
              }
              while (!degree_queue.empty()) {
                v = degree_queue.top(); degree_queue.pop();
                bfs_queue.push(v);
              }
              put(color, u, Color::black());
            } // while
    }
    return inverse_permutation;
  }  
  

  template < class Graph, class OutputIterator, 
             class Color, class Degree >
  inline OutputIterator 
  cuthill_mckee_ordering(Graph& G, OutputIterator inverse_permutation, 
                         Color color, Degree degree)
  {
    typedef typename boost::graph_traits<Graph>::vertex_descriptor
Vertex;
    typedef typename boost::graph_traits<Graph>::vertex_iterator  
VerIter;

    VerIter     ri = vertices(G).first;
    Vertex      r = *ri;
    Vertex      s;

        // Check the number of connected components in G.
        std::vector<int>        c( num_vertices( G ) );
        std::deque<Vertex>      vertex_queue;

        int num = boost::connected_components(G, &c[0]);

        // Common case: we only have one set.
        if( num <= 1 ) {
                s = find_starting_node(G, r, color, degree);
                vertex_queue.push_front( s );

        } else {
                // We seem to have more than one disjoint set.  So, find
good
                // starting nodes within each of the subgraphs, and then
add
                // these starting nodes to our vertex queue.
                int                     num_considered = 0;
                std::vector<int>        sets_considered( num );
                std::fill( sets_considered.begin(),
sets_considered.end(), 0 ); //
Sanity

                for( unsigned int i = 0; i < c.size(); ++i ) {
                        // If it's the first time we've considered this
set,
                        // then find a good pseudo peripheral node for
it.
                        // Otherwise, keep going until we've considered
all of
                        // the sets.
                        if( sets_considered[c[i]] == 0 ) {
                                ++num_considered;
                                s = find_starting_node(G, i, color,
degree);
                                assert( c[s] == c[i] );
                                vertex_queue.push_back( s );

                                if( num_considered >= num ) {
                                        break;
                                }
                        }
                        ++(sets_considered[c[i]]);
                }
        }
    return cuthill_mckee_ordering(G, vertex_queue, inverse_permutation,
color, degree);
  }
} // namespace boost

// END CODE SNIPPET --------------------------------------------

Okay, so this code basically identifies disconnected components in the
graph, and loops over the components.  The pseudoperipheral pair code
doesn't need to be changed.  And, these changes seem to give good
reorderings.  I'm sure that the code can be cleaned up, so this is 
really just an example of how I've tackled the problem...

One caveat that I'd like to point out, however, and what I casually
reference above, is that in making this
change, I think that I discovered another potentially more serious
problem which occurs when I feed in quite a large graph derived from one
of my matrix problems.  (The graph has about 272000 vertices -- a
graphviz format file representing it takes about 1.8MB ;).

When I feed this fairly large graph into connected_components(),
as you know, connected_components() does a DFS, but somewhere along the
line, it segfaults in the adjacency_list<> code while it's DFSing
through the graph.  (I've run it through 'ddd', and have identified
where the segfault occurs, but it will take me a while to figure out why
this is happening.)  

I'm not sure how much time I have to debug this problem, so I think that
I will just have to modify the cuthill_mckee_ordering to work on my MTL
sparse matrix instead of relying on Boost graph calls.  

If possible, I will try to write some short sample code that recreates
the segfault.  (Then, since I'm not sure if this mailing list can handle
compressed attachments, I'll put the sample graph data on my website or
something so that developers can take a look at it.)  I will post a
description of the bug in a new message, as soon as I'm able to better
describe why the bug's happening.  (I mean, who knows, maybe I'm
incompetent and building an invalid graph or something.)

-kris