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

From: Kris Vorwerk (vorwerk_at_[hidden])
Date: 2004-01-13 21:12:45

Hello,

After more digging into this matter, I'm fairly sure that the problem
lies in the fact that disjoint sets of nodes aren't looped over in
cuthill_mckee_ordering.hpp.  Consequently, the out-edges of the nodes
are examined, but if the out-edges never connect to another set of
nodes, then only a portion of each disjointed graph is ever considered
for reordering.  This can be somewhat disastrous, because the ordering
results will vary immensely depending on which starting vertex was used
(and, by extension, which disjoint set was reordered).  This seems
equivalent to only scanning through one of the sets of level sets in the
RCM algorithm.  After a very quick glance at the
minimal_degree_ordering.hpp and sloan_ordering.hpp code, I suspect that
they also won't work quite right with disjoint graphs.

I don't know if this is intended behaviour or not, as the documentation
didn't really seem to hint toward how these kinds of graphs should be
handled.  In the meantime, I started to hack together a solution for my
problem, but have found it to be rather "unpretty".  (Basically, I use
the Boost connected_components function to find disconnected components,
then I loop through each disconnected component, find a good
pseudo-peripheral starting vertex, and do the reordering just for the
vertices in that component.  I'm not even really sure that this is the
best way to fix the RCM code.)  

Anyway, given my lack of experience with Boost, my hack is very ugly,
but I thought I'd let ppl know where I think the problem lies, just in
case they were having similar issues.

regards,
Kris

On Sun, 2004-01-11 at 11:28, Kris Vorwerk wrote:
> 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).
[snip]