chiark
/
gitweb
/
~ian
/
appendix-a6.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
0627d3e
)
seems to work
author
Ian Jackson
<ijackson@chiark.greenend.org.uk>
Sun, 2 Feb 2014 20:40:14 +0000
(20:40 +0000)
committer
Ian Jackson
<ijackson@chiark.greenend.org.uk>
Sun, 2 Feb 2014 20:40:18 +0000
(20:40 +0000)
parse
patch
|
blob
|
history
diff --git
a/parse
b/parse
index c04d33b0083cea24f5495e5b35d9e2318083fe1e..adb3d7df3ad1062d5759645458f61b9513087644 100755
(executable)
--- a/
parse
+++ b/
parse
@@
-147,10
+147,15
@@
foreach my $i (0..$#choices) {
my $defeats = Graph::Directed->new; # A.6(4)
my $defeats = Graph::Directed->new; # A.6(4)
-foreach my $ia (0..$#ch) {
- foreach my $ib (0..$#ch) {
- my $vab = $vab[$ia][$ib];
- my $vba = $vab[$ib][$ia];
+sub chremain () {
+ return grep { !$ch[$_]{Dropped} } (0..$#ch);
+}
+
+foreach my $ia (chremain()) {
+ $defeats->add_vertex($ia);
+ foreach my $ib (chremain()) {
+ my $vab = scalar @{ $vab[$ia][$ib] };
+ my $vba = scalar @{ $vab[$ib][$ia] };
next unless $vab > $vba;
print "defeat: $choices[$ia] beats $choices[$ib] ($vab > $vba)\n";
$defeats->add_vertex($ia,$ib);
next unless $vab > $vba;
print "defeat: $choices[$ia] beats $choices[$ib] ($vab > $vba)\n";
$defeats->add_vertex($ia,$ib);
@@
-168,6
+173,8
@@
sub weaker ($$) {
return 0;
}
return 0;
}
+print "defeats graph: $defeats\n";
+
our $schwartz;
for (;;) {
our $schwartz;
for (;;) {
@@
-177,14
+184,16
@@
for (;;) {
my $tdefeats = $defeats->transitive_closure();
my $tdefeats = $defeats->transitive_closure();
- print "# schwartz set A.6(6)\n";
+ print "closure graph: $tdefeats\n";
+
+ print "# Schwartz set A.6(6)\n";
$schwartz = $defeats->copy();
$schwartz = $defeats->copy();
- foreach my $ia (
0..$#ch
) {
- foreach my $ib (
0..$#ch
) {
- next if $tdefeats->has_edge($ia,$b);
- next if !$tdefeats->has_edge($b,$ia);
+ foreach my $ia (
chremain()
) {
+ foreach my $ib (
chremain()
) {
+ next if $tdefeats->has_edge($ia,$
i
b);
+ next if !$tdefeats->has_edge($
i
b,$ia);
print "not in Schwartz set: $choices[$ia] because $choices[$ib]\n";
$schwartz->delete_vertex($ia);
last;
print "not in Schwartz set: $choices[$ia] because $choices[$ib]\n";
$schwartz->delete_vertex($ia);
last;
@@
-195,7
+204,7
@@
for (;;) {
our @weakest = ();
our @weakest = ();
- foreach my $edge (
@{ $schwartz->edges() }
) {
+ foreach my $edge (
$schwartz->edges()
) {
if (!@weakest) {
# no weakest edges yet
} elsif (weaker($edge, $weakest[0])) {
if (!@weakest) {
# no weakest edges yet
} elsif (weaker($edge, $weakest[0])) {
@@
-213,8
+222,8
@@
for (;;) {
last unless @weakest;
printf "weakest defeats %d > %d",
last unless @weakest;
printf "weakest defeats %d > %d",
- (scalar @{ $vab[$_->[0]][$_->[1]]
) }
,
- (scalar @{ $vab[$_->[1]][$_->[0]]
) }
;
+ (scalar @{ $vab[$_->[0]][$_->[1]]
})
,
+ (scalar @{ $vab[$_->[1]][$_->[0]]
})
;
foreach my $weakest (@weakest) {
my ($ia,$ib) = @$weakest;
print "weakest defeat $choices[$ia] > $choices[$ib]\n";
foreach my $weakest (@weakest) {
my ($ia,$ib) = @$weakest;
print "weakest defeat $choices[$ia] > $choices[$ib]\n";
@@
-227,7
+236,8
@@
for (;;) {
print "# no defeats within the Schwartz set\n";
print "FINAL SCHWARTZ SET:\n";
print "# no defeats within the Schwartz set\n";
print "FINAL SCHWARTZ SET:\n";
-print $choices[$_] foreach (@{ $schwartz->nodes() });
+printf " %-5s %s\n", $choices[$_], $ch[$_]{Desc}
+ foreach ($schwartz->vertices());
print ".\n";
print ".\n";