address@hidden: Re: [igraph] a question on the isomorphim]

[Gabor Csardi]

FYI,
G.

----- Forwarded message from yu chen <address@hidden> -----

Date: Thu, 29 Mar 2007 17:34:34 +0800
From: yu chen <address@hidden>
To: Gabor Csardi <address@hidden>
Subject: Re: [igraph] a question on the isomorphim

   Hi Gabor,

       Actually I've used the boost graph library. They use an
   optimized back-trace algorithm,
   [1]http://www.boost.org/libs/graph/doc/isomorphism.html , it seems that
   the performance is fairly good since I only test on those small graphs.

      BTW, do you know what is the number of all the possible isomorphism
   classes for a connected graph with size from 5 to 10? Or there is some way
   to calculate?

      Thanks for your help. You're so nice.
    Tracy

   On 3/28/07, Gabor Csardi <address@hidden > wrote:

     Tracy,

     actually i just checked the isomorphism algorithms and found
     [3]http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf
     which is not much worse than nauty, for some graphs even better,
     and it is also very easy to implement contrary to nauty. So you
     might also consider implementing it or using the code they offer
     online. I will also implement it in igraph, but that might take
     some weeks as i'm busy with other things.

     FYI,
     G.

     On Wed, Mar 28, 2007 at 09:37:23AM +0800, yu chen wrote:
     >    Hi Gabor,
     >
     >        Thanks a lot. That's really helpful.
     >
     >    Tracy
     >
     >

     --
     Csardi Gabor < address@hidden>    MTA RMKI, ELTE TTK

References

   Visible links
   1. http://www.boost.org/libs/graph/doc/isomorphism.html
   2. mailto:address@hidden
   3. http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf
   4. mailto:address@hidden

----- End forwarded message -----

-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK