1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
# Copyright (c) 1997-2024
# Ewgenij Gawrilow, Michael Joswig, and the polymake team
# Technische Universität Berlin, Germany
# https://polymake.org
#
# 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.
#-------------------------------------------------------------------------------
use application "topaz";
print "This defines functions random_growth(n,d) and coupon_collector(n,d)\n",
"for producing random simplicial complexes of dimension d on n vertices.\n",
"this is the working version.\n";
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 print_homology ($$) {
my ($text,$hom)=@_;
my $d=$#{$hom}; # dimension
print $text, " : ";
for (my $i=0; $i<=$d; ++$i) {
print "H_$i = ", $hom->[$i];
print ", " unless $i==$d;
}
print "\n";
}
# Produce a sequence of random complexes of dimension d on n vertices.
# Shuffle all possible d-simplices, and then add one after another
# until the codimension-1-homology vanishes.
sub random_growth($$) {
my ($n,$d)=@_; # number of vertices and dimension
die "n>d>0 required\n" unless $n>$d && $d>0;
#my @set=(0..$n-1);
my $set = sequence(0,$n);
my $complete_skeleton=all_subsets_of_k($set,$d);
my @simplices=randomize(@{all_subsets_of_k($set,$d+1)});
my $k=0;
print "The (d-1)-skeleton has ", $complete_skeleton->size, " faces, and there are ", scalar(@simplices), " possible d-faces.\n";
while (1) {
my @faces=(@$complete_skeleton,@simplices[0..$k]);
my $complex=new SimplicialComplex("simplicial_complex", INPUT_FACES=>\@faces);
print_homology ("complex #$k",$complex->HOMOLOGY);
++$k;
my $hom=$complex->HOMOLOGY->[$d-1];
last if "$hom" eq "{} 0";
}
print "time to complete: ", $k/scalar(@simplices), "\n";
}
# Produce a sequence of random complexes of dimension d on n vertices.
# Repeatedly pick d-simplices at random until the codimension-1-homology vanishes.
sub coupon_collector($$) {
my ($n,$d)=@_; # number of vertices and dimension
die "n>d>0 required\n" unless $n>$d && $d>0;
my $set = sequence(0,$n);
my @complete_skeleton=@{all_subsets_of_k($set,$d)};
my @simplices=@{all_subsets_of_k($set,$d+1)};
my @faces=@complete_skeleton;
print "The (d-1)-skeleton has ", scalar(@complete_skeleton), " faces, and there are ", scalar(@simplices), " possible d-faces.\n";
my $k=0;
while (1) {
my $i=int(rand(scalar(@simplices)));
push @faces, $simplices[$i];
my $complex=new SimplicialComplex("simplicial_complex", INPUT_FACES=>\@faces);
print_homology ("complex #$k",$complex->HOMOLOGY);
++$k;
my $hom=$complex->HOMOLOGY->[$d-1];
last if "$hom" eq "{} 0";
}
print "time to complete: ", $k/scalar(@simplices), "\n";
}
1
# Local Variables:
# mode: perl
# c-basic-offset:3
# End:
|
