[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