[Cdk-devel] Patch #2740730 status

[Mark R. <ma...@eb...>]

Here's an update from Ulrich Bauer regarding patch #2740730 received today.
Just to keep you informed on this patch-to-be. Hopefully he'll manage 
some more spare time to complete the fix.

Mark


-------- Original Message --------
Subject: 	Re: SSSR (CDK)
Date: 	Wed, 10 Jun 2009 11:25:01 +0200
From: 	Ulrich Bauer <ba...@ma...>
To: 	Mark Rijnbeek <ma...@eb...>

	


Hi Mark!

Sorry for the late reply, the last few weeks have been quite busy...

I found an error in the method to compute fundamental cycles (this is  
done in the first step of the minimum cycle basis algorithm). The  
fundamental cycles are defined al follows: first a minimum spanning  
tree of the molecule graph is computed. All non-tree edges now define  
a unique cycle together with some edges of the spanning tree: the  
unique path in the spanning tree between the endpoints of the non-tree  
edge.

My code tried to construct this path by going to the root of the tree  
from both endpoints, so some edges could be visited twice. I fixed  
that problem, but there seems to be another one. I send you the  
modified version of the class SimpleCycleBasis containing the  
algorithm, and also the class SimpleCycle, where I added some  
assertions. If you use -enableassertions with the Java VM, you will  
see that the test class you sent me still produces some errors.

If you try to debug the code and have any questions, don't hesitate to  
ask me. There is also documentation available at http://num.math.uni-goettingen.de/~bauer/pub/CDK-Ringsearch.pdf 
  . I will also try to find the remaining errors.

Best regards, Ulrich