X-Git-Url: http://git.shadowcat.co.uk/gitweb/gitweb.cgi?p=scpubgit%2Fstemmatology.git;a=blobdiff_plain;f=lib%2FText%2FTradition%2FAnalysis.pm;h=1a3e7b19a5e14ba8b86b40869d6145719bfc53c5;hp=fda51376077c9e67781e1c5e134c203704fd706a;hb=62a39b8f5d0ae86b26350664828069a2a44f5645;hpb=f2fec47dc44816775c844e8b50cef03b12b69dae diff --git a/lib/Text/Tradition/Analysis.pm b/lib/Text/Tradition/Analysis.pm index fda5137..1a3e7b1 100644 --- a/lib/Text/Tradition/Analysis.pm +++ b/lib/Text/Tradition/Analysis.pm @@ -10,6 +10,7 @@ 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 /; @@ -104,13 +105,28 @@ my %expected_genealogical = ( ); 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->{'variant_count'}, 58, "Got right total variant number" ); # TODO Make something meaningful of conflict count, maybe test other bits @@ -130,11 +146,11 @@ sub run_analysis { # 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.$c->ac_label ) if $_->is_layered } - $tradition->witnesses; push( @lacunose, _symmdiff( [ $stemma->witnesses ], \@tradition_wits ) ); # Find and mark 'common' ranks for exclusion, unless they were @@ -149,39 +165,68 @@ sub run_analysis { # Group the variants to send to the solver my @groups; + my @use_ranks; my %lacunae; + my $moved = {}; foreach my $rank ( @ranks ) { my $missing = [ @lacunose ]; - my $rankgroup = 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 ); + my( $rdgs, $grps ) = _useful_variant( $rankgroup, + $stemma->graph, $c->ac_label ); next unless @$rdgs; } + push( @use_ranks, $rank ); push( @groups, $rankgroup ); $lacunae{$rank} = $missing; } - $DB::single = 1; - # Parse the answer + # 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; @@ -193,7 +238,8 @@ sub run_analysis { 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 a hash $group_readings where $rdg is attested by the witnesses listed in $group_readings->{$rdg}. @@ -202,48 +248,185 @@ in $group_readings->{$rdg}. # 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 $aclabel = $c->ac_label; + my $table = $c->alignment_table; # Get the alignment table readings my %readings_at_rank; - my @gap_wits; - foreach my $tablewit ( @{$c->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'}; + # 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, $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, $aclabel ); + _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; - 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; + 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 ) @@ -265,69 +448,113 @@ The answer has the form sub solve_variants { my( $stemma, @groups ) = @_; - - # Make the json with stemma + groups - my $groupings = []; - foreach my $ghash ( @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 ( 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"; } - push( @$groupings, \@grouping ); + unless( exists $graph_problems->{"$graph"} ) { + $graph_problems->{"$graph"} = { 'object' => $graph, 'groups' => [] }; + } + push( @{$graph_problems->{"$graph"}->{'groups'}}, \@grouping ); } - ## Witness map is a HACK to get around limitations in node names from IDP - my $witness_map = {}; - my $json = encode_json( _safe_wit_strings( $stemma, $groupings, $witness_map ) ); - - # 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; - 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( $stemma, @$groupings ); - } - - # 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]}; - 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 ) { - my @pg = _prune_group( $cg, $stemma ); - push( @pruned_groups, \@pg ); + 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 ); + } + ## 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; } - $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; } } - my $input_group = $groups[$idx]; - foreach my $k ( sort keys %$input_group ) { - my $cg = shift @$calc_groups; - $input_group->{$k} = $cg; - } - my $vstruct = { - 'genealogical' => $result, - 'readings' => [], - }; - foreach my $k ( keys %$input_group ) { - push( @{$vstruct->{'readings'}}, - { 'readingid' => $k, 'group' => $input_group->{$k}} ); - } - push( @$variants, $vstruct ); } return { 'variants' => $variants, @@ -338,24 +565,28 @@ sub solve_variants { #### HACKERY to cope with IDP's limited idea of what a node name looks like ### sub _safe_wit_strings { - my( $stemma, $groupings, $witness_map ) = @_; + 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 ( $stemma->graph->vertices ) { + foreach my $n ( $graph->vertices ) { my $sn = _safe_witstr( $n ); - warn "Ambiguous stringification $sn for $n and " . $witness_map->{$sn} - if exists $witness_map->{$sn}; - $witness_map->{$sn} = $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, - $stemma->graph->get_vertex_attributes( $n ) ); + $graph->get_vertex_attributes( $n ) ); } - foreach my $e ( $stemma->graph->edges ) { + 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' => $stemma->collation, 'graph' => $safegraph ); + 'collation' => $c, 'graph' => $safegraph ); # Now convert the witness groupings to a safe representation. my $safe_groupings = []; @@ -377,7 +608,8 @@ sub _safe_wit_strings { # 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( ' ' ), 'groupings' => $safe_groupings }; + return { 'graph' => $safe_stemma->editable( { 'linesep' => ' ' } ), + 'groupings' => $safe_groupings }; } sub _safe_witstr { @@ -426,22 +658,52 @@ conflict, reading_parents, independent_occurrence, followed, not_followed, and f =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; } @@ -450,18 +712,16 @@ sub analyze_location { # 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. @@ -471,7 +731,7 @@ sub analyze_location { foreach my $wparent( @check ) { my $preading = $contig->{$wparent}; if( $preading ) { - $rdgparents{$preading} = 1; + $rdgparents->{$preading} = 1; } else { push( @next, $graph->predecessors( $wparent ) ); } @@ -479,7 +739,25 @@ sub analyze_location { @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. @@ -530,8 +808,7 @@ possibly with the addition of hypothetical readings. =cut sub perl_solver { - my( $stemma, @groups ) = @_; - my $graph = $stemma->graph; + my( $graph, @groups ) = @_; my @answer; foreach my $g ( @groups ) { push( @answer, _solve_variant_location( $graph, $g ) ); @@ -577,7 +854,7 @@ sub _solve_variant_location { # that implicitly later. foreach my $root ( @roots ) { # Prune the tree to get rid of extraneous hypotheticals. - $root = _prune_subtree( $part, $root, $contig ); + $root = _prune_subtree_old( $part, $root, $contig ); next unless $root; # Save this root for our group. push( @group_roots, $root ); @@ -710,24 +987,47 @@ sub _solve_variant_location { } sub _prune_group { - my( $group, $stemma ) = @_; - # Get these into a form prune_subtree will recognize. Make a "contighash" - my $hypohash = {}; - map { $hypohash->{$_} = 1 } @$group; - # ...with reference values for hypotheticals. - map { $hypohash->{$_} = [] } $stemma->hypotheticals; + my( $group, $stemma, $graph ) = @_; + my $lacunose = {}; + map { $lacunose->{$_} = 1 } $stemma->hypotheticals; + map { $lacunose->{$_} = 0 } @$group; # Make our subgraph - my $subgraph = $stemma->graph->copy; - map { $subgraph->delete_vertex( $_ ) unless exists $hypohash->{$_} } + my $subgraph = $graph->copy; + map { $subgraph->delete_vertex( $_ ) unless exists $lacunose->{$_} } $subgraph->vertices; # ...and find the root. - my( $root ) = $subgraph->predecessorless_vertices; # Now prune and return the remaining vertices. - _prune_subtree( $subgraph, $root, $hypohash ); + _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->{$_} ) } @@ -809,28 +1109,6 @@ sub wit_stringify { 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;