[Nauty] Generating trees

[Brendan McKay]

* Felix Goldberg <felixg at techunix.technion.ac.il> [041124 12:47]:
> Hi,
> 
> I want to generate all trees on $n$ vertices with geng. Is there a way do
> this?
> 
> Thanks,
> Felix.

Your message was trapped by the mailing list software with this
explanation:
   Blind carbon copies or other implicit destinations are not
   allowed. Try reposting your message by explicitly including the
   list address in the To: or Cc: fields.
I guess it is an anti-spam measure.  The moral is to not use Bcc
on a message sent to the list.

Now to your question.  geng can be used by specifying connectivity
and the required number of vertices and edges.  For example:

% geng -c -u 16 15
>A geng -cd1D15 n=16 e=15
>Z 19320 graphs generated in 6.42 sec

You can help it out with the hint that trees are bipartite and have
no 4-cycles:

% geng -cbf -u 16 15
>A geng -cfbd1D15 n=16 e=15
>Z 19320 graphs generated in 0.43 sec

(Yes, geng should be able to figure that out for itself.
Next release...)

Maybe that is fast enough for your purposes.  If not, there are some
other programs not presently in the package that are much faster:

% gentree -u 25
104636890 trees generated; cpu=6.80 sec

...and I have some code from Frank Ruskey which is slower but allows
some additional parameters like bounds on maximum degree.

Brendan.