| Subject: | union miscounts rank |
I've been enjoying looking at your excellent Graph perl module.
There is a minor bug in Graph::Base::_union_vertex_set. If it is called with two vertices which are already in the same vertex set, it incorrectly increments the rank of the set. It should take no action in that situation. Since the ranks are only used to keep the vertex set trees from growing too tall, this doesn't cause the module to misbehave in any overt way. However, there is a small performance cost when the trees grow more than they should.
It appears that you based this code on the disjoint-set algorithm given by Cormen, Leiserson, and Rivest. If you look carefully, you'll find a little note saying that their Union procedure assumes its arguments are disjoint to start with.
The fix is trivial. Patch attached.
*** lib/Graph/Base.pm.orig Wed May 21 10:05:57 2003
--- lib/Graph/Base.pm Wed May 21 10:54:53 2003
***************
*** 306,311 ****
--- 306,312 ----
my $su = $G->vertex_set( $u );
my $sv = $G->vertex_set( $v );
+ return if $su eq $sv;
my $ru = $G->{ VertexSetRank }->{ $su };
my $rv = $G->{ VertexSetRank }->{ $sv };