is( ref( $s ), 'Text::Tradition::Stemma', "Added stemma to tradition" );
my %expected_genealogical = (
- 1 => '',
+ 1 => 0,
2 => 1,
- 3 => '',
- 5 => '',
- 7 => '',
- 8 => '',
- 10 => '',
+ 3 => 0,
+ 5 => 0,
+ 7 => 0,
+ 8 => 0,
+ 10 => 0,
13 => 1,
- 33 => '',
- 34 => '',
- 37 => '',
- 60 => '',
+ 33 => 0,
+ 34 => 0,
+ 37 => 0,
+ 60 => 0,
81 => 1,
- 84 => '',
- 87 => '',
- 101 => '',
- 102 => '',
+ 84 => 0,
+ 87 => 0,
+ 101 => 0,
+ 102 => 0,
122 => 1,
- 157 => '',
+ 157 => 0,
166 => 1,
169 => 1,
- 200 => 1,
+ 200 => 0,
216 => 1,
217 => 1,
219 => 1,
my $data = run_analysis( $tradition );
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'}},
"Got correct genealogical flag for row " . $row->{'id'} );
}
-is( $data->{'conflict_count'}, 16, "Got right conflict count" );
-is( $data->{'variant_count'}, 28, "Got right total variant number" );
+is( $data->{'conflict_count'}, 34, "Got right conflict count" );
+is( $data->{'variant_count'}, 58, "Got right total variant number" );
=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 );
# explicitly specified.
unless( @ranks ) {
my %common_rank;
- foreach my $rdg ( $tradition->collation->common_readings ) {
+ foreach my $rdg ( $c->common_readings ) {
$common_rank{$rdg->rank} = 1;
}
@ranks = grep { !$common_rank{$_} } ( 1 .. $c->end->rank-1 );
# Group the variants to send to the solver
my @groups;
+ my %lacunae;
foreach my $rank ( @ranks ) {
- push( @groups, group_variants( $tradition, $rank, \@lacunose, \@collapse ) );
+ my $missing = [ @lacunose ];
+ push( @groups, group_variants( $tradition, $rank, $missing, \@collapse ) );
+ $lacunae{$rank} = $missing;
}
# Parse the answer
- my $answer = solve_variants( $stemma->editable( ' ' ), @groups );
- $DB::single = 1;
+ my $answer = solve_variants( $stemma, @groups );
# Do further analysis on the answer
+ my $conflict_count = 0;
foreach my $idx ( 0 .. $#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]};
# Run the extra analysis we need.
analyze_location( $tradition, $stemma->graph, $location );
+ # Add the reading text back in
+ foreach my $rdghash ( @{$location->{'readings'}} ) {
+ $conflict_count++
+ if exists $rdghash->{'conflict'} && $rdghash->{'conflict'};
+ my $rdg = $c->reading( $rdghash->{'readingid'} );
+ $rdghash->{'text'} = $rdg ? $rdg->text : $rdghash->{'readingid'};
+ }
}
+ $answer->{'conflict_count'} = $conflict_count;
return $answer;
}
# Get the alignment table readings
my %readings_at_rank;
my @gap_wits;
- foreach my $tablewit ( @{$tradition->collation->alignment_table->{'alignment'}} ) {
+ foreach my $tablewit ( @{$c->alignment_table->{'alignment'}} ) {
my $rdg = $tablewit->{'tokens'}->[$rank-1];
my $wit = $tablewit->{'witness'};
$wit =~ s/^(.*)\Q$aclabel\E$/${1}_ac/;
=cut
sub solve_variants {
- my( $graph, @groups ) = @_;
+ my( $stemma, @groups ) = @_;
# Make the json with stemma + groups
- my $jsonstruct = { 'graph' => $graph, 'groupings' => [] };
+ my $jsonstruct = { 'graph' => $stemma->editable( ' ' ), 'groupings' => [] };
foreach my $ghash ( @groups ) {
my @grouping;
foreach my $k ( sort keys %$ghash ) {
# 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 );
+ $answer = perl_solver( $stemma, @{$jsonstruct->{'groupings'}} );
}
# Fold the result back into what we know about the groups.
$rdghash->{'followed'} = scalar( $part->vertices ) - scalar( @roots );
# Find the parent readings, if any, of this reading.
my %rdgparents;
- $DB::single = 1;
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.
=cut
sub perl_solver {
- my( $graph, @groups ) = @_;
-
- warn "Not implemented yet";
- return [];
+ my( $stemma, @groups ) = @_;
+ my $graph = $stemma->graph;
+ 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( $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_subtree {
my( $tree, $root, $contighash ) = @_;
projects / scpubgit/stemmatology.git / blobdiff