Re: [igraph] a question on the isomorphim

[Gabor Csardi]

Tracy,

the currectly implemented method cannot work for graphs with 10 vertices.

If you have n vertices in an undirected graph then you can have 
n(n-1)/2 different edges. Every edge is either present or not,
so you have 

 n(n-1)/2
2

different graphs altogether. To store the isomorphism class for so many 
graphs is possible if you have n=4 (64 graphs) or n=5 (1024 graphs),
but centainly not possible for n=10 (about 3.518437e+13 graphs),
the latter would require 262144 gigabytes of memory/disk space if we
store the isomorphism class in 4 bytes. 

However if we sort the vertices of the graph according to their degree
that might help, but i need to do some calculations for this.

I recommend using the nauty library if you need a solution quickly.

Gabor

On Tue, Mar 27, 2007 at 01:07:41PM +0800, yu chen wrote:
>    Hi Gabor,
> 
>        Thanks for your reply.
> 
>        Actually I'm doing isomorphism analysis on undirected graphs with no
>    more than 10 vertices. But there are millions of them. That's why I want
>    to find some low-cost algorithm. The one used in i-graph seems quite nice
>    if it could be scaled to graphs with more vertices. So could you please
>    tell me the algorithm or show me some souce code of how to precompute the
>    isomorphism classes? I'm quite interested in that.
> 
>        Thanks a lot.
> 
>    Tracy
> 
>    On 3/26/07, Gabor Csardi <address@hidden> wrote:
> 
>      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
>      > [3]http://lists.nongnu.org/mailman/listinfo/igraph-help
> 
>      --
>      Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK
> 
> References
> 
>    Visible links
>    1. mailto:address@hidden
>    2. mailto:address@hidden
>    3. http://lists.nongnu.org/mailman/listinfo/igraph-help
>    4. mailto:address@hidden

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