[Nauty-list] maintaining a set of non-isomorphic graphs

Susanne Nieß niess at ma.tum.de
Fri Jan 6 05:00:06 EST 2012


Yes, this is what I do.  I have refined the procedure a bit by sorting 
the graphs according to number of edges and number of isolated vertices 
and then comparing only to those in the correct class (I know those 
parameters of the new graph because of the way how I am producing them).

Susanne Nieß


On 01/05/12 06:52 PM, Gregory Puleo wrote:
> More efficient would maybe be storing the already-seen canonical 
> graphs in a hash table -- am I understanding correctly that your 
> solution compares the new graph to every graph already in the list?
>
> -Greg
>
> 2012/1/5 Susanne Nieß <niess at ma.tum.de <mailto:niess at ma.tum.de>>
>
>     This is what I am already doing. I use nauty with getcanon=TRUE to
>     produce a canonically labelled version of every graph in the list
>     and of any new graph I want to test. Then I compare the
>     canonically labelled graphs with memcmp. I suppose that should
>     also work for you. If any one knows a more efficient method, I'd
>     like to learn it.
>
>     Susanne Nieß
>
>
>     On 01/04/12 04:10 AM, Grant Farmer wrote:
>
>         Hi,
>
>         I am trying to maintain a set of non-isomorphic graphs in my
>         program and I am hoping to use Nauty to do so.  How would one
>         go about doing that?  I would also like it to be able to
>         quickly test if a graph has an isomorphic graph already in the
>         set or not.  The geng program will not work for my purposes
>         because I do not want all graphs that are non-isomorphic, just
>         the ones that I am actually using.  Thank you for any help you
>         may be able to provide.
>
>         Grant Farmer
>
>         _______________________________________________
>         Nauty-list mailing list
>         Nauty-list at cs.anu.edu.au <mailto:Nauty-list at cs.anu.edu.au>
>         http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
>
>
>
>     _______________________________________________
>     Nauty-list mailing list
>     Nauty-list at cs.anu.edu.au <mailto:Nauty-list at cs.anu.edu.au>
>     http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
>
>
>
>
> -- 
> Gregory Puleo
> http://www.math.uiuc.edu/~puleo/ <http://www.math.uiuc.edu/%7Epuleo/>





More information about the Nauty mailing list