[Nauty-list] Generating oriented graphs

[Brendan McKay]

Hi, If you have nauty installed (version 2.4), then
  directg -G
will produce directed graphs in a format that gives the group
size as the third argument.  For example:

% geng 3 | directg -G
>A geng -d0D2 n=3 e=0-3
>A directg
>Z 4 graphs generated in 0.00 sec
3 0 1
3 1 1 0 2
3 2 2 0 2 2 0
3 2 2 0 2 1 2
3 2 1 0 2 2 1
3 2 2 2 0 2 1
3 3 1 0 2 2 0 1 2
3 3 1 0 2 2 0 2 1
3 4 2 0 2 2 0 1 2 2 1
3 3 1 0 1 0 2 1 2
3 3 3 0 1 2 0 1 2
3 4 2 0 1 1 0 0 2 1 2
3 4 1 0 1 1 0 0 2 2 1
3 4 2 0 1 1 0 2 0 2 1
3 5 1 0 1 1 0 0 2 2 0 1 2
3 6 6 0 1 1 0 0 2 2 0 1 2 2 1
>Z 4 graphs read from stdin; 16 digraphs written to stdout; 0.00 sec

However, the group size does not include the interchange of isolated
vertices, so you will need to filter out the digraphs with two or
more isolated vertices.  If you don't want to have isolated vertices
at all, don't feed in such graphs.  For example:

% geng -d1 3 | directg -G
>A geng -d1D2 n=3 e=2-3
>A directg
>Z 2 graphs generated in 0.00 sec
3 2 2 0 2 1 2
3 2 1 0 2 2 1
3 2 2 2 0 2 1
3 3 1 0 2 2 0 1 2
3 3 1 0 2 2 0 2 1
3 4 2 0 2 2 0 1 2 2 1
3 3 1 0 1 0 2 1 2
3 3 3 0 1 2 0 1 2
3 4 2 0 1 1 0 0 2 1 2
3 4 1 0 1 1 0 0 2 2 1
3 4 2 0 1 1 0 2 0 2 1
3 5 1 0 1 1 0 0 2 2 0 1 2
3 6 6 0 1 1 0 0 2 2 0 1 2 2 1
>Z 2 graphs read from stdin; 13 digraphs written to stdout; 0.00 sec

If you don't want directed cycles of length 2, include the switch -o
on the directg command.

On Unix-like systems (incl Linux and cygwin), you can select those
with no isolated vertices and trivial group like this:

% geng -d1 3 | directg -G | egrep '^[0-9]* [0-9]* 1 '
>A geng -d1D2 n=3 e=2-3
>A directg
>Z 2 graphs generated in 0.00 sec
>Z 2 graphs read from stdin; 13 digraphs written to stdout; 0.00 sec
3 2 1 0 2 2 1
3 3 1 0 2 2 0 1 2
3 3 1 0 2 2 0 2 1
3 3 1 0 1 0 2 1 2
3 4 1 0 1 1 0 0 2 2 1
3 5 1 0 1 1 0 0 2 2 0 1 2

Brendan.


* Blackman Claire <Claire.Blackman at rhul.ac.uk> [090116 07:53]:
> Hi,
> 
> I need to generate the set of non-isomorphic oriented graphs with n
> vertices, with the restriction that each graph must have n equivalence
> classes (so I need to weed out all the ones with less than n equivalence
> classes.) I am new to graph theory and c (but not set theory or
> programming), so would really appreciate some pointers as to where to
> start; if someone could suggest nauty functions that I should be looking
> at, I'd be very grateful.
> 
>  
> 
> Thanks,
> 
> Claire
> 
>  
> 
>  
> 

> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list