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]