[Nauty-list] shortg outputs

Brendan McKay bdm at cs.anu.edu.au
Wed Jan 4 13:50:07 EST 2012


Hi Ken,

I didn't notice your query until William's reply came.

Property (1) is guaranteed if you use both -v and -k. In the next release
-k by itself will also guarantee that, but at the moment it doesn't.

Property (2) is not so easy to achieve. William's approach of using an
internal hash table (please tell us if it works well enough for you)
is not suitable for the production version since it limits the
output to what can be held in memory, but I'd like shortg to be
only limited by disk space.

If your output size fits into memory, it would be better to just
read the graphs, apply nauty, keep the canonical forms in a hash
table, and write the inputs through to the output if their canonical
forms are previously unseen. No sorting required. I put on my to-do
list an option for labelg to do that.

To achieve (1) and (2) not limited by memory size, one could use the
same algorithm with a hashtable/B-tree on disk but that sounds too
slow. Maybe the fastest would be to sort once to remove duplicates
then sort again to put the remaining graphs back into their original
order.

Brendan.

* Kenneth Joseph Ryan <kjryan at bgsu.edu> [120104 12:10]:
> Hi,
> 
> I use shortg -k to reduce files of graphs. The input files in our applications can be rather large (tens of millions of bipartite undirected graphs all with the same number of vertices), and the reductions are typically an order of magnitude or more.
> 
> For a new method to our problem type, each input file will be presorted by a "secondary criterion."  I ultimately need to produce an output file which
> 
> 1)      contains the isomorphic copy within each class that occurs "first" in the input file and
> 
> 2)      the output file needs to preserve input file order.
> At this point, I realize that I could use the class output produced by shortg -vu and then extract the needed subset of input graphs through a separate program, but am hoping to find a direct, more timely solution because the reductions are so large.
> 
> I focused on reading the manual and then even tried my hand at reading nauty code but with no luck, so I moved onto simple examples. Through simple examples I already know that 2) does not happen directly, but I have not constructed an example where 1) did not hold. Does 1) always hold? Is there a setting (or some slick approach) such that I can get 1) AND 2) directly?
> 
> Thanks in advance for your time,
> ----
> Ken Ryan, Associate Professor
> Applied Statistics and Operations Research
> Bowling Green State University
> Bowling Green, Ohio 43403-0267
> Phone: (419)372-2958
> Fax: (419)372-2875
> Email: kjryan at bgsu.edu<mailto:kjryan at bgsu.edu>
> Web: http://www.cba.bgsu.edu/faculty_staff/ryan/
> 
> 
> 
> ----
> Ken Ryan, Associate Professor
> Applied Statistics and Operations Research
> Bowling Green State University
> Bowling Green, Ohio 43403-0267
> Phone: (419)372-2958
> Fax: (419)372-2875
> Email: kjryan at bgsu.edu
> Web: http://www.cba.bgsu.edu/faculty_staff/ryan/
> 

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