[Nauty-list] Question about nauty

Brendan McKay bdm at cs.anu.edu.au
Tue May 11 15:03:23 EST 2010


Hi Jing Yuan,

The distributed version of dreadnaut only uses the packed form of
graph representation, which is inefficient for large sparse graphs.
On a 32-bit computer with 4GB of memory, you should be able to
get to around 100,000 vertices.  If your "very large" graphs are
much smaller than that, there is some other problem and you should
send me more detail and the input that causes the crash.

Nauty also has a sparse representation. An example of how to call it
is in the file nautyex5.c. The next edition of dreadnaut has sparse
form built in, but it isn't available for distribution yet.

Brendan.


* Jing Yuan <yuanj05 at gmail.com> [100509 07:15]:
> Hi all
> 
> Now, I want to use nauty do determin wheater the two graph is isomorphism or
> not and get a vertex mapping between these two graph.
> The two graph is sparse. I use the dreadnaut to do this,but there are some
> problems. Can anyboady help me to solve these problem? Thank you very much
> The procedure is below:
> (1)First,  I converted the two graphs into dreadnaut format and store them
> into two files (G1.txt G2.txt , the number of vertex is N1, N2, N1=N2). The
> graph formats are as follows
> 0: 1 2 3;
> 1: 2 4;
> 2: 4 5;
> 3: ;
> 4:;
> 5;
> (2) Then I use the command showed in page37 of the nauty User's Guidebelow
> to run nauty.
> > c -a -m
> >n=N1 g<G1.txt
> >x @
> >g<G2.txt
> >x
> >##
> The problem is when the number of vertex (N1) is very large, the program was
> wrong. it said the segmentation fault.  My questions are as follows:
> (1) The above method is right to determin wheater the two graph is
> isomorphism or not ?
> (2) If the method is right, how can I solve the segmentation fault problem
> when the vertex number is very large.

> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list





More information about the Nauty mailing list