#  Copyright (c) 1997-2004
#  Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
#  http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de
#
#  This program is free software; you can redistribute it and/or modify it
#  under the terms of the GNU General Public License as published by the
#  Free Software Foundation; either version 2, or (at your option) any
#  later version: http://www.gnu.org/licenses/gpl.txt.
#
#  This program is distributed in the hope that it will be useful,
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more details.
#-----------------------------------------------------------------------------
#  $Project: polymake $$Id: grow_complex 5639 2004-12-17 21:36:25Z gawrilow $

application 'topaz';

# Start with the complete graph on $n vertices and randomly insert $d-faces until the ($d-1)-homology is trivial.
# Output integer homology for each intermediate complex.

# This is a call example:
# random_growth(5,3)

sub randomize(@) {
   my @set=@_;
   my $n=@set;
   my @list=();
   for (my $i=$n; $i>0; --$i) {
      my $k=int(rand($i));
      push @list, $set[$k];
      splice @set, $k, 1;
   }
   return @list;
}

sub derefify(@) {
   map { "{@$_}\n" } @_;
}

sub random_growth($$) {
  my ($n,$d)=@_;
  my @set=(0..$n-1);
  my @complete_graph=derefify(all_subsets_of_k(2,@set));
  my @triangles=derefify(randomize(all_subsets_of_k($d,@set)));

  my $k=0;
  while (1) {
    my @faces=(@complete_graph,@triangles[0..$k]);
    my $complex=SimplicialComplex("simplicial_complex", INPUT_FACES=>\@faces);
    print "$k\n", @{$complex->HOMOLOGY}, "\n";
    ++$k;
    last if $complex->HOMOLOGY->[$d-2] eq "({} 0)\n";
  }
  print "time to complete: ", $k/scalar(@triangles), "\n";
}

sub coupon_collector($$) {
  my ($n,$d)=@_;
  my @set=(0..$n-1);
  my @complete_graph=derefify(all_subsets_of_k(2,@set));
  my @triangles=derefify(all_subsets_of_k($d,@set));
  my @faces=@complete_graph;

  my $k=0;
  while (1) {
    my $i=int(rand(scalar(@triangles)));
    push @faces, $triangles[$i];
    my $complex=SimplicialComplex("simplicial_complex", INPUT_FACES=>\@faces);
    print "$k\n", @{$complex->HOMOLOGY}, "\n";
    ++$k;
    last if $complex->HOMOLOGY->[$d-2] eq "({} 0)\n";
  }
  print "time to complete: ", $k/scalar(@triangles), "\n";
}

1

# Local Variables:
# mode: perl
# c-basic-offset:3
# End: