Re: [boost] BGL isomorphism broken

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-11-29 02:23:54

Hi Doug,

I just checked in the fixes to isomorphism. Looks like it hadn't been tested
with directed graphs, and there were a couple other mistakes as well. It now
passes your test code. I also checked in a change to the test code to use
the Boost.Random library instead of the stuff from stdlib.h.

For fun I created a more efficient version of verify_isomorphism, but I
haven't checked that in. It's attached.

Cheers,
Jeremy

On 11/28/01 11:08 PM, "Douglas Gregor" <gregod_at_[hidden]> wrote:

> On Wednesday 28 November 2001 06:14 pm, you wrote:
>> Oh, and can you move the verify_isomorphism function into the test file, or
>> perhaps a separate header? (and send me a copy too please).
> 
> Done. libs/graph/test/isomorphism.cpp will test the current isomorphism
> implementation. verify_isomorphism is in there, but it's not exactly an
> efficient implementation... what's an O(n^4) verifier matter when
> you're verifying an O(n!) algorithm, anyway?
> 
> Doug
> 
> Info: http://www.boost.org  Unsubscribe:
> <mailto:boost-unsubscribe_at_[hidden]>
> 
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
> 
> 

-- 
Jeremy Siek                          http://www.osl.iu.edu/~jsiek
Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
C++ Booster (http://www.boost.org)   office phone: [phone]