[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] a question on the isomorphim
From: |
Gabor Csardi |
Subject: |
Re: [igraph] a question on the isomorphim |
Date: |
Tue, 27 Mar 2007 17:06:48 +0200 |
User-agent: |
Mutt/1.5.12-2006-07-14 |
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