use File::Which;
use Graph;
use IPC::Run qw( run binary );
-use Text::CSV_XS;
+use Text::CSV;
use Text::Tradition::Collation::Reading;
use Text::Tradition::Collation::RelationshipStore;
use Text::Tradition::Error;
+use XML::Easy::Syntax qw( $xml10_namestartchar_rx $xml10_namechar_rx );
use XML::LibXML;
use XML::LibXML::XPathContext;
use Moose;
has 'tradition' => (
is => 'ro',
isa => 'Text::Tradition',
+ writer => '_set_tradition',
weak_ref => 1,
);
ok( $c->reading( 'n21p0' ), "New reading exists" );
is( scalar $c->readings, $rno, "Reading add offset by flatten_ranks" );
-# Combine n3 and n4
+# Combine n3 and n4 ( with his )
$c->merge_readings( 'n3', 'n4', 1 );
ok( !$c->reading('n4'), "Reading n4 is gone" );
is( $c->reading('n3')->text, 'with his', "Reading n3 has both words" );
-# Collapse n25 and n26
-$c->merge_readings( 'n25', 'n26' );
-ok( !$c->reading('n26'), "Reading n26 is gone" );
-is( $c->reading('n25')->text, 'rood', "Reading n25 has an unchanged word" );
+# Collapse n9 and n10 ( rood / root )
+$c->merge_readings( 'n9', 'n10' );
+ok( !$c->reading('n10'), "Reading n10 is gone" );
+is( $c->reading('n9')->text, 'rood', "Reading n9 has an unchanged word" );
# Combine n21 and n21p0
my $remaining = $c->reading('n21');
sub add_relationship {
my $self = shift;
my( $source, $target, $opts ) = $self->_stringify_args( @_ );
- my( @vectors ) = $self->relations->add_relationship( $source,
- $self->reading( $source ), $target, $self->reading( $target ), $opts );
+ my( @vectors ) = $self->relations->add_relationship( $source, $target, $opts );
$self->_graphcalc_done(0);
return @vectors;
}
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;
+ $self->calculate_ranks() unless( $self->_graphcalc_done || $opts->{'nocalc'} );
if( !$self->has_cached_svg || $opts->{'recalc'} || $want_subgraph ) {
my @cmd = qw/dot -Tsvg/;
my( $svg, $err );
my $color_common = $opts->{'color_common'} if $opts;
my $STRAIGHTENHACK = !$startrank && !$endrank && $self->end->rank
&& $self->end->rank > 100;
+ $STRAIGHTENHACK = 1 if $opts->{'straight'}; # even for subgraphs or small graphs
# Check the arguments
if( $startrank ) {
}
if( $STRAIGHTENHACK ) {
## HACK part 1
- $dot .= "\tsubgraph { rank=same \"#START#\" \"#SILENT#\" }\n";
+ my $startlabel = $startrank ? 'SUBSTART' : 'START';
+ $dot .= "\tsubgraph { rank=same \"#$startlabel#\" \"#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
}
# HACK part 2
if( $STRAIGHTENHACK ) {
- $dot .= "\t\"#END#\" -> \"#SILENT#\" [ color=white,penwidth=0 ];\n";
+ my $endlabel = $endrank ? 'SUBEND' : 'END';
+ $dot .= "\t\"#$endlabel#\" -> \"#SILENT#\" [ color=white,penwidth=0 ];\n";
}
$dot .= "}\n";
return @wits;
}
+# Helper function. Make a display label for the given witnesses, showing a.c.
+# witnesses only where the main witness is not also in the list.
sub _path_display_label {
my $self = shift;
- my @wits = sort @_;
+ my %wits;
+ map { $wits{$_} = 1 } @_;
+
+ # If an a.c. wit is listed, remove it if the main wit is also listed.
+ # Otherwise keep it for explicit listing.
+ my $aclabel = $self->ac_label;
+ my @disp_ac;
+ foreach my $w ( sort keys %wits ) {
+ if( $w =~ /^(.*)\Q$aclabel\E$/ ) {
+ if( exists $wits{$1} ) {
+ delete $wits{$w};
+ } else {
+ push( @disp_ac, $w );
+ }
+ }
+ }
+
+ # See if we are in a majority situation.
my $maj = scalar( $self->tradition->witnesses ) * 0.6;
- if( scalar @wits > $maj ) {
- # TODO break out a.c. wits
- return 'majority';
+ if( scalar keys %wits > $maj ) {
+ unshift( @disp_ac, 'majority' );
+ return join( ', ', @disp_ac );
} else {
- return join( ', ', @wits );
+ return join( ', ', sort keys %wits );
}
}
=cut
sub as_graphml {
- my( $self ) = @_;
+ my( $self, $options ) = @_;
$self->calculate_ranks unless $self->_graphcalc_done;
+ my $start = $options->{'from'}
+ ? $self->reading( $options->{'from'} ) : $self->start;
+ my $end = $options->{'to'}
+ ? $self->reading( $options->{'to'} ) : $self->end;
+ if( $start->has_rank && $end->has_rank && $end->rank < $start->rank ) {
+ throw( 'Start node must be before end node' );
+ }
+ # The readings need to be ranked for this to work.
+ $start = $self->start unless $start->has_rank;
+ $end = $self->end unless $end->has_rank;
+ my $rankoffset = 0;
+ unless( $start eq $self->start ) {
+ $rankoffset = $start->rank - 1;
+ }
+ my %use_readings;
+
# Some namespaces
my $graphml_ns = 'http://graphml.graphdrawing.org/xmlns';
my $xsi_ns = 'http://www.w3.org/2001/XMLSchema-instance';
$key->setAttribute( 'id', $edge_data_keys{$datum} );
}
- # Add the collation graph itself
+ # Add the collation graph itself. First, sanitize the name to a valid XML ID.
+ my $xmlidname = $self->tradition->name;
+ $xmlidname =~ s/(?!$xml10_namechar_rx)./_/g;
+ if( $xmlidname !~ /^$xml10_namestartchar_rx/ ) {
+ $xmlidname = '_'.$xmlidname;
+ }
my $sgraph = $root->addNewChild( $graphml_ns, 'graph' );
$sgraph->setAttribute( 'edgedefault', 'directed' );
- $sgraph->setAttribute( 'id', $self->tradition->name );
+ $sgraph->setAttribute( 'id', $xmlidname );
$sgraph->setAttribute( 'parse.edgeids', 'canonical' );
- $sgraph->setAttribute( 'parse.edges', scalar($self->paths) );
+ $sgraph->setAttribute( 'parse.edges', 0 ); # fill in later
$sgraph->setAttribute( 'parse.nodeids', 'canonical' );
- $sgraph->setAttribute( 'parse.nodes', scalar($self->readings) );
+ $sgraph->setAttribute( 'parse.nodes', 0 ); # fill in later
$sgraph->setAttribute( 'parse.order', 'nodesfirst' );
# Collation attribute data
my %node_hash;
# Add our readings to the graph
foreach my $n ( sort { $a->id cmp $b->id } $self->readings ) {
+ next if $n->has_rank && $n ne $self->start && $n ne $self->end &&
+ ( $n->rank < $start->rank || $n->rank > $end->rank );
+ $use_readings{$n->id} = 1;
# Add to the main graph
my $node_el = $sgraph->addNewChild( $graphml_ns, 'node' );
my $node_xmlid = 'n' . $node_ctr++;
$node_el->setAttribute( 'id', $node_xmlid );
foreach my $d ( keys %reading_attributes ) {
my $nval = $n->$d;
+ if( $rankoffset && $d eq 'rank' && $n ne $self->start ) {
+ # Adjust the ranks within the subgraph.
+ $nval = $n eq $self->end ? $end->rank - $rankoffset + 1
+ : $nval - $rankoffset;
+ }
_add_graphml_data( $node_el, $node_data_keys{$d}, $nval )
if defined $nval;
}
# Add the path edges to the sequence graph
my $edge_ctr = 0;
+ $DB::single = 1;
foreach my $e ( sort { $a->[0] cmp $b->[0] } $self->sequence->edges() ) {
# We add an edge in the graphml for every witness in $e.
- foreach my $wit ( sort $self->path_witnesses( $e ) ) {
+ next unless( $use_readings{$e->[0]} || $use_readings{$e->[1]} );
+ my @edge_wits = sort $self->path_witnesses( $e );
+ $e->[0] = $self->start->id unless $use_readings{$e->[0]};
+ $e->[1] = $self->end->id unless $use_readings{$e->[1]};
+ # Skip any path from start to end; that witness is not in the subgraph.
+ next if ( $e->[0] eq $self->start->id && $e->[1] eq $self->end->id );
+ foreach my $wit ( @edge_wits ) {
my( $id, $from, $to ) = ( 'e'.$edge_ctr++,
$node_hash{ $e->[0] },
$node_hash{ $e->[1] } );
}
}
+ # Report the actual number of nodes and edges that went in
+ $sgraph->setAttribute( 'parse.edges', $edge_ctr );
+ $sgraph->setAttribute( 'parse.nodes', $node_ctr );
+
# Add the relationship graph to the XML
map { delete $edge_data_keys{$_} } @path_attributes;
$self->relations->_as_graphml( $graphml_ns, $root, \%node_hash,
sub as_csv {
my( $self ) = @_;
my $table = $self->alignment_table;
- my $csv = Text::CSV_XS->new( { binary => 1, quote_null => 0 } );
+ my $csv = Text::CSV->new( { binary => 1, quote_null => 0 } );
my @result;
# Make the header row
$csv->combine( map { $_->{'witness'} } @{$table->{'alignment'}} );
return @common;
}
-=head2 path_text( $sigil, $mainsigil [, $start, $end ] )
+=head2 path_text( $sigil, [, $start, $end ] )
Returns the text of a witness (plus its backup, if we are using a layer)
as stored in the collation. The text is returned as a string, where the
my( $self, $wit ) = @_;
my @chain = @{$wit->path};
my $sig = $wit->sigil;
+ # Add start and end if necessary
+ unshift( @chain, $self->start ) unless $chain[0] eq $self->start;
+ push( @chain, $self->end ) unless $chain[-1] eq $self->end;
foreach my $idx ( 0 .. $#chain-1 ) {
$self->add_path( $chain[$idx], $chain[$idx+1], $sig );
}
if( $wit->is_layered ) {
@chain = @{$wit->uncorrected_path};
+ unshift( @chain, $self->start ) unless $chain[0] eq $self->start;
+ push( @chain, $self->end ) unless $chain[-1] eq $self->end;
foreach my $idx( 0 .. $#chain-1 ) {
my $source = $chain[$idx];
my $target = $chain[$idx+1];
$wit->clear_uncorrected_path;
}
+=head2 equivalence_graph( \%readingmap, $startrank, $endrank, @testvector )
+
+Returns an equivalence graph of the collation, in which all readings
+related via a 'colocated' relationship are transformed into a single
+vertex. Can be used to determine the validity of a new relationship. The
+mapping between equivalence vertices and reading IDs will be stored in the
+hash whose reference is passed as readingmap. For a subset of the graph,
+pass in a start and/or an ending rank (this only works if L<calculate_ranks>
+has been called at least once.)
+
+It is also possible to pass in a test relationship in @testvector, and get
+the resulting equivalence graph before the relationship has been made.
+
+=cut
+
+sub equivalence_graph {
+ my( $self, $map, $start, $end, @newvector ) = @_;
+ $start = undef unless $self->end->has_rank;
+ $end = undef unless $self->end->has_rank;
+ my $eqgraph = Graph->new();
+ my $rel_ctr = 0;
+ # Add the nodes
+ foreach my $r ( $self->readings ) {
+ unless( $r eq $self->start || $r eq $self->end ) {
+ next if $start && $r->rank < $start;
+ next if $end && $r->rank > $end;
+ }
+ next if exists $map->{$r->id};
+ my @rels = $self->related_readings( $r->id, 'colocated' );
+ push( @rels, $r->id );
+ # Make an equivalence vertex
+ my $rn = 'equivalence_' . $rel_ctr++;
+ $eqgraph->add_vertex( $rn );
+ # Note which readings belong to this vertex.
+ push( @rels, $r->id );
+ foreach( @rels ) {
+ $map->{$_} = $rn;
+ }
+ }
+
+ # Add the edges.
+ foreach my $p ( $self->paths ) {
+ my $efrom = exists $map->{$p->[0]} ? $map->{$p->[0]}
+ : $map->{$self->start->id};
+ my $eto = exists $map->{$p->[1]} ? $map->{$p->[1]}
+ : $map->{$self->end->id};
+ $eqgraph->add_edge( $efrom, $eto );
+ }
+
+ # Collapse the vertices in @newvector if applicable.
+ if( @newvector ) {
+ my( $eqs, $eqt ) = map { $map->{$_} } @newvector;
+ $DB::single = 1 unless $eqs && $eqt;
+ unless( $eqs eq $eqt ) {
+ # Combine the vertices.
+ map { $eqgraph->add_edge( $eqs, $_ ) } $eqgraph->successors( $eqt );
+ map { $eqgraph->add_edge( $_, $eqs ) } $eqgraph->predecessors( $eqt );
+ $eqgraph->delete_vertex( $eqt );
+ }
+ }
+ return $eqgraph;
+}
+
=head2 calculate_ranks
Calculate the reading ranks (that is, their aligned positions relative
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' } );
+$c->add_relationship( 'n24', 'n23', { 'type' => 'spelling' } );
isnt( $c->alignment_table, $table, "Alignment table changed after relationship add" );
=end testing
my $self = shift;
# Save the existing ranks, in case we need to invalidate the cached SVG.
my %existing_ranks;
+ map { $existing_ranks{$_} = $_->rank } $self->readings;
# 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.
- my $topo_graph = Graph->new();
my %rel_containers;
- my $rel_ctr = 0;
- # Add the nodes
- foreach my $r ( $self->readings ) {
- next if exists $rel_containers{$r->id};
- my @rels = $r->related_readings( 'colocated' );
- if( @rels ) {
- # Make a relationship container.
- push( @rels, $r );
- my $rn = 'rel_container_' . $rel_ctr++;
- $topo_graph->add_vertex( $rn );
- foreach( @rels ) {
- $rel_containers{$_->id} = $rn;
- }
- } else {
- # Add a new node to mirror the old node.
- $rel_containers{$r->id} = $r->id;
- $topo_graph->add_vertex( $r->id );
- }
- }
-
- # 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} );
- # $DB::single = 1 unless $tfrom && $tto;
- $topo_graph->add_edge( $tfrom, $tto );
- }
- }
+ my $topo_graph = $self->equivalence_graph( \%rel_containers );
# Now do the rankings, starting with the start node.
my $topo_start = $rel_containers{$self->start->id};
$r->rank( $node_ranks->{$rel_containers{$r->id}} );
} else {
# Die. Find the last rank we calculated.
- my @all_defined = sort { $node_ranks->{$rel_containers{$a->id}}
- <=> $node_ranks->{$rel_containers{$b->id}} }
+ my @all_defined = sort { ( $node_ranks->{$rel_containers{$a->id}}||-1 )
+ <=> ( $node_ranks->{$rel_containers{$b->id}}||-1 ) }
$self->readings;
my $last = pop @all_defined;
throw( "Ranks not calculated after $last - do you have a cycle in the graph?" );
is( scalar @common, 8, "Found correct number of common readings" );
my @marked = sort $c->common_readings();
is( scalar @common, 8, "All common readings got marked as such" );
-my @expected = qw/ n1 n12 n16 n19 n20 n5 n6 n7 /;
+my @expected = qw/ n1 n11 n16 n19 n20 n5 n6 n7 /;
is_deeply( \@marked, \@expected, "Found correct list of common readings" );
=end testing
=head2 common_predecessor( $reading_a, $reading_b )
Find the last reading that occurs in sequence before both the given readings.
+At the very least this should be $self->start.
=head2 common_successor( $reading_a, $reading_b )
Find the first reading that occurs in sequence after both the given readings.
+At the very least this should be $self->end.
=begin testing
);
my $c = $t->collation;
-is( $c->common_predecessor( 'n9', 'n23' )->id,
+is( $c->common_predecessor( 'n24', 'n23' )->id,
'n20', "Found correct common predecessor" );
-is( $c->common_successor( 'n9', 'n23' )->id,
+is( $c->common_successor( 'n24', 'n23' )->id,
'#END#', "Found correct common successor" );
is( $c->common_predecessor( 'n19', 'n17' )->id,
'n16', "Found correct common predecessor for readings on same path" );
-is( $c->common_successor( 'n21', 'n26' )->id,
+is( $c->common_successor( 'n21', 'n10' )->id,
'#END#', "Found correct common successor for readings on same path" );
=end testing
return $self->_common_in_path( $r1, $r2, 'successors' );
}
+
+# TODO think about how to do this without ranks...
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';
+ my $iter = $self->end->rank;
my @candidates;
- my @last_checked = ( $r1, $r2 );
+ my @last_r1 = ( $r1 );
+ my @last_r2 = ( $r2 );
+ # my %all_seen = ( $r1 => 'r1', $r2 => 'r2' );
my %all_seen;
+ # print STDERR "Finding common $dir for $r1, $r2\n";
while( !@candidates ) {
- my @new_lc;
- foreach my $lc ( @last_checked ) {
+ last unless $iter--; # Avoid looping infinitely
+ # Iterate separately down the graph from r1 and r2
+ my( @new_lc1, @new_lc2 );
+ foreach my $lc ( @last_r1 ) {
+ foreach my $p ( $lc->$dir ) {
+ if( $all_seen{$p->id} && $all_seen{$p->id} ne 'r1' ) {
+ # print STDERR "Path candidate $p from $lc\n";
+ push( @candidates, $p );
+ } elsif( !$all_seen{$p->id} ) {
+ $all_seen{$p->id} = 'r1';
+ push( @new_lc1, $p );
+ }
+ }
+ }
+ foreach my $lc ( @last_r2 ) {
foreach my $p ( $lc->$dir ) {
- if( $all_seen{$p->id} ) {
+ if( $all_seen{$p->id} && $all_seen{$p->id} ne 'r2' ) {
+ # print STDERR "Path candidate $p from $lc\n";
push( @candidates, $p );
- } else {
- $all_seen{$p->id} = 1;
- push( @new_lc, $p );
+ } elsif( !$all_seen{$p->id} ) {
+ $all_seen{$p->id} = 'r2';
+ push( @new_lc2, $p );
}
}
}
- @last_checked = @new_lc;
+ @last_r1 = @new_lc1;
+ @last_r2 = @new_lc2;
}
my @answer = sort { $a->rank <=> $b->rank } @candidates;
return $dir eq 'predecessors' ? pop( @answer ) : shift ( @answer );
projects / scpubgit/stemmatology.git / blobdiff