[Nauty-list] graph isomorphism

Brendan McKay bdm at cs.anu.edu.au
Tue Feb 17 18:05:27 EST 2009


There isn't such a procedure.  You just need to compare them
word by word.  Here are two methods:

boolean
aresame_packed(graph *g1, graph *g2, int m, int n)
{
    set *g1p,*g2p,*g1pmax;

    g1pmax = g1 + m*(size_t)n;
    for (g1p = g1, g2p = g2; g1p < g1pmax; ++g1p, ++g2p)
        if (*g1p != *g2p) return FALSE;

    return TRUE;
}

#define ARESAME_PACKED(g3,g2,m,n) memcmp(g1,g2,(m)*sizeof(graph)*(n))

In each case I am assuming the same value of m is used for each graph.
I'm also ignoring vertex colours: you must have the same number of
vertices of each colour (which is best tested before calling nauty
and not after).

Brendan.

* Sara Voss <sarasvoss at gmail.com> [090217 17:53]:
> I read through the manual and don't think I found the answer to my
> question.  I am trying to use nauty to check for isomorphisms using a
> dynamic packed form.  Is there a built in aresame function for the packed
> form or just the sparse form.  Thanks.

> _______________________________________________
> 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