[Nauty] How to produce a histogram of graphs?

Brendan McKay bdm at cs.anu.edu.au
Tue Feb 3 22:31:02 EST 2004


If you are Unix/Linux you can use the uniq command.  Feed the graphs
through labelg, then through sort, then feed them into uniq -c.
For example, I made a file xxx containing each 3-vertex graph 3 times
and each 4-vertex graph twice.

% labelg xxx | sort | uniq -c
>A labelg xxx
>Z  34 graphs labelled from xxx to stdout in -0.00 sec.
      3 B?
      3 BG
      3 BW
      3 Bw
      2 C?
      2 C@
      2 CB
      2 CF
      2 CJ
      2 CN
      2 CR
      2 C^
      2 C`
      2 Cr

The number on each line is the number of times each graph occurred.
uniq -c only works if the input is sorted.

You can omit the first two lines (>A, >Z, which go to stderr rather than
stdout) by using labelg -q.

You can also use shortg to get the full detail of which graphs are
isomorphic:

% labelg -q xxx | shortg -vq - xxxy

  1 :   1  16  31
  2 :   2  17  32
  3 :   3  18  33
  4 :   4  19  34
  5 :   5  20
  6 :   6  21
  7 :   7  22
  8 :   8  23
  9 :  11  26
 10 :  12  27
 11 :  10  25
 12 :  14  29
 13 :   9  24
 14 :  13  28
 15 :  15  30

This says that output 1 is isomorphic to inputs 1,16,31, output 2 is
isomorphic to inputs 2,17,32, and so on.

If these options are not adequate for your task, give us an example of
what output you would like.  Maybe it is something I could easily add
to the program.

WARNING: See my note in the next message about the dangers of the
locale environment variables like LANG.

Brendan.




More information about the Nauty mailing list