use Benchmark;
use Encode qw/ encode_utf8 /;
use Exporter 'import';
+use Graph;
use JSON qw/ encode_json decode_json /;
use LWP::UserAgent;
use Text::Tradition;
use Text::Tradition::Stemma;
+use TryCatch;
use vars qw/ @EXPORT_OK /;
@EXPORT_OK = qw/ run_analysis group_variants analyze_variant_location wit_stringify /;
=item * merge_types - Specify a list of relationship types, where related readings
should be treated as identical for the purposes of analysis.
+=item * exclude_type1 - Exclude those ranks whose groupings have only type-1 variants.
+
=back
=begin testing
);
my $data = run_analysis( $tradition );
+my $c = $tradition->collation;
foreach my $row ( @{$data->{'variants'}} ) {
# Account for rows that used to be "not useful"
unless( exists $expected_genealogical{$row->{'id'}} ) {
$expected_genealogical{$row->{'id'}} = 1;
}
- is( $row->{'genealogical'}, $expected_genealogical{$row->{'id'}},
+ my $gen_bool = $row->{'genealogical'} ? 1 : 0;
+ is( $gen_bool, $expected_genealogical{$row->{'id'}},
"Got correct genealogical flag for row " . $row->{'id'} );
+ # Check that we have the right row with the right groups
+ my $rank = $row->{'id'};
+ foreach my $rdghash ( @{$row->{'readings'}} ) {
+ # Skip 'readings' that aren't really
+ next unless $c->reading( $rdghash->{'readingid'} );
+ # Check the rank
+ is( $c->reading( $rdghash->{'readingid'} )->rank, $rank,
+ "Got correct reading rank" );
+ # Check the witnesses
+ my @realwits = sort $c->reading_witnesses( $rdghash->{'readingid'} );
+ my @sgrp = sort @{$rdghash->{'group'}};
+ is_deeply( \@sgrp, \@realwits, "Reading analyzed with correct groups" );
+ }
}
-is( $data->{'conflict_count'}, 34, "Got right conflict count" );
is( $data->{'variant_count'}, 58, "Got right total variant number" );
+# TODO Make something meaningful of conflict count, maybe test other bits
=end testing
my $c = $tradition->collation;
my $stemma_id = $opts{'stemma_id'} || 0;
- my @ranks = @{$opts{'ranks'}} if ref( $opts{'ranks'} ) eq 'ARRAY';
- my @collapse = @{$opts{'merge_types'}} if ref( $opts{'merge_types'} ) eq 'ARRAY';
+ my @ranks = ref( $opts{'ranks'} ) eq 'ARRAY' ? @{$opts{'ranks'}} : ();
+ my @collapse = ref( $opts{'merge_types'} ) eq 'ARRAY' ? @{$opts{'merge_types'}} : ();
# Get the stemma
my $stemma = $tradition->stemma( $stemma_id );
- # Figure out which witnesses we are working with
+
+ # Figure out which witnesses we are working with - that is, the ones that
+ # appear both in the stemma and in the tradition. All others are 'lacunose'
+ # for our purposes.
my @lacunose = $stemma->hypotheticals;
my @tradition_wits = map { $_->sigil } $tradition->witnesses;
- map { push( @tradition_wits, $_->sigil."_ac" ) if $_->is_layered }
- $tradition->witnesses;
push( @lacunose, _symmdiff( [ $stemma->witnesses ], \@tradition_wits ) );
# Find and mark 'common' ranks for exclusion, unless they were
# Group the variants to send to the solver
my @groups;
+ my @use_ranks;
my %lacunae;
+ my $moved = {};
foreach my $rank ( @ranks ) {
my $missing = [ @lacunose ];
- push( @groups, group_variants( $tradition, $rank, $missing, \@collapse ) );
+ my $rankgroup = group_variants( $tradition, $rank, $missing, $moved, \@collapse );
+ # Filter out any empty rankgroups
+ # (e.g. from the later rank for a transposition)
+ next unless keys %$rankgroup;
+ if( $opts{'exclude_type1'} ) {
+ # Check to see whether this is a "useful" group.
+ my( $rdgs, $grps ) = _useful_variant( $rankgroup,
+ $stemma->graph, $c->ac_label );
+ next unless @$rdgs;
+ }
+ push( @use_ranks, $rank );
+ push( @groups, $rankgroup );
$lacunae{$rank} = $missing;
}
-
- # Parse the answer
- my $answer = solve_variants( $stemma->editable( ' ' ), @groups );
+ # Run the solver
+ my $answer = solve_variants( $stemma, @groups );
# Do further analysis on the answer
my $conflict_count = 0;
- foreach my $idx ( 0 .. $#ranks ) {
+ my $aclabel = $c->ac_label;
+ foreach my $idx ( 0 .. $#use_ranks ) {
my $location = $answer->{'variants'}->[$idx];
# Add the rank back in
- $location->{'id'} = $ranks[$idx];
- # Add the lacunae back in
- $location->{'missing'} = $lacunae{$ranks[$idx]};
+ my $rank = $use_ranks[$idx];
+ $location->{'id'} = $rank;
+ # Note what our lacunae are
+ my %lmiss;
+ map { $lmiss{$_} = 1 } @{$lacunae{$use_ranks[$idx]}};
+ $location->{'missing'} = [ keys %lmiss ];
+
# Run the extra analysis we need.
- analyze_location( $tradition, $stemma->graph, $location );
- # Add the reading text back in
+ analyze_location( $tradition, $stemma, $location, \%lmiss );
+
+ my @layerwits;
+ # Do the final post-analysis tidying up of the data.
foreach my $rdghash ( @{$location->{'readings'}} ) {
$conflict_count++
if exists $rdghash->{'conflict'} && $rdghash->{'conflict'};
+ # Add the reading text back in, setting display value as needed
my $rdg = $c->reading( $rdghash->{'readingid'} );
- $rdghash->{'text'} = $rdg ? $rdg->text : $rdghash->{'readingid'};
+ if( $rdg ) {
+ $rdghash->{'text'} = $rdg->text .
+ ( $rdg->rank == $rank ? '' : ' [' . $rdg->rank . ']' );
+ }
+ # Remove lacunose witnesses from this reading's list now that the
+ # analysis is done
+ my @realgroup;
+ map { push( @realgroup, $_ ) unless $lmiss{$_} } @{$rdghash->{'group'}};
+ $rdghash->{'group'} = \@realgroup;
+ # Note any layered witnesses that appear in this group
+ foreach( @realgroup ) {
+ if( $_ =~ /^(.*)\Q$aclabel\E$/ ) {
+ push( @layerwits, $1 );
+ }
+ }
}
+ $location->{'layerwits'} = \@layerwits if @layerwits;
}
$answer->{'conflict_count'} = $conflict_count;
Groups the variants at the given $rank of the collation, treating any
relationships in @merge_relationship_types as equivalent. $lacunose should
be a reference to an array, to which the sigla of lacunose witnesses at this
-rank will be appended.
+rank will be appended; $transposed should be a reference to a hash, wherein
+the identities of transposed readings and their relatives will be stored.
-Returns two ordered lists $readings, $groups, where $readings->[$n] is attested
-by the witnesses listed in $groups->[$n].
+Returns a hash $group_readings where $rdg is attested by the witnesses listed
+in $group_readings->{$rdg}.
=cut
# Return group_readings, groups, lacunose
sub group_variants {
- my( $tradition, $rank, $lacunose, $collapse ) = @_;
+ my( $tradition, $rank, $lacunose, $transposed, $collapse ) = @_;
my $c = $tradition->collation;
my $aclabel = $c->ac_label;
+ my $table = $c->alignment_table;
# Get the alignment table readings
my %readings_at_rank;
- my @gap_wits;
- foreach my $tablewit ( @{$tradition->collation->alignment_table->{'alignment'}} ) {
+ my %is_lacunose; # lookup table for witnesses not in stemma
+ map { $is_lacunose{$_} = 1; $is_lacunose{$_.$aclabel} = 1 } @$lacunose;
+ my @check_for_gaps;
+ my %moved_wits;
+ my $has_transposition;
+ foreach my $tablewit ( @{$table->{'alignment'}} ) {
my $rdg = $tablewit->{'tokens'}->[$rank-1];
my $wit = $tablewit->{'witness'};
- $wit =~ s/^(.*)\Q$aclabel\E$/${1}_ac/;
+ # Exclude the witness if it is "lacunose" which if we got here
+ # means "not in the stemma".
+ next if $is_lacunose{$wit};
+ # Note if the witness is actually in a lacuna
if( $rdg && $rdg->{'t'}->is_lacuna ) {
- _add_to_witlist( $wit, $lacunose, '_ac' );
+ _add_to_witlist( $wit, $lacunose, $aclabel );
+ # Otherwise the witness either has a positive reading...
} elsif( $rdg ) {
- $readings_at_rank{$rdg->{'t'}->text} = $rdg->{'t'};
+ # If the reading has been counted elsewhere as a transposition, ignore it.
+ if( $transposed->{$rdg->{'t'}->id} ) {
+ # TODO Does this cope with three-way transpositions?
+ map { $moved_wits{$_} = 1 } @{$transposed->{$rdg->{'t'}->id}};
+ next;
+ }
+ # Otherwise, record it...
+ $readings_at_rank{$rdg->{'t'}->id} = $rdg->{'t'};
+ # ...and grab any transpositions, and their relations.
+ my @transp = grep { $_->rank != $rank } $rdg->{'t'}->related_readings();
+ foreach my $trdg ( @transp ) {
+ next if exists $readings_at_rank{$trdg->id};
+ $has_transposition = 1;
+ my @affected_wits = _table_witnesses(
+ $table, $trdg, \%is_lacunose, $aclabel );
+ next unless @affected_wits;
+ map { $moved_wits{$_} = 1 } @affected_wits;
+ $transposed->{$trdg->id} =
+ [ _table_witnesses( $table, $rdg->{'t'}, \%is_lacunose, $aclabel ) ];
+ $readings_at_rank{$trdg->id} = $trdg;
+ }
+ # ...or it is empty, ergo a gap.
} else {
- _add_to_witlist( $wit, \@gap_wits, '_ac' );
+ _add_to_witlist( $wit, \@check_for_gaps, $aclabel );
}
}
-
+ my @gap_wits;
+ map { _add_to_witlist( $_, \@gap_wits, $aclabel )
+ unless $moved_wits{$_} } @check_for_gaps;
# Group the readings, collapsing groups by relationship if needed
- my %grouped_readings;
- foreach my $rdg ( sort { $b->witnesses <=> $a->witnesses } values %readings_at_rank ) {
+ my $grouped_readings = {};
+ foreach my $rdg ( values %readings_at_rank ) {
# Skip readings that have been collapsed into others.
- next if exists $grouped_readings{$rdg->id} && !$grouped_readings{$rdg->id};
- my @wits = $rdg->witnesses;
- map { s/\Q$aclabel\E$/_ac/ } @wits;
- if( $collapse ) {
+ next if exists $grouped_readings->{$rdg->id}
+ && $grouped_readings->{$rdg->id} eq 'COLLAPSE';
+ # Get the witness list, including from readings collapsed into this one.
+ my @wits = _table_witnesses( $table, $rdg, \%is_lacunose, $aclabel );
+ if( $collapse && @$collapse ) {
my $filter = sub { my $r = $_[0]; grep { $_ eq $r->type } @$collapse; };
foreach my $other ( $rdg->related_readings( $filter ) ) {
- my @otherwits = $other->witnesses;
- map { s/\Q$aclabel\E$/_ac/ } @otherwits;
+ my @otherwits = _table_witnesses(
+ $table, $other, \%is_lacunose, $aclabel );
push( @wits, @otherwits );
- $grouped_readings{$other->id} = 0;
+ $grouped_readings->{$other->id} = 'COLLAPSE';
}
}
- $grouped_readings{$rdg->id} = \@wits;
+ $grouped_readings->{$rdg->id} = \@wits;
}
- $grouped_readings{'(omitted)'} = \@gap_wits if @gap_wits;
+ $grouped_readings->{'(omitted)'} = \@gap_wits if @gap_wits;
# Get rid of our collapsed readings
- map { delete $grouped_readings{$_} unless $grouped_readings{$_} }
- keys %grouped_readings
+ map { delete $grouped_readings->{$_} if $grouped_readings->{$_} eq 'COLLAPSE' }
+ keys %$grouped_readings
if $collapse;
+
+ # If something was transposed, check the groups for doubled-up readings
+ if( $has_transposition ) {
+ # print STDERR "Group for rank $rank:\n";
+ # map { print STDERR "\t$_: " . join( ' ' , @{$grouped_readings->{$_}} ) . "\n" }
+ # keys %$grouped_readings;
+ _check_transposed_consistency( $c, $rank, $transposed, $grouped_readings );
+ }
- return \%grouped_readings;
+ # Return the result
+ return $grouped_readings;
+}
+
+# Helper function to query the alignment table for all witnesses (a.c. included)
+# that have a given reading at its rank.
+sub _table_witnesses {
+ my( $table, $trdg, $lacunose, $aclabel ) = @_;
+ my $tableidx = $trdg->rank - 1;
+ my @has_reading;
+ foreach my $row ( @{$table->{'alignment'}} ) {
+ my $wit = $row->{'witness'};
+ next if $lacunose->{$wit};
+ my $rdg = $row->{'tokens'}->[$tableidx];
+ next unless exists $rdg->{'t'} && defined $rdg->{'t'};
+ _add_to_witlist( $wit, \@has_reading, $aclabel )
+ if $rdg->{'t'}->id eq $trdg->id;
+ }
+ return @has_reading;
+}
+
+# Helper function to ensure that X and X a.c. never appear in the same list.
+sub _add_to_witlist {
+ my( $wit, $list, $acstr ) = @_;
+ my %inlist;
+ my $idx = 0;
+ map { $inlist{$_} = $idx++ } @$list;
+ if( $wit =~ /^(.*)\Q$acstr\E$/ ) {
+ my $acwit = $1;
+ unless( exists $inlist{$acwit} ) {
+ push( @$list, $acwit.$acstr );
+ }
+ } else {
+ if( exists( $inlist{$wit.$acstr} ) ) {
+ # Replace the a.c. version with the main witness
+ my $i = $inlist{$wit.$acstr};
+ $list->[$i] = $wit;
+ } else {
+ push( @$list, $wit );
+ }
+ }
+}
+
+sub _check_transposed_consistency {
+ my( $c, $rank, $transposed, $groupings ) = @_;
+ my %seen_wits;
+ my %thisrank;
+ # Note which readings are actually at this rank, and which witnesses
+ # belong to which reading.
+ foreach my $rdg ( keys %$groupings ) {
+ my $rdgobj = $c->reading( $rdg );
+ # Count '(omitted)' as a reading at this rank
+ $thisrank{$rdg} = 1 if !$rdgobj || $rdgobj->rank == $rank;
+ map { push( @{$seen_wits{$_}}, $rdg ) } @{$groupings->{$rdg}};
+ }
+ # Our work is done if we have no witness belonging to more than one
+ # reading.
+ my @doubled = grep { scalar @{$seen_wits{$_}} > 1 } keys %seen_wits;
+ return unless @doubled;
+ # If we have a symmetric related transposition, drop the non-rank readings.
+ if( @doubled == scalar keys %seen_wits ) {
+ foreach my $rdg ( keys %$groupings ) {
+ if( !$thisrank{$rdg} ) {
+ my $groupstr = wit_stringify( $groupings->{$rdg} );
+ my ( $matched ) = grep { $groupstr eq wit_stringify( $groupings->{$_} ) }
+ keys %thisrank;
+ delete $groupings->{$rdg};
+ # If we found a group match, assume there is a symmetry happening.
+ # TODO think more about this
+ # print STDERR "*** Deleting symmetric reading $rdg\n";
+ unless( $matched ) {
+ delete $transposed->{$rdg};
+ warn "Found problem in evident symmetry with reading $rdg";
+ }
+ }
+ }
+ # Otherwise 'unhook' the transposed reading(s) that have duplicates.
+ } else {
+ foreach my $dup ( @doubled ) {
+ foreach my $rdg ( @{$seen_wits{$dup}} ) {
+ next if $thisrank{$rdg};
+ next unless exists $groupings->{$rdg};
+ # print STDERR "*** Deleting asymmetric doubled-up reading $rdg\n";
+ delete $groupings->{$rdg};
+ delete $transposed->{$rdg};
+ }
+ }
+ # and put any now-orphaned readings into an 'omitted' reading.
+ foreach my $wit ( keys %seen_wits ) {
+ unless( grep { exists $groupings->{$_} } @{$seen_wits{$wit}} ) {
+ $groupings->{'(omitted)'} = [] unless exists $groupings->{'(omitted)'};
+ _add_to_witlist( $wit, $groupings->{'(omitted)'}, $c->ac_label );
+ }
+ }
+ }
}
=head2 solve_variants( $graph, @groups )
=cut
sub solve_variants {
- my( $graph, @groups ) = @_;
-
- # Make the json with stemma + groups
- my $jsonstruct = { 'graph' => $graph, 'groupings' => [] };
- foreach my $ghash ( @groups ) {
+ my( $stemma, @groups ) = @_;
+ my $aclabel = $stemma->collation->ac_label;
+
+ # Filter the groups down to distinct groups, and work out what graph
+ # should be used in the calculation of each group. We want to send each
+ # distinct problem to the solver only once.
+ # We need a whole bunch of lookup tables for this.
+ my $index_groupkeys = {}; # Save the order of readings
+ my $group_indices = {}; # Save the indices that have a given grouping
+ my $graph_problems = {}; # Save the groupings for the given graph
+
+ foreach my $idx ( 0..$#groups ) {
+ my $ghash = $groups[$idx];
my @grouping;
- foreach my $k ( sort keys %$ghash ) {
- push( @grouping, $ghash->{$k} );
+ # Sort the groupings from big to little, and scan for a.c. witnesses
+ # that would need an extended graph.
+ my @acwits; # note which AC witnesses crop up at this rank
+ my @idxkeys = sort { scalar @{$ghash->{$b}} <=> scalar @{$ghash->{$a}} }
+ keys %$ghash;
+ foreach my $rdg ( @idxkeys ) {
+ my @sg = sort @{$ghash->{$rdg}};
+ push( @acwits, grep { $_ =~ /\Q$aclabel\E$/ } @sg );
+ push( @grouping, \@sg );
+ }
+ # Save the reading order
+ $index_groupkeys->{$idx} = \@idxkeys;
+
+ # Now associate the distinct group with this index
+ my $gstr = wit_stringify( \@grouping );
+ push( @{$group_indices->{$gstr}}, $idx );
+
+ # Finally, add the group to the list to be calculated for this graph.
+ map { s/\Q$aclabel\E$// } @acwits;
+ my $graph;
+ try {
+ $graph = $stemma->extend_graph( \@acwits );
+ } catch {
+ die "Unable to extend graph with @acwits";
+ }
+ unless( exists $graph_problems->{"$graph"} ) {
+ $graph_problems->{"$graph"} = { 'object' => $graph, 'groups' => [] };
}
- push( @{$jsonstruct->{'groupings'}}, \@grouping );
+ push( @{$graph_problems->{"$graph"}->{'groups'}}, \@grouping );
}
- my $json = encode_json( $jsonstruct );
-
- # Send it off and get the result
+
+ ## For each distinct graph, send its groups to the solver.
my $solver_url = 'http://byzantini.st/cgi-bin/graphcalc.cgi';
my $ua = LWP::UserAgent->new();
- my $resp = $ua->post( $solver_url, 'Content-Type' => 'application/json',
- 'Content' => $json );
-
- my $answer;
- if( $resp->is_success ) {
- $answer = decode_json( $resp->content );
- } else {
- # Fall back to the old method.
- warn "IDP solver returned " . $resp->status_line . " / " . $resp->content
- . "; falling back to perl method";
- $answer = perl_solver( $graph, @groups );
- }
-
- # Fold the result back into what we know about the groups.
- my $variants = [];
+ ## Witness map is a HACK to get around limitations in node names from IDP
+ my $witness_map = {};
+ ## Variables to store answers as they come back
+ my $variants = [ ( undef ) x ( scalar keys %$index_groupkeys ) ];
my $genealogical = 0;
- foreach my $idx ( 0 .. $#groups ) {
- my( $calc_groups, $result ) = @{$answer->[$idx]};
- $genealogical++ if $result;
- my $input_group = $groups[$idx];
- foreach my $k ( sort keys %$input_group ) {
- my $cg = shift @$calc_groups;
- $input_group->{$k} = $cg;
+ foreach my $graphkey ( keys %$graph_problems ) {
+ my $graph = $graph_problems->{$graphkey}->{'object'};
+ my $groupings = $graph_problems->{$graphkey}->{'groups'};
+ my $json = encode_json( _safe_wit_strings( $graph, $stemma->collation,
+ $groupings, $witness_map ) );
+ # Send it off and get the result
+ #print STDERR "Sending request: $json\n";
+ my $resp = $ua->post( $solver_url, 'Content-Type' => 'application/json',
+ 'Content' => $json );
+ my $answer;
+ my $used_idp;
+ if( $resp->is_success ) {
+ $answer = _desanitize_names( decode_json( $resp->content ), $witness_map );
+ $used_idp = 1;
+ } else {
+ # Fall back to the old method.
+ warn "IDP solver returned " . $resp->status_line . " / " . $resp->content
+ . "; falling back to perl method";
+ $answer = perl_solver( $graph, @$groupings );
}
- my $vstruct = {
- 'genealogical' => $result,
- 'readings' => [],
- };
- foreach my $k ( keys %$input_group ) {
- push( @{$vstruct->{'readings'}},
- { 'readingid' => $k, 'group' => $input_group->{$k}} );
+ ## The answer is the evaluated groupings, plus a boolean for whether
+ ## they were genealogical. Reconstruct our original groups.
+ foreach my $gidx ( 0 .. $#{$groupings} ) {
+ my( $calc_groups, $result ) = @{$answer->[$gidx]};
+ if( $result ) {
+ $genealogical++;
+ # Prune the calculated groups, in case the IDP solver failed to.
+ if( $used_idp ) {
+ my @pruned_groups;
+ foreach my $cg ( @$calc_groups ) {
+ # This is a little wasteful but the path of least
+ # resistance. Send both the stemma, which knows what
+ # its hypotheticals are, and the actual graph used.
+ my @pg = _prune_group( $cg, $stemma, $graph );
+ push( @pruned_groups, \@pg );
+ }
+ $calc_groups = \@pruned_groups;
+ }
+ }
+ # Retrieve the key for the original group that went to the solver
+ my $input_group = wit_stringify( $groupings->[$gidx] );
+ foreach my $oidx ( @{$group_indices->{$input_group}} ) {
+ my @readings = @{$index_groupkeys->{$oidx}};
+ my $vstruct = {
+ 'genealogical' => $result,
+ 'readings' => [],
+ };
+ foreach my $ridx ( 0 .. $#readings ) {
+ push( @{$vstruct->{'readings'}},
+ { 'readingid' => $readings[$ridx],
+ 'group' => $calc_groups->[$ridx] } );
+ }
+ $variants->[$oidx] = $vstruct;
+ }
}
- push( @$variants, $vstruct );
}
return { 'variants' => $variants,
'genealogical_count' => $genealogical };
}
+#### HACKERY to cope with IDP's limited idea of what a node name looks like ###
+
+sub _safe_wit_strings {
+ my( $graph, $c, $groupings, $witness_map ) = @_;
+ # Parse the graph we were given into a stemma.
+ my $safegraph = Graph->new();
+ # Convert the graph to a safe representation and store the conversion.
+ foreach my $n ( $graph->vertices ) {
+ my $sn = _safe_witstr( $n );
+ if( exists $witness_map->{$sn} ) {
+ warn "Ambiguous stringification $sn for $n and " . $witness_map->{$sn}
+ if $witness_map->{$sn} ne $n;
+ } else {
+ $witness_map->{$sn} = $n;
+ }
+ $safegraph->add_vertex( $sn );
+ $safegraph->set_vertex_attributes( $sn,
+ $graph->get_vertex_attributes( $n ) );
+ }
+ foreach my $e ( $graph->edges ) {
+ my @safe_e = ( _safe_witstr( $e->[0] ), _safe_witstr( $e->[1] ) );
+ $safegraph->add_edge( @safe_e );
+ }
+ my $safe_stemma = Text::Tradition::Stemma->new(
+ 'collation' => $c, 'graph' => $safegraph );
+
+ # Now convert the witness groupings to a safe representation.
+ my $safe_groupings = [];
+ foreach my $grouping ( @$groupings ) {
+ my $safe_grouping = [];
+ foreach my $group ( @$grouping ) {
+ my $safe_group = [];
+ foreach my $n ( @$group ) {
+ my $sn = _safe_witstr( $n );
+ warn "Ambiguous stringification $sn for $n and " . $witness_map->{$sn}
+ if exists $witness_map->{$sn} && $witness_map->{$sn} ne $n;
+ $witness_map->{$sn} = $n;
+ push( @$safe_group, $sn );
+ }
+ push( @$safe_grouping, $safe_group );
+ }
+ push( @$safe_groupings, $safe_grouping );
+ }
+
+ # Return it all in the struct we expect. We have stored the reductions
+ # in the $witness_map that we were passed.
+ return { 'graph' => $safe_stemma->editable( { 'linesep' => ' ' } ),
+ 'groupings' => $safe_groupings };
+}
+
+sub _safe_witstr {
+ my $witstr = shift;
+ $witstr =~ s/\s+/_/g;
+ $witstr =~ s/[^\w\d-]//g;
+ return $witstr;
+}
+
+sub _desanitize_names {
+ my( $jsonstruct, $witness_map ) = @_;
+ my $result = [];
+ foreach my $grouping ( @$jsonstruct ) {
+ my $real_grouping = [];
+ foreach my $element ( @$grouping ) {
+ if( ref( $element ) eq 'ARRAY' ) {
+ # it's the groupset.
+ my $real_groupset = [];
+ foreach my $group ( @$element ) {
+ my $real_group = [];
+ foreach my $n ( @$group ) {
+ my $rn = $witness_map->{$n};
+ push( @$real_group, $rn );
+ }
+ push( @$real_groupset, $real_group );
+ }
+ push( @$real_grouping, $real_groupset );
+ } else {
+ # It is the boolean, not actually a group.
+ push( @$real_grouping, $element );
+ }
+ }
+ push( @$result, $real_grouping );
+ }
+ return $result;
+}
+
+### END HACKERY ###
+
=head2 analyze_location ( $tradition, $graph, $location_hash )
Given the tradition, its stemma graph, and the solution from the graph solver,
=cut
sub analyze_location {
- my ( $tradition, $graph, $variant_row ) = @_;
+ my ( $tradition, $stemma, $variant_row, $lacunose ) = @_;
+ my $c = $tradition->collation;
# Make a hash of all known node memberships, and make the subgraphs.
my $contig = {};
my $reading_roots = {};
my $subgraph = {};
+ my $acstr = $c->ac_label;
+ my @acwits;
+ $DB::single = 1 if $variant_row->{id} == 87;
+ # Note which witnesses positively belong to which group
foreach my $rdghash ( @{$variant_row->{'readings'}} ) {
my $rid = $rdghash->{'readingid'};
- map { $contig->{$_} = $rid } @{$rdghash->{'group'}};
-
+ foreach my $wit ( @{$rdghash->{'group'}} ) {
+ $contig->{$wit} = $rid;
+ if( $wit =~ /^(.*)\Q$acstr\E$/ ) {
+ push( @acwits, $1 );
+ }
+ }
+ }
+
+ # Get the actual graph we should work with
+ my $graph;
+ try {
+ $graph = @acwits ? $stemma->extend_graph( \@acwits ) : $stemma->graph;
+ } catch {
+ die "Could not extend graph with a.c. witnesses @acwits";
+ }
+
+ # Now, armed with that knowledge, make a subgraph for each reading
+ # and note the root(s) of each subgraph.
+ foreach my $rdghash( @{$variant_row->{'readings'}} ) {
+ my $rid = $rdghash->{'readingid'};
+ my %rdgwits;
# Make the subgraph.
my $part = $graph->copy;
- my %these_vertices;
- map { $these_vertices{$_} = 1 } @{$rdghash->{'group'}};
- $part->delete_vertices( grep { !$these_vertices{$_} } $part->vertices );
+ my @todelete = grep { exists $contig->{$_} && $contig->{$_} ne $rid }
+ keys %$contig;
+ $part->delete_vertices( @todelete );
+ _prune_subtree( $part, $lacunose );
$subgraph->{$rid} = $part;
+ # Record the remaining lacunose nodes as part of this group, if
+ # we are dealing with a non-genealogical reading.
+ unless( $variant_row->{'genealogical'} ) {
+ map { $contig->{$_} = $rid } $part->vertices;
+ }
# Get the reading roots.
map { $reading_roots->{$_} = $rid } $part->predecessorless_vertices;
}
# non-followed/unknown values for each reading. Also figure out the
# reading's evident parent(s).
foreach my $rdghash ( @{$variant_row->{'readings'}} ) {
- # Group string key - TODO do we need this?
- my $gst = wit_stringify( $rdghash->{'group'} );
my $rid = $rdghash->{'readingid'};
# Get the subgraph
my $part = $subgraph->{$rid};
# Start figuring things out.
- my @roots = $part->predecessorless_vertices;
- $rdghash->{'independent_occurrence'} = scalar @roots;
+ my @roots = grep { $reading_roots->{$_} eq $rid } keys %$reading_roots;
+ $rdghash->{'independent_occurrence'} = \@roots;
$rdghash->{'followed'} = scalar( $part->vertices ) - scalar( @roots );
# Find the parent readings, if any, of this reading.
- my %rdgparents;
+ my $rdgparents = {};
foreach my $wit ( @roots ) {
# Look in the main stemma to find this witness's extant or known-reading
# immediate ancestor(s), and look up the reading that each ancestor olds.
foreach my $wparent( @check ) {
my $preading = $contig->{$wparent};
if( $preading ) {
- $rdgparents{$preading} = 1;
+ $rdgparents->{$preading} = 1;
} else {
push( @next, $graph->predecessors( $wparent ) );
}
@check = @next;
}
}
- $rdghash->{'reading_parents'} = [ keys %rdgparents ];
+ foreach my $p ( keys %$rdgparents ) {
+ # Resolve the relationship of the parent to the reading, and
+ # save it in our hash.
+ my $pobj = $c->reading( $p );
+ my $relation;
+ my $prep = $pobj ? $pobj->id . ' (' . $pobj->text . ')' : $p;
+ if( $pobj ) {
+ my $rel = $c->get_relationship( $p, $rdghash->{readingid} );
+ if( $rel ) {
+ $relation = { type => $rel->type };
+ if( $rel->has_annotation ) {
+ $relation->{'annotation'} = $rel->annotation;
+ }
+ }
+ }
+ $rdgparents->{$p} = { 'label' => $prep, 'relation' => $relation };
+ }
+
+ $rdghash->{'reading_parents'} = $rdgparents;
# Find the number of times this reading was altered, and the number of
# times we're not sure.
sub perl_solver {
my( $graph, @groups ) = @_;
-
- warn "Not implemented yet";
- return [];
+ my @answer;
+ foreach my $g ( @groups ) {
+ push( @answer, _solve_variant_location( $graph, $g ) );
+ }
+ return \@answer;
}
+sub _solve_variant_location {
+ my( $graph, $groups ) = @_;
# Now do the work.
-# my $contig = {};
-# my $subgraph = {};
-# my $is_conflicted;
-# my $conflict = {};
-# my %reading_roots;
-# my $variant_row = { 'id' => $rank, 'readings' => [] };
-# # Mark each ms as in its own group, first.
-# foreach my $g ( @$groups ) {
-# my $gst = wit_stringify( $g );
-# map { $contig->{$_} = $gst } @$g;
-# }
-# # Now for each unmarked node in the graph, initialize an array
-# # for possible group memberships. We will use this later to
-# # resolve potential conflicts.
-# map { $contig->{$_} = [] unless $contig->{$_} } $graph->vertices;
-# foreach my $g ( sort { scalar @$b <=> scalar @$a } @$groups ) {
-# my $gst = wit_stringify( $g ); # This is the group name
-# # Copy the graph, and delete all non-members from the new graph.
-# my $part = $graph->copy;
-# my @group_roots;
-# $part->delete_vertices(
-# grep { !ref( $contig->{$_} ) && $contig->{$_} ne $gst } $graph->vertices );
-#
-# # Now look to see if our group is connected.
-# if( $undirected ) { # For use with distance trees etc.
-# # Find all vertices reachable from the first (arbitrary) group
-# # member. If we are genealogical this should include them all.
-# my $reachable = {};
-# map { $reachable->{$_} = 1 } $part->all_reachable( $g->[0] );
-# # TODO This is a terrible way to do distance trees, since all
-# # non-leaf nodes are included in every graph part now. We may
-# # have to go back to SPDP.
-# } else {
-# if( @$g > 1 ) {
-# # We have to take directionality into account.
-# # How many root nodes do we have?
-# my @roots = grep { ref( $contig->{$_} ) || $contig->{$_} eq $gst }
-# $part->predecessorless_vertices;
-# # Assuming that @$g > 1, find the first root node that has at
-# # least one successor belonging to our group. If this reading
-# # is genealogical, there should be only one, but we will check
-# # that implicitly later.
-# foreach my $root ( @roots ) {
-# # Prune the tree to get rid of extraneous hypotheticals.
-# $root = _prune_subtree( $part, $root, $contig );
-# next unless $root;
-# # Save this root for our group.
-# push( @group_roots, $root );
-# # Get all the successor nodes of our root.
-# }
-# } else {
-# # Dispense with the trivial case of one reading.
-# my $wit = pop @$g;
-# @group_roots = ( $wit );
-# foreach my $v ( $part->vertices ) {
-# $part->delete_vertex( $v ) unless $v eq $wit;
-# }
-# }
-# }
-#
-# map { $reading_roots{$_} = 1 } @group_roots;
-# if( @group_roots > 1 ) {
-# $conflict->{$group_readings->{$gst}} = 1;
-# $is_conflicted = 1;
-# }
-# # Paint the 'hypotheticals' with our group.
-# foreach my $wit ( $part->vertices ) {
-# if( ref( $contig->{$wit} ) ) {
-# push( @{$contig->{$wit}}, $gst );
-# } elsif( $contig->{$wit} ne $gst ) {
-# warn "How did we get here?";
-# }
-# }
-#
-#
-# # Start to write the reading, and save the group subgraph.
-# my $reading = { 'readingid' => $group_readings->{$gst},
-# 'missing' => wit_stringify( \@lacunose ),
-# 'group' => $gst }; # This will change if we find no conflict
-# # Save the relevant subgraph.
-# $subgraph->{$gst} = $part;
-# push( @{$variant_row->{'readings'}}, $reading );
-# }
-#
-# # For each of our hypothetical readings, flatten its 'contig' array if
-# # the array contains zero or one group. If we have any unflattened arrays,
-# # we may need to run the resolution process. If the reading is already known
-# # to have a conflict, flatten the 'contig' array to nothing; we won't resolve
-# # it.
-# my @resolve;
-# foreach my $wit ( keys %$contig ) {
-# next unless ref( $contig->{$wit} );
-# if( @{$contig->{$wit}} > 1 ) {
-# if( $is_conflicted ) {
-# $contig->{$wit} = ''; # We aren't going to decide.
-# } else {
-# push( @resolve, $wit );
-# }
-# } else {
-# my $gst = pop @{$contig->{$wit}};
-# $contig->{$wit} = $gst || '';
-# }
-# }
-#
-# if( @resolve ) {
-# my $still_contig = {};
-# foreach my $h ( @resolve ) {
-# # For each of the hypothetical readings with more than one possibility,
-# # try deleting it from each of its member subgraphs in turn, and see
-# # if that breaks the contiguous grouping.
-# # TODO This can still break in a corner case where group A can use
-# # either vertex 1 or 2, and group B can use either vertex 2 or 1.
-# # Revisit this if necessary; it could get brute-force nasty.
-# foreach my $gst ( @{$contig->{$h}} ) {
-# my $gpart = $subgraph->{$gst}->copy();
-# # If we have come this far, there is only one root and everything
-# # is reachable from it.
-# my( $root ) = $gpart->predecessorless_vertices;
-# my $reachable = {};
-# map { $reachable->{$_} = 1 } $gpart->vertices;
-#
-# # Try deleting the hypothetical node.
-# $gpart->delete_vertex( $h );
-# if( $h eq $root ) {
-# # See if we still have a single root.
-# my @roots = $gpart->predecessorless_vertices;
-# warn "This shouldn't have happened" unless @roots;
-# if( @roots > 1 ) {
-# # $h is needed by this group.
-# if( exists( $still_contig->{$h} ) ) {
-# # Conflict!
-# $conflict->{$group_readings->{$gst}} = 1;
-# $still_contig->{$h} = '';
-# } else {
-# $still_contig->{$h} = $gst;
-# }
-# }
-# } else {
-# # $h is somewhere in the middle. See if everything
-# # else can still be reached from the root.
-# my %still_reachable = ( $root => 1 );
-# map { $still_reachable{$_} = 1 }
-# $gpart->all_successors( $root );
-# foreach my $v ( keys %$reachable ) {
-# next if $v eq $h;
-# if( !$still_reachable{$v}
-# && ( $contig->{$v} eq $gst
-# || ( exists $still_contig->{$v}
-# && $still_contig->{$v} eq $gst ) ) ) {
-# # We need $h.
-# if( exists $still_contig->{$h} ) {
-# # Conflict!
-# $conflict->{$group_readings->{$gst}} = 1;
-# $still_contig->{$h} = '';
-# } else {
-# $still_contig->{$h} = $gst;
-# }
-# last;
-# } # else we don't need $h in this group.
-# } # end foreach $v
-# } # endif $h eq $root
-# } # end foreach $gst
-# } # end foreach $h
-#
-# # Now we have some hypothetical vertices in $still_contig that are the
-# # "real" group memberships. Replace these in $contig.
-# foreach my $v ( keys %$contig ) {
-# next unless ref $contig->{$v};
-# $contig->{$v} = $still_contig->{$v};
-# }
-# } # end if @resolve
-#
-#
-# $variant_row->{'genealogical'} = !( keys %$conflict );
-# return $variant_row;
-# }
+ my $contig = {};
+ my $subgraph = {};
+ my $is_conflicted;
+ my $conflict = {};
+
+ # Mark each ms as in its own group, first.
+ foreach my $g ( @$groups ) {
+ my $gst = wit_stringify( $g );
+ map { $contig->{$_} = $gst } @$g;
+ }
+
+ # Now for each unmarked node in the graph, initialize an array
+ # for possible group memberships. We will use this later to
+ # resolve potential conflicts.
+ map { $contig->{$_} = [] unless $contig->{$_} } $graph->vertices;
+ foreach my $g ( sort { scalar @$b <=> scalar @$a } @$groups ) {
+ my $gst = wit_stringify( $g ); # This is the group name
+ # Copy the graph, and delete all non-members from the new graph.
+ my $part = $graph->copy;
+ my @group_roots;
+ $part->delete_vertices(
+ grep { !ref( $contig->{$_} ) && $contig->{$_} ne $gst } $graph->vertices );
+
+ # Now look to see if our group is connected.
+ if( @$g > 1 ) {
+ # We have to take directionality into account.
+ # How many root nodes do we have?
+ my @roots = grep { ref( $contig->{$_} ) || $contig->{$_} eq $gst }
+ $part->predecessorless_vertices;
+ # Assuming that @$g > 1, find the first root node that has at
+ # least one successor belonging to our group. If this reading
+ # is genealogical, there should be only one, but we will check
+ # that implicitly later.
+ foreach my $root ( @roots ) {
+ # Prune the tree to get rid of extraneous hypotheticals.
+ $root = _prune_subtree_old( $part, $root, $contig );
+ next unless $root;
+ # Save this root for our group.
+ push( @group_roots, $root );
+ # Get all the successor nodes of our root.
+ }
+ } else {
+ # Dispense with the trivial case of one reading.
+ my $wit = $g->[0];
+ @group_roots = ( $wit );
+ foreach my $v ( $part->vertices ) {
+ $part->delete_vertex( $v ) unless $v eq $wit;
+ }
+ }
+
+ if( @group_roots > 1 ) {
+ $conflict->{$gst} = 1;
+ $is_conflicted = 1;
+ }
+ # Paint the 'hypotheticals' with our group.
+ foreach my $wit ( $part->vertices ) {
+ if( ref( $contig->{$wit} ) ) {
+ push( @{$contig->{$wit}}, $gst );
+ } elsif( $contig->{$wit} ne $gst ) {
+ warn "How did we get here?";
+ }
+ }
+
+
+ # Save the relevant subgraph.
+ $subgraph->{$gst} = $part;
+ }
+
+ # For each of our hypothetical readings, flatten its 'contig' array if
+ # the array contains zero or one group. If we have any unflattened arrays,
+ # we may need to run the resolution process. If the reading is already known
+ # to have a conflict, flatten the 'contig' array to nothing; we won't resolve
+ # it.
+ my @resolve;
+ foreach my $wit ( keys %$contig ) {
+ next unless ref( $contig->{$wit} );
+ if( @{$contig->{$wit}} > 1 ) {
+ if( $is_conflicted ) {
+ $contig->{$wit} = ''; # We aren't going to decide.
+ } else {
+ push( @resolve, $wit );
+ }
+ } else {
+ my $gst = pop @{$contig->{$wit}};
+ $contig->{$wit} = $gst || '';
+ }
+ }
+
+ if( @resolve ) {
+ my $still_contig = {};
+ foreach my $h ( @resolve ) {
+ # For each of the hypothetical readings with more than one possibility,
+ # try deleting it from each of its member subgraphs in turn, and see
+ # if that breaks the contiguous grouping.
+ # TODO This can still break in a corner case where group A can use
+ # either vertex 1 or 2, and group B can use either vertex 2 or 1.
+ # Revisit this if necessary; it could get brute-force nasty.
+ foreach my $gst ( @{$contig->{$h}} ) {
+ my $gpart = $subgraph->{$gst}->copy();
+ # If we have come this far, there is only one root and everything
+ # is reachable from it.
+ my( $root ) = $gpart->predecessorless_vertices;
+ my $reachable = {};
+ map { $reachable->{$_} = 1 } $gpart->vertices;
+
+ # Try deleting the hypothetical node.
+ $gpart->delete_vertex( $h );
+ if( $h eq $root ) {
+ # See if we still have a single root.
+ my @roots = $gpart->predecessorless_vertices;
+ warn "This shouldn't have happened" unless @roots;
+ if( @roots > 1 ) {
+ # $h is needed by this group.
+ if( exists( $still_contig->{$h} ) ) {
+ # Conflict!
+ $conflict->{$gst} = 1;
+ $still_contig->{$h} = '';
+ } else {
+ $still_contig->{$h} = $gst;
+ }
+ }
+ } else {
+ # $h is somewhere in the middle. See if everything
+ # else can still be reached from the root.
+ my %still_reachable = ( $root => 1 );
+ map { $still_reachable{$_} = 1 }
+ $gpart->all_successors( $root );
+ foreach my $v ( keys %$reachable ) {
+ next if $v eq $h;
+ if( !$still_reachable{$v}
+ && ( $contig->{$v} eq $gst
+ || ( exists $still_contig->{$v}
+ && $still_contig->{$v} eq $gst ) ) ) {
+ # We need $h.
+ if( exists $still_contig->{$h} ) {
+ # Conflict!
+ $conflict->{$gst} = 1;
+ $still_contig->{$h} = '';
+ } else {
+ $still_contig->{$h} = $gst;
+ }
+ last;
+ } # else we don't need $h in this group.
+ } # end foreach $v
+ } # endif $h eq $root
+ } # end foreach $gst
+ } # end foreach $h
+
+ # Now we have some hypothetical vertices in $still_contig that are the
+ # "real" group memberships. Replace these in $contig.
+ foreach my $v ( keys %$contig ) {
+ next unless ref $contig->{$v};
+ $contig->{$v} = $still_contig->{$v};
+ }
+ } # end if @resolve
+
+ my $is_genealogical = keys %$conflict ? JSON::false : JSON::true;
+ my $variant_row = [ [], $is_genealogical ];
+ # Fill in the groupings from $contig.
+ foreach my $g ( @$groups ) {
+ my $gst = wit_stringify( $g );
+ my @realgroup = grep { $contig->{$_} eq $gst } keys %$contig;
+ push( @{$variant_row->[0]}, \@realgroup );
+ }
+ return $variant_row;
+}
+
+sub _prune_group {
+ my( $group, $stemma, $graph ) = @_;
+ my $lacunose = {};
+ map { $lacunose->{$_} = 1 } $stemma->hypotheticals;
+ map { $lacunose->{$_} = 0 } @$group;
+ # Make our subgraph
+ my $subgraph = $graph->copy;
+ map { $subgraph->delete_vertex( $_ ) unless exists $lacunose->{$_} }
+ $subgraph->vertices;
+ # ...and find the root.
+ # Now prune and return the remaining vertices.
+ _prune_subtree( $subgraph, $lacunose );
+ return $subgraph->vertices;
+}
sub _prune_subtree {
+ my( $tree, $lacunose ) = @_;
+
+ # Delete lacunose witnesses that have no successors
+ my @orphan_hypotheticals;
+ my $ctr = 0;
+ do {
+ die "Infinite loop on leaves" if $ctr > 100;
+ @orphan_hypotheticals = grep { $lacunose->{$_} }
+ $tree->successorless_vertices;
+ $tree->delete_vertices( @orphan_hypotheticals );
+ $ctr++;
+ } while( @orphan_hypotheticals );
+
+ # Delete lacunose roots that have a single successor
+ my @redundant_root;
+ $ctr = 0;
+ do {
+ die "Infinite loop on roots" if $ctr > 100;
+ @redundant_root = grep { $lacunose->{$_} && $tree->successors( $_ ) == 1 }
+ $tree->predecessorless_vertices;
+ $tree->delete_vertices( @redundant_root );
+ $ctr++;
+ } while( @redundant_root );
+}
+
+sub _prune_subtree_old {
my( $tree, $root, $contighash ) = @_;
# First, delete hypothetical leaves / orphans until there are none left.
my @orphan_hypotheticals = grep { ref( $contighash->{$_} ) }
return join( ' / ', @gst );
}
-# Helper function to ensure that X and X a.c. never appear in the same list.
-sub _add_to_witlist {
- my( $wit, $list, $acstr ) = @_;
- my %inlist;
- my $idx = 0;
- map { $inlist{$_} = $idx++ } @$list;
- if( $wit =~ /^(.*)\Q$acstr\E$/ ) {
- my $acwit = $1;
- unless( exists $inlist{$acwit} ) {
- push( @$list, $acwit.$acstr );
- }
- } else {
- if( exists( $inlist{$wit.$acstr} ) ) {
- # Replace the a.c. version with the main witness
- my $i = $inlist{$wit.$acstr};
- $list->[$i] = $wit;
- } else {
- push( @$list, $wit );
- }
- }
-}
-
sub _symmdiff {
my( $lista, $listb ) = @_;
my %union;
projects / scpubgit/stemmatology.git / blobdiff