use Encode qw( decode_utf8 );
use File::Temp;
+use File::Which;
use Graph;
use IPC::Run qw( run binary );
use Text::CSV_XS;
handles => {
relationships => 'relationships',
related_readings => 'related_readings',
+ get_relationship => 'get_relationship',
+ del_relationship => 'del_relationship',
},
writer => '_set_relations',
);
writer => '_set_end',
weak_ref => 1,
);
+
+has 'cached_svg' => (
+ is => 'rw',
+ isa => 'Str',
+ predicate => 'has_cached_svg',
+ clearer => 'wipe_svg',
+ );
+
+has 'cached_table' => (
+ is => 'rw',
+ isa => 'HashRef',
+ predicate => 'has_cached_table',
+ clearer => 'wipe_table',
+ );
+
+has '_graphcalc_done' => (
+ is => 'rw',
+ isa => 'Bool',
+ default => undef,
+ );
=head1 NAME
if( $self->reading( $reading->id ) ) {
throw( "Collation already has a reading with id " . $reading->id );
}
+ $self->_graphcalc_done(0);
$self->_add_reading( $reading->id => $reading );
# Once the reading has been added, put it in both graphs.
$self->sequence->add_vertex( $reading->id );
$arg = $arg->id;
}
# Remove the reading from the graphs.
+ $self->_graphcalc_done(0);
$self->sequence->delete_vertex( $arg );
$self->relations->delete_reading( $arg );
# We only need the IDs for adding paths to the graph, not the reading
# objects themselves.
my( $kept, $deleted, $combine_char ) = $self->_stringify_args( @_ );
+ $self->_graphcalc_done(0);
# The kept reading should inherit the paths and the relationships
# of the deleted reading.
# objects themselves.
my( $source, $target, $wit ) = $self->_stringify_args( @_ );
+ $self->_graphcalc_done(0);
# Connect the readings
$self->sequence->add_edge( $source, $target );
# Note the witness in question
# objects themselves.
my( $source, $target, $wit ) = $self->_stringify_args( @args );
+ $self->_graphcalc_done(0);
if( $self->sequence->has_edge_attribute( $source, $target, $wit ) ) {
$self->sequence->delete_edge_attribute( $source, $target, $wit );
}
sub clear_witness {
my( $self, @sigils ) = @_;
+ $self->_graphcalc_done(0);
# Clear the witness(es) out of the paths
foreach my $e ( $self->paths ) {
foreach my $sig ( @sigils ) {
my( $source, $target, $opts ) = $self->_stringify_args( @_ );
my( @vectors ) = $self->relations->add_relationship( $source,
$self->reading( $source ), $target, $self->reading( $target ), $opts );
- # Force a full rank recalculation every time. Yuck.
- $self->calculate_ranks() if $self->end->has_rank;
+ $self->_graphcalc_done(0);
return @vectors;
}
+around qw/ get_relationship del_relationship / => sub {
+ my $orig = shift;
+ my $self = shift;
+ my @args = @_;
+ if( @args == 1 && ref( $args[0] ) eq 'ARRAY' ) {
+ @args = @{$_[0]};
+ }
+ my( $source, $target ) = $self->_stringify_args( @args );
+ $self->$orig( $source, $target );
+};
+
=head2 reading_witnesses( $reading )
Return a list of sigils corresponding to the witnesses in which the reading appears.
my $wits = $self->sequence->get_edge_attributes( @$e );
@all_witnesses{ keys %$wits } = 1;
}
+ my $acstr = $self->ac_label;
+ foreach my $acwit ( grep { $_ =~ s/^(.*)\Q$acstr\E$/$1/ } keys %all_witnesses ) {
+ delete $all_witnesses{$acwit.$acstr} if exists $all_witnesses{$acwit};
+ }
return keys %all_witnesses;
}
=head2 as_svg( \%options )
Returns an SVG string that represents the graph, via as_dot and graphviz.
-See as_dot for a list of options.
+See as_dot for a list of options. Must have GraphViz (dot) installed to run.
=cut
sub as_svg {
my( $self, $opts ) = @_;
-
- my @cmd = qw/dot -Tsvg/;
- my( $svg, $err );
- my $dotfile = File::Temp->new();
- ## USE FOR DEBUGGING
- # $dotfile->unlink_on_destroy(0);
- binmode $dotfile, ':utf8';
- print $dotfile $self->as_dot( $opts );
- push( @cmd, $dotfile->filename );
- run( \@cmd, ">", binary(), \$svg );
- # HACK part 3 - remove silent node+edge
- my $parser = XML::LibXML->new();
- my $svgdom = $parser->parse_string( $svg );
- my $xpc = XML::LibXML::XPathContext->new( $svgdom->documentElement );
- $xpc->registerNs( 'svg', 'http://www.w3.org/2000/svg' );
- my @hacknodes = $xpc->findnodes( '//svg:g[contains(child::svg:title, "#SILENT#")]' );
- foreach my $h ( @hacknodes ) {
- $h->parentNode->removeChild( $h );
- }
- return decode_utf8( $svgdom->toString() );
+ throw( "Need GraphViz installed to output SVG" )
+ unless File::Which::which( 'dot' );
+ my $want_subgraph = exists $opts->{'from'} || exists $opts->{'to'};
+ $self->calculate_ranks() unless $self->_graphcalc_done;
+ if( !$self->has_cached_svg || $opts->{'recalc'} || $want_subgraph ) {
+ my @cmd = qw/dot -Tsvg/;
+ my( $svg, $err );
+ my $dotfile = File::Temp->new();
+ ## USE FOR DEBUGGING
+ # $dotfile->unlink_on_destroy(0);
+ binmode $dotfile, ':utf8';
+ print $dotfile $self->as_dot( $opts );
+ push( @cmd, $dotfile->filename );
+ run( \@cmd, ">", binary(), \$svg );
+ $svg = decode_utf8( $svg );
+ $self->cached_svg( $svg ) unless $want_subgraph;
+ return $svg;
+ } else {
+ return $self->cached_svg;
+ }
}
my $endrank = $opts->{'to'} if $opts;
my $color_common = $opts->{'color_common'} if $opts;
my $STRAIGHTENHACK = !$startrank && !$endrank && $self->end->rank
- && $self->end->rank > 100;
-
+ && $self->end->rank > 100;
+
# Check the arguments
if( $startrank ) {
return if $endrank && $startrank > $endrank;
$endrank = undef if $endrank == $self->end->rank;
}
- # TODO consider making some of these things configurable
my $graph_name = $self->tradition->name;
$graph_name =~ s/[^\w\s]//g;
$graph_name = join( '_', split( /\s+/, $graph_name ) );
'bgcolor' => 'none',
);
my %node_attrs = (
- 'fontsize' => 11,
+ 'fontsize' => 14,
'fillcolor' => 'white',
'style' => 'filled',
'shape' => 'ellipse'
}
if( $STRAIGHTENHACK ) {
## HACK part 1
- $dot .= "\tsubgraph { rank=same \"#START#\" \"#SILENT#\" }\n";
- $dot .= "\t\"#SILENT#\" [ color=white,penwidth=0,label=\"\" ];"
+ $dot .= "\tsubgraph { rank=same \"#START#\" \"#SILENT#\" }\n";
+ $dot .= "\t\"#SILENT#\" [ shape=diamond,color=white,penwidth=0,label=\"\" ];"
}
my %used; # Keep track of the readings that actually appear in the graph
- foreach my $reading ( $self->readings ) {
+ # Sort the readings by rank if we have ranks; this speeds layout.
+ my @all_readings = $self->end->has_rank
+ ? sort { $a->rank <=> $b->rank } $self->readings
+ : $self->readings;
+ # TODO Refrain from outputting lacuna nodes - just grey out the edges.
+ foreach my $reading ( @all_readings ) {
# Only output readings within our rank range.
next if $startrank && $reading->rank < $startrank;
next if $endrank && $reading->rank > $endrank;
next if $reading->id eq $reading->text;
my $rattrs;
my $label = $reading->text;
+ $label .= '-' if $reading->join_next;
+ $label = "-$label" if $reading->join_prior;
$label =~ s/\"/\\\"/g;
$rattrs->{'label'} = $label;
$rattrs->{'fillcolor'} = '#b3f36d' if $reading->is_common && $color_common;
$dot .= sprintf( "\t\"%s\" %s;\n", $reading->id, _dot_attr_string( $rattrs ) );
}
- # Add the real edges
+ # Add the real edges. Need to weight one edge per rank jump, in a
+ # continuous line.
+ # my $weighted = $self->_add_edge_weights;
my @edges = $self->paths;
my( %substart, %subend );
foreach my $edge ( @edges ) {
# Do we need to output this edge?
if( $used{$edge->[0]} && $used{$edge->[1]} ) {
- my $label = $self->path_display_label( $self->path_witnesses( $edge ) );
+ my $label = $self->_path_display_label( $self->path_witnesses( $edge ) );
my $variables = { %edge_attrs, 'label' => $label };
+
# Account for the rank gap if necessary
- if( $self->reading( $edge->[1] )->has_rank
- && $self->reading( $edge->[0] )->has_rank
- && $self->reading( $edge->[1] )->rank
- - $self->reading( $edge->[0] )->rank > 1 ) {
- $variables->{'minlen'} = $self->reading( $edge->[1] )->rank
- - $self->reading( $edge->[0] )->rank;
+ my $rank0 = $self->reading( $edge->[0] )->rank
+ if $self->reading( $edge->[0] )->has_rank;
+ my $rank1 = $self->reading( $edge->[1] )->rank
+ if $self->reading( $edge->[1] )->has_rank;
+ if( defined $rank0 && defined $rank1 && $rank1 - $rank0 > 1 ) {
+ $variables->{'minlen'} = $rank1 - $rank0;
}
+
+ # Add the calculated edge weights
+ # if( exists $weighted->{$edge->[0]}
+ # && $weighted->{$edge->[0]} eq $edge->[1] ) {
+ # # $variables->{'color'} = 'red';
+ # $variables->{'weight'} = 3.0;
+ # }
+
# EXPERIMENTAL: make edge width reflect no. of witnesses
my $extrawidth = scalar( $self->path_witnesses( $edge ) ) * 0.2;
$variables->{'penwidth'} = $extrawidth + 0.8; # gives 1 for a single wit
}
# Add substitute start and end edges if necessary
foreach my $node ( keys %substart ) {
- my $witstr = $self->path_display_label ( $self->reading_witnesses( $self->reading( $node ) ) );
+ my $witstr = $self->_path_display_label ( $self->reading_witnesses( $self->reading( $node ) ) );
my $variables = { %edge_attrs, 'label' => $witstr };
my $varopts = _dot_attr_string( $variables );
$dot .= "\t\"#SUBSTART#\" -> \"$node\" $varopts;";
}
foreach my $node ( keys %subend ) {
- my $witstr = $self->path_display_label ( $self->reading_witnesses( $self->reading( $node ) ) );
+ my $witstr = $self->_path_display_label ( $self->reading_witnesses( $self->reading( $node ) ) );
my $variables = { %edge_attrs, 'label' => $witstr };
my $varopts = _dot_attr_string( $variables );
$dot .= "\t\"$node\" -> \"#SUBEND#\" $varopts;";
# HACK part 2
if( $STRAIGHTENHACK ) {
$dot .= "\t\"#END#\" -> \"#SILENT#\" [ color=white,penwidth=0 ];\n";
- }
-
+ }
+
$dot .= "}\n";
return $dot;
}
return( '[ ' . join( ', ', @attrs ) . ' ]' );
}
+sub _add_edge_weights {
+ my $self = shift;
+ # Walk the graph from START to END, choosing the successor node with
+ # the largest number of witness paths each time.
+ my $weighted = {};
+ my $curr = $self->start->id;
+ my $ranked = $self->end->has_rank;
+ while( $curr ne $self->end->id ) {
+ my $rank = $ranked ? $self->reading( $curr )->rank : 0;
+ my @succ = sort { $self->path_witnesses( $curr, $a )
+ <=> $self->path_witnesses( $curr, $b ) }
+ $self->sequence->successors( $curr );
+ my $next = pop @succ;
+ my $nextrank = $ranked ? $self->reading( $next )->rank : 0;
+ # Try to avoid lacunae in the weighted path.
+ while( @succ &&
+ ( $self->reading( $next )->is_lacuna ||
+ $nextrank - $rank > 1 ) ){
+ $next = pop @succ;
+ }
+ $weighted->{$curr} = $next;
+ $curr = $next;
+ }
+ return $weighted;
+}
+
+=head2 path_witnesses( $edge )
+
+Returns the list of sigils whose witnesses are associated with the given edge.
+The edge can be passed as either an array or an arrayref of ( $source, $target ).
+
+=cut
+
sub path_witnesses {
my( $self, @edge ) = @_;
# If edge is an arrayref, cope.
return @wits;
}
-sub path_display_label {
+sub _path_display_label {
my $self = shift;
my @wits = sort @_;
my $maj = scalar( $self->tradition->witnesses ) * 0.6;
return join( ', ', @wits );
}
}
-
+
+=head2 witnesses_at_rank
+
+Returns a list of witnesses that are not lacunose, for a given rank.
+
+=cut
+
+sub witnesses_at_rank {
+ my( $self, $rank ) = @_;
+}
=head2 as_graphml
sub as_graphml {
my( $self ) = @_;
-
+ $self->calculate_ranks unless $self->_graphcalc_done;
+
# Some namespaces
my $graphml_ns = 'http://graphml.graphdrawing.org/xmlns';
my $xsi_ns = 'http://www.w3.org/2001/XMLSchema-instance';
is_start => 'boolean',
is_end => 'boolean',
is_lacuna => 'boolean',
+ is_common => 'boolean',
+ join_prior => 'boolean',
+ join_next => 'boolean',
);
foreach my $datum ( keys %node_data ) {
$node_data_keys{$datum} = 'dn'.$ndi++;
relationship => 'string', # ID/label for a relationship
extra => 'boolean', # Path key
scope => 'string', # Relationship key
+ annotation => 'string', # Relationship key
non_correctable => 'boolean', # Relationship key
non_independent => 'boolean', # Relationship key
);
}
# Add the relationship graph to the XML
- $self->relations->as_graphml( $graphml_ns, $root, \%node_hash,
+ $self->relations->_as_graphml( $graphml_ns, $root, \%node_hash,
$node_data_keys{'id'}, \%edge_data_keys );
# Save and return the thing
sub as_csv {
my( $self ) = @_;
- my $table = $self->make_alignment_table;
+ my $table = $self->alignment_table;
my $csv = Text::CSV_XS->new( { binary => 1, quote_null => 0 } );
my @result;
# Make the header row
# Make the rest of the rows
foreach my $idx ( 0 .. $table->{'length'} - 1 ) {
my @rowobjs = map { $_->{'tokens'}->[$idx] } @{$table->{'alignment'}};
- my @row = map { $_ ? $_->{'t'} : $_ } @rowobjs;
+ my @row = map { $_ ? $_->{'t'}->text : $_ } @rowobjs;
$csv->combine( @row );
push( @result, decode_utf8( $csv->string ) );
}
return join( "\n", @result );
}
-=head2 make_alignment_table( $use_refs, $include_witnesses )
+=head2 alignment_table( $use_refs, $include_witnesses )
Return a reference to an alignment table, in a slightly enhanced CollateX
format which looks like this:
=cut
-sub make_alignment_table {
- my( $self, $noderefs, $include ) = @_;
+sub alignment_table {
+ my( $self ) = @_;
+ $self->calculate_ranks() unless $self->_graphcalc_done;
+ return $self->cached_table if $self->has_cached_table;
+
# Make sure we can do this
throw( "Need a linear graph in order to make an alignment table" )
unless $self->linear;
my $table = { 'alignment' => [], 'length' => $self->end->rank - 1 };
my @all_pos = ( 1 .. $self->end->rank - 1 );
foreach my $wit ( sort { $a->sigil cmp $b->sigil } $self->tradition->witnesses ) {
- if( $include ) {
- next unless $include->{$wit->sigil};
- }
# print STDERR "Making witness row(s) for " . $wit->sigil . "\n";
my @wit_path = $self->reading_sequence( $self->start, $self->end, $wit->sigil );
- my @row = _make_witness_row( \@wit_path, \@all_pos, $noderefs );
+ my @row = _make_witness_row( \@wit_path, \@all_pos );
push( @{$table->{'alignment'}},
{ 'witness' => $wit->sigil, 'tokens' => \@row } );
if( $wit->is_layered ) {
my @wit_ac_path = $self->reading_sequence( $self->start, $self->end,
$wit->sigil.$self->ac_label );
- my @ac_row = _make_witness_row( \@wit_ac_path, \@all_pos, $noderefs );
+ my @ac_row = _make_witness_row( \@wit_ac_path, \@all_pos );
push( @{$table->{'alignment'}},
{ 'witness' => $wit->sigil.$self->ac_label, 'tokens' => \@ac_row } );
}
}
- return $table;
+ $self->cached_table( $table );
+ return $table;
}
sub _make_witness_row {
- my( $path, $positions, $noderefs ) = @_;
+ my( $path, $positions ) = @_;
my %char_hash;
map { $char_hash{$_} = undef } @$positions;
my $debug = 0;
$rtext = '#LACUNA#' if $rdg->is_lacuna;
print STDERR "rank " . $rdg->rank . "\n" if $debug;
# print STDERR "No rank for " . $rdg->id . "\n" unless defined $rdg->rank;
- $char_hash{$rdg->rank} = $noderefs ? { 't' => $rdg }
- : { 't' => $rtext };
+ $char_hash{$rdg->rank} = { 't' => $rdg };
}
my @row = map { $char_hash{$_} } @$positions;
# Fill in lacuna markers for undef spots in the row
foreach my $el ( @row ) {
# If we are using node reference, make the lacuna node appear many times
# in the table. If not, use the lacuna tag.
- if( $last_el && _el_is_lacuna( $last_el ) && !defined $el ) {
- $el = $noderefs ? $last_el : { 't' => '#LACUNA#' };
+ if( $last_el && $last_el->{'t'}->is_lacuna && !defined $el ) {
+ $el = $last_el;
}
push( @filled_row, $el );
$last_el = $el;
return @filled_row;
}
-# Tiny utility function to say if a table element is a lacuna
-sub _el_is_lacuna {
- my $el = shift;
- return 1 if $el->{'t'} eq '#LACUNA#';
- return 1 if ref( $el->{'t'} ) eq 'Text::Tradition::Collation::Reading'
- && $el->{'t'}->is_lacuna;
- return 0;
-}
-
-# Helper to turn the witnesses along columns rather than rows. Assumes
-# equal-sized rows.
-sub _turn_table {
- my( $table ) = @_;
- my $result = [];
- return $result unless scalar @$table;
- my $nrows = scalar @{$table->[0]};
- foreach my $idx ( 0 .. $nrows - 1 ) {
- foreach my $wit ( 0 .. $#{$table} ) {
- $result->[$idx]->[$wit] = $table->[$wit]->[$idx];
- }
- }
- return $result;
-}
-
=head1 NAVIGATION METHODS
=head2 reading_sequence( $first, $last, $sigil, $backup )
$start = $self->start unless $start;
$end = $self->end unless $end;
my @path = grep { !$_->is_meta } $self->reading_sequence( $start, $end, $wit );
- return join( ' ', map { $_->text } @path );
+ my $pathtext = '';
+ my $last;
+ foreach my $r ( @path ) {
+ if( $r->join_prior || !$last || $last->join_next ) {
+ $pathtext .= $r->text;
+ } else {
+ $pathtext .= ' ' . $r->text;
+ }
+ $last = $r;
+ }
+ return $pathtext;
}
=head1 INITIALIZATION METHODS
Calculate the reading ranks (that is, their aligned positions relative
to each other) for the graph. This can only be called on linear collations.
+=begin testing
+
+use Text::Tradition;
+
+my $cxfile = 't/data/Collatex-16.xml';
+my $t = Text::Tradition->new(
+ 'name' => 'inline',
+ 'input' => 'CollateX',
+ 'file' => $cxfile,
+ );
+my $c = $t->collation;
+
+# Make an svg
+my $table = $c->alignment_table;
+ok( $c->has_cached_table, "Alignment table was cached" );
+is( $c->alignment_table, $table, "Cached table returned upon second call" );
+$c->calculate_ranks;
+is( $c->alignment_table, $table, "Cached table retained with no rank change" );
+$c->add_relationship( 'n9', 'n23', { 'type' => 'spelling' } );
+isnt( $c->alignment_table, $table, "Alignment table changed after relationship add" );
+
+=end testing
+
=cut
sub calculate_ranks {
my $self = shift;
+ # Save the existing ranks, in case we need to invalidate the cached SVG.
+ my %existing_ranks;
# Walk a version of the graph where every node linked by a relationship
# edge is fundamentally the same node, and do a topological ranking on
# the nodes in this graph.
# Add the edges.
foreach my $r ( $self->readings ) {
+ $existing_ranks{$r} = $r->rank;
foreach my $n ( $self->sequence->successors( $r->id ) ) {
my( $tfrom, $tto ) = ( $rel_containers{$r->id},
$rel_containers{$n} );
throw( "Ranks not calculated after $last - do you have a cycle in the graph?" );
}
}
+ # Do we need to invalidate the cached data?
+ if( $self->has_cached_svg || $self->has_cached_table ) {
+ foreach my $r ( $self->readings ) {
+ next if defined( $existing_ranks{$r} )
+ && $existing_ranks{$r} == $r->rank;
+ # Something has changed, so clear the cache
+ $self->_clear_cache;
+ # ...and recalculate the common readings.
+ $self->calculate_common_readings();
+ last;
+ }
+ }
+ # The graph calculation information is now up to date.
+ $self->_graphcalc_done(1);
}
sub _assign_rank {
return @next_nodes;
}
+sub _clear_cache {
+ my $self = shift;
+ $self->wipe_svg if $self->has_cached_svg;
+ $self->wipe_table if $self->has_cached_table;
+}
+
+
=head2 flatten_ranks
A convenience method for parsing collation data. Searches the graph for readings
}
}
}
+
=head2 calculate_common_readings
sub calculate_common_readings {
my $self = shift;
my @common;
- my $table = $self->make_alignment_table( 1 );
+ map { $_->is_common( 0 ) } $self->readings;
+ # Implicitly calls calculate_ranks
+ my $table = $self->alignment_table;
foreach my $idx ( 0 .. $table->{'length'} - 1 ) {
- my @row = map { $_->{'tokens'}->[$idx]->{'t'} } @{$table->{'alignment'}};
+ my @row = map { $_->{'tokens'}->[$idx]
+ ? $_->{'tokens'}->[$idx]->{'t'} : '' }
+ @{$table->{'alignment'}};
my %hash;
foreach my $r ( @row ) {
if( $r ) {
sub common_predecessor {
my $self = shift;
my( $r1, $r2 ) = $self->_objectify_args( @_ );
- return $self->common_in_path( $r1, $r2, 'predecessors' );
+ return $self->_common_in_path( $r1, $r2, 'predecessors' );
}
sub common_successor {
my $self = shift;
my( $r1, $r2 ) = $self->_objectify_args( @_ );
- return $self->common_in_path( $r1, $r2, 'successors' );
+ return $self->_common_in_path( $r1, $r2, 'successors' );
}
-sub common_in_path {
+sub _common_in_path {
my( $self, $r1, $r2, $dir ) = @_;
my $iter = $r1->rank > $r2->rank ? $r1->rank : $r2->rank;
$iter = $self->end->rank - $iter if $dir eq 'successors';
no Moose;
__PACKAGE__->meta->make_immutable;
-=head1 BUGS / TODO
+=head1 LICENSE
-=over
+This package is free software and is provided "as is" without express
+or implied warranty. You can redistribute it and/or modify it under
+the same terms as Perl itself.
-=item * Get rid of $backup in reading_sequence
+=head1 AUTHOR
-=back
+Tara L Andrews E<lt>aurum@cpan.orgE<gt>
projects / scpubgit/stemmatology.git / blobdiff