use warnings;
use feature 'state';
use strict;
no strict 'refs';

use Data::Dumper;

sub gen
{
    my $n = shift;
    return "O" if $n == 0;
    my $rand = int(rand(3));
    return "O" if $rand == 0;
    $n--;
    return { P => [ gen($n), gen($n) ] } if $rand == 1;
    return { S => [ gen($n), gen($n) ] } if $rand == 2;
}

sub to_dot
{
    state %counters = (node => 0, P => 0, S => 0);
    my $data = shift;
    # my $depth = shift;
    return "a_" . $counters{node}++ if($data eq 'O');
    my ($kind) = keys %{$data};
    my @inners;
    my $separator;
    $separator = '; ' if $kind eq 'P';
    $separator = ' -> ' if $kind eq 'S';
    foreach my $subgraph (@{${$data}{$kind}})
    {
        my $subdot = to_dot($subgraph);
        $subdot =~ s/^/	/gm;
        push @inners, $subdot;
    }
    my $inner = join $separator, @inners;
    my $block = <<END;
subgraph  {
$inner
}
END
    chomp($block);
    return $block
}

my $g = gen(5);
print "digraph {\n	rankdir = BT;\n";
print to_dot($g);
print "\n}";