Re: [igraph] a question on the isomorphim

[Gabor Csardi]

Tracy,

the current isomorphism implementation is not very useful as it works
only for graphs with 3 or 4 vertices. The best known algorithm 
is implemented in the nauty library but unfortunately i cannot use 
that since it is not GPL conform. So it needs to be reimplemented, but
the implementation is not easy at all. 

The current limited igraph implementation works by precalculating the
isomorphism classes for all possible networks and storing them in an
array. The igraph sources contain the arrays only and the isoclass
function just looks up the corresponding element in the array.

The reason for having these limited isomorphism functions in igraph
is that we need them for the motif detection functions.

Gabor

PS. please consider signing up the mailing list, mails sent by non-members
are not sent to the list by default to prevent spamming. Thanks.

On Mon, Mar 26, 2007 at 05:50:36PM +0800, yu chen wrote:
>    Hi all,
> 
>        I'm a new user of the igraph-library. I'm looking at the isomorphism
>    algorithm in it. Would any one please give an explanation to the algorithm
>    (say the one used in igraph_isoclass function)? It seems quite mysterious
>    to me.
> 
>        Thanks in advance.
> 
>    Yours
>    Tracy

> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help


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