# 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
my $location = $answer->{'variants'}->[$idx];
# Add the rank back in
$location->{'id'} = $use_ranks[$idx];
- $DB::single = 1 if $use_ranks[$idx] == 87;
# Note what our lacunae are
my %lmiss;
map { $lmiss{$_} = 1 } @{$lacunae{$use_ranks[$idx]}};
sub group_variants {
my( $tradition, $rank, $lacunose, $collapse ) = @_;
my $c = $tradition->collation;
- my $aclabel = $c->ac_label;
- my %seen_acwits;
- map { $seen_acwits{$_->sigil.$aclabel} = 0 if $_->is_layered } $tradition->witnesses;
+ my $aclabel = $c->ac_label;
+
# Get the alignment table readings
my %readings_at_rank;
my %is_lacunose; # lookup table for $lacunose
# means "not in the stemma".
next if $is_lacunose{$wit};
if( $rdg && $rdg->{'t'}->is_lacuna ) {
- push( @$lacunose, $wit );
+ _add_to_witlist( $wit, $lacunose, $aclabel );
} elsif( $rdg ) {
$readings_at_rank{$rdg->{'t'}->text} = $rdg->{'t'};
} else {
- $seen_acwits{$wit} = 1 if exists $seen_acwits{$wit};
- push( @gap_wits, $wit );
+ _add_to_witlist( $wit, \@gap_wits, $aclabel );
}
}
$grouped_readings{$other->id} = 0;
}
}
- # Filter the group to those witnesses in the stemma, and note any
- # a.c. witnesses explicitly returned.
+ # Filter the group to those witnesses in the stemma
my @use_wits;
foreach my $wit ( @wits ) {
next if $is_lacunose{$wit};
push( @use_wits, $wit );
- $seen_acwits{$wit} = 1 if exists $seen_acwits{$wit};
}
$grouped_readings{$rdg->id} = \@use_wits;
}
map { delete $grouped_readings{$_} unless $grouped_readings{$_} }
keys %grouped_readings
if $collapse;
- # Any unseen a.c. witnesses should be made lacunose
- map { push( @$lacunose, $_ ) unless $seen_acwits{$_} } keys %seen_acwits;
# Return the result
return \%grouped_readings;
}
+# 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 );
+ }
+ }
+}
+
=head2 solve_variants( $graph, @groups )
Sends the set of groups to the external graph solver service and returns
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 ( 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 = $stemma->extend_graph( \@acwits );
+ unless( exists $graph_problems->{"$graph"} ) {
+ $graph_problems->{"$graph"} = { 'object' => $graph, 'groups' => [] };
}
- push( @$groupings, \@grouping );
+ 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.
+ $DB::single = 1;
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
+ 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 ( sort { @{$input_group->{$b}} <=> @{$input_group->{$a}} }
- keys %$input_group ) {
- push( @{$vstruct->{'readings'}},
- { 'readingid' => $k, 'group' => $input_group->{$k}} );
- }
- push( @$variants, $vstruct );
}
return { 'variants' => $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 = [];
# 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 {
=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 ) );
}
sub _prune_group {
- my( $group, $stemma ) = @_;
+ my( $group, $stemma, $graph ) = @_;
# 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;
# Make our subgraph
- my $subgraph = $stemma->graph->copy;
+ my $subgraph = $graph->copy;
map { $subgraph->delete_vertex( $_ ) unless exists $hypohash->{$_} }
$subgraph->vertices;
# ...and find the root.
=head1 DESCRIPTION
Text::Tradition is a library for representation and analysis of collated
-texts, particularly medieval ones. The Collation is the central feature of
-a Tradition, where the text, its sequence of readings, and its relationships
-between readings are actually kept.
+texts, particularly medieval ones. The Stemma is a representation of the
+copying relationships between the witnesses in a Tradition, modelled with
+a connected rooted directed acyclic graph (CRDAG).
=head1 DOT SYNTAX
-The easiest way to define a stemma (which is a directed acyclic graph, denoting
-the scholar's hypothesis concerning which text(s) were copied from which other(s))
-is to use a special form of the 'dot' syntax of GraphViz.
+The easiest way to define a stemma is to use a special form of the 'dot'
+syntax of GraphViz.
Each stemma opens with the line
sub as_dot {
my( $self, $opts ) = @_;
+ ## See if we are including any a.c. witnesses in this graph.
+ my $graph = $self->graph;
+ if( exists $opts->{'layerwits'} ) {
+ $graph = $self->extend_graph( $opts->{'layerwits'} );
+ }
+
# Get default and specified options
my %graphopts = (
# 'ratio' => 1,
if $opts->{'node'};
@edgeopts{ keys %{$opts->{'edge'}} } = values %{$opts->{'edge'}}
if $opts->{'edge'};
-
+
my @dotlines;
push( @dotlines, 'digraph stemma {' );
## Print out the global attributes
push( @dotlines, _make_dotline( 'node', %nodeopts ) ) if keys %nodeopts;
# Add each of the nodes.
- foreach my $n ( $self->graph->vertices ) {
- if( $self->graph->has_vertex_attribute( $n, 'label' ) ) {
- my $ltext = $self->graph->get_vertex_attribute( $n, 'label' );
+ foreach my $n ( $graph->vertices ) {
+ if( $graph->has_vertex_attribute( $n, 'label' ) ) {
+ my $ltext = $graph->get_vertex_attribute( $n, 'label' );
push( @dotlines, _make_dotline( $n, 'label' => $ltext ) );
} else {
# Use the default display settings.
}
}
# Add each of our edges.
- foreach my $e ( $self->graph->edges ) {
+ foreach my $e ( $graph->edges ) {
my( $from, $to ) = map { _dotquote( $_ ) } @$e;
push( @dotlines, " $from -> $to;" );
}
return join( "\n", @dotlines );
}
-=head2 editable( $linesep )
+=head2 editable( $opts )
Returns a version of the graph rendered in our definition format. The
-$linesep argument defaults to newline; set it to the empty string or to
-a space if the result is to be sent via JSON.
+output separates statements with a newline; set $opts->{'linesep'} to the
+empty string or to a space if the result is to be sent via JSON.
+
+Any layer witnesses to be included should be passed via $opts->{'layerwits'}.
=cut
sub editable {
- my $self = shift;
- my $join = shift || "\n";
+ my( $self, $opts ) = @_;
+
+ ## See if we are including any a.c. witnesses in this graph.
+ my $graph = $self->graph;
+ if( exists $opts->{'layerwits'} ) {
+ $graph = $self->extend_graph( $opts->{'layerwits'} );
+ }
+
+ # Create the graph
+ my $join = ( $opts && exists $opts->{'linesep'} ) ? $opts->{'linesep'} : "\n";
my @dotlines;
push( @dotlines, 'digraph stemma {' );
my @real; # A cheap sort
return $a->[0].$a->[1] cmp $b->[0].$b->[1];
}
+=head2 extend_graph( $layered_witnesses )
+
+Returns a graph which is the original stemma with witness layers added for the
+list in @$layered_witnesses. A layered (a.c.) witness is added as a parent
+of its main version, and additionally shares all other parents and children with
+that version.
+
+=cut
+
+sub extend_graph {
+ my( $self, $layerwits ) = @_;
+ # For each 'layered' witness in the layerwits array, add it to the graph
+ # as an ancestor of the 'main' witness, and otherwise with the same parent/
+ # child links as its main analogue.
+ # TOOD Handle case where B is copied from A but corrected from C
+
+ # Iterate through, adding a.c. witnesses
+ my $actag = $self->collation->ac_label;
+ my $graph = $self->graph->copy;
+ foreach my $lw ( @$layerwits ) {
+ # Add the layered witness and set it with the same attributes as
+ # its 'main' analogue
+ my $lwac = $lw . $self->collation->ac_label;
+ $graph->add_vertex( $lwac );
+ $graph->set_vertex_attributes( $lwac,
+ $graph->get_vertex_attributes( $lw ) );
+
+ # Set it as ancestor to the main witness
+ $graph->add_edge( $lwac, $lw );
+
+ # Give it the same ancestors and descendants as the main witness has,
+ # bearing in mind that those ancestors and descendants might also just
+ # have had a layered witness defined.
+ foreach my $v ( $graph->predecessors( $lw ) ) {
+ next if $v eq $lwac; # Don't add a loop
+ $graph->add_edge( $v, $lwac );
+ $graph->add_edge( $v.$self->collation->ac_label, $lwac )
+ if $graph->has_vertex( $v.$self->collation->ac_label );
+ }
+ foreach my $v ( $graph->successors( $lw ) ) {
+ next if $v eq $lwac; # but this shouldn't occur
+ $graph->add_edge( $lwac, $v );
+ $graph->add_edge( $lwac, $v.$self->collation->ac_label )
+ if $graph->has_vertex( $v.$self->collation->ac_label );
+ }
+ }
+ return $graph;
+}
+
=head2 as_svg
Returns an SVG representation of the graph, calling as_dot first.
projects / scpubgit/stemmatology.git / commitdiff