X-Git-Url: http://git.shadowcat.co.uk/gitweb/gitweb.cgi?a=blobdiff_plain;f=lib%2FText%2FTradition%2FCollation%2FRelationshipStore.pm;h=4342bd98b79b209a991c37f034e8460a126a7095;hb=428bcf0bc79f77a7857b21ef881708faa792e33a;hp=2a0703a2f3e1dab054c1de5a036a5dfbb2465179;hpb=3579c22be6d538476081f0a0dede988aa3f7acb9;p=scpubgit%2Fstemmatology.git diff --git a/lib/Text/Tradition/Collation/RelationshipStore.pm b/lib/Text/Tradition/Collation/RelationshipStore.pm index 2a0703a..4342bd9 100644 --- a/lib/Text/Tradition/Collation/RelationshipStore.pm +++ b/lib/Text/Tradition/Collation/RelationshipStore.pm @@ -31,10 +31,10 @@ use_ok( 'Text::Tradition::Collation::RelationshipStore' ); my $cxfile = 't/data/Collatex-16.xml'; my $t = Text::Tradition->new( - 'name' => 'inline', - 'input' => 'CollateX', - 'file' => $cxfile, - ); + 'name' => 'inline', + 'input' => 'CollateX', + 'file' => $cxfile, + ); my $c = $t->collation; my @v1 = $c->add_relationship( 'n21', 'n22', { 'type' => 'lexical' } ); @@ -196,18 +196,9 @@ sub create { } } - # Check to see if a nonlocal relationship is defined for the two readings - $rel = $self->scoped_relationship( $options->{'reading_a'}, - $options->{'reading_b'} ); - if( $rel && $rel->type eq $options->{'type'} ) { - return $rel; - } elsif( $rel ) { - throw( sprintf( "Relationship of type %s with scope %s already defined for readings %s and %s", $rel->type, $rel->scope, $options->{'reading_a'}, $options->{'reading_b'} ) ); - } else { - $rel = Text::Tradition::Collation::Relationship->new( $options ); - $self->add_scoped_relationship( $rel ) if $rel->nonlocal; - return $rel; - } + $rel = Text::Tradition::Collation::Relationship->new( $options ); + $self->add_scoped_relationship( $rel ) if $rel->nonlocal; + return $rel; } =head2 add_scoped_relationship( $rel ) @@ -241,8 +232,12 @@ between the two reading strings. Returns undef if there is no general relationsh sub scoped_relationship { my( $self, $rdga, $rdgb ) = @_; my( $first, $second ) = sort( $rdga, $rdgb ); + my( $lcfirst, $lcsecond ) = sort( lc( $rdga ), lc( $rdgb ) ); if( exists $self->scopedrels->{$first}->{$second} ) { return $self->scopedrels->{$first}->{$second}; + } elsif( exists $self->scopedrels->{$lcfirst}->{$lcsecond} ) { + my $rel = $self->scopedrels->{$lcfirst}->{$lcsecond}; + return $rel->type ne 'orthographic' ? $rel : undef; } else { return undef; } @@ -260,10 +255,16 @@ add_relationship. =begin testing +use Test::Warn; use Text::Tradition; use TryCatch; -my $t1 = Text::Tradition->new( 'input' => 'Self', 'file' => 't/data/legendfrag.xml' ); +my $t1; +warning_is { + $t1 = Text::Tradition->new( 'input' => 'Self', 'file' => 't/data/legendfrag.xml' ); +} 'DROPPING r14.2 -> r8.1: Cannot set relationship on a meta reading', + "Got expected relationship drop warning on parse"; + # Test 1.1: try to equate nodes that are prevented with an intermediate collation ok( $t1, "Parsed test fragment file" ); my $c1 = $t1->collation; @@ -305,9 +306,23 @@ try { "Relationship link prevented for a meta reading" ); } +# Test 1.4: try to break a relationship near a meta reading +$c1->add_relationship( 'r7.6', 'r7.3', { type => 'orthographic' } ); +try { + $c1->del_relationship( 'r7.6', 'r7.7' ); + $c1->del_relationship( 'r7.6', 'r7.3' ); + ok( 1, "Relationship broken with a meta reading as neighbor" ); +} catch { + ok( 0, "Relationship deletion failed with a meta reading as neighbor" ); +} + # Test 2.1: try to equate nodes that are prevented with a real intermediate # equivalence -my $t2 = Text::Tradition->new( 'input' => 'Self', 'file' => 't/data/legendfrag.xml' ); +my $t2; +warning_is { + $t2 = Text::Tradition->new( 'input' => 'Self', 'file' => 't/data/legendfrag.xml' ); +} 'DROPPING r14.2 -> r8.1: Cannot set relationship on a meta reading', + "Got expected relationship drop warning on parse"; my $c2 = $t2->collation; $c2->add_relationship( 'r9.2', 'r9.3', { 'type' => 'lexical' } ); my $trel2 = $c2->get_relationship( 'r9.2', 'r9.3' ); @@ -408,27 +423,21 @@ sub add_relationship { if( $options->{'scope'} ne 'local' ) { # Is there a relationship with this a & b already? # Case-insensitive for non-orthographics. - my $rdga = $options->{'type'} eq 'orthographic' - ? $options->{'reading_a'} : lc( $options->{'reading_a'} ); - my $rdgb = $options->{'type'} eq 'orthographic' - ? $options->{'reading_b'} : lc( $options->{'reading_b'} ); + my $rdga = $options->{'reading_a'}; + my $rdgb = $options->{'reading_b'}; my $otherrel = $self->scoped_relationship( $rdga, $rdgb ); if( $otherrel && $otherrel->type eq $options->{type} && $otherrel->scope eq $options->{scope} ) { - warn "Applying existing scoped relationship"; + warn "Applying existing scoped relationship for $rdga / $rdgb"; $relationship = $otherrel; + } elsif( $otherrel ) { + throw( "Conflicting scoped relationship for $rdga / $rdgb at $source / $target" ); } } $relationship = $self->create( $options ) unless $relationship; # Will throw on error } - # Find all the pairs for which we need to set the relationship. - my @vectors; - if( $relationship->colocated && $relationship->nonlocal && !$thispaironly ) { - push( @vectors, $self->_find_applicable( $relationship ) ); - } - # Now set the relationship(s). my @pairs_set; my $rel = $self->get_relationship( $source, $target ); @@ -451,19 +460,58 @@ sub add_relationship { $self->_set_relationship( $relationship, $source, $target ) unless $skip; push( @pairs_set, [ $source, $target ] ); - # Set any additional relationships that might be in @vectors. - foreach my $v ( @vectors ) { - next if $v->[0] eq $source && $v->[1] eq $target; - next if $v->[1] eq $source && $v->[0] eq $target; - my @added = $self->add_relationship( @$v, $relationship ); - push( @pairs_set, @added ); + # Find all the pairs for which we need to set the relationship. + if( $relationship->colocated && $relationship->nonlocal && !$thispaironly ) { + push( @pairs_set, $self->add_global_relationship( $relationship ) ); } - # Finally, restore whatever collations we can, and return. $self->_restore_collations( @$droppedcolls ); return @pairs_set; } +=head2 add_global_relationship( $options, $skipvector ) + +Adds the relationship specified wherever the relevant readings appear together +in the graph. Options as in add_relationship above. + +=cut + +sub add_global_relationship { + my( $self, $options ) = @_; + # First see if we are dealing with a relationship object already + my $relationship; + if( ref( $options ) eq 'Text::Tradition::Collation::Relationship' ) { + $relationship = $options; + } else { + # Then see if a scoped relationship already applies for the words. + my $scopedrel = $self->scoped_relationship( + $options->{reading_a}, $options->{reading_b} ); + $relationship = $scopedrel ? $scopedrel + : $self->create( $options ); + } + # Sanity checking + throw( "Relationship passed to add_global is not global" ) + unless $relationship->nonlocal; + throw( "Relationship passed to add_global is not a valid global type" ) + unless $relationship->colocated && $relationship->type ne 'collated'; + + # Apply the relationship wherever it is valid + my @pairs_set; + foreach my $v ( $self->_find_applicable( $relationship ) ) { + my $exists = $self->get_relationship( @$v ); + if( $exists && $exists->type ne 'collated' ) { + throw( "Found conflicting relationship at @$v" ) + unless $exists->type eq $relationship->type + && $exists->scope eq $relationship->scope; + } else { + my @added = $self->add_relationship( @$v, $relationship ); + push( @pairs_set, @added ); + } + } + return @pairs_set; +} + + =head2 del_scoped_relationship( $reading_a, $reading_b ) Returns the general (document-level or global) relationship that has been defined @@ -566,10 +614,10 @@ sub relationship_valid { my $c = $self->collation; ## Assume validity is okay if we are initializing from scratch. return ( 1, "initializing" ) unless $c->tradition->_initialized; - - if ( $rel eq 'transposition' || $rel eq 'repetition' ) { + if ( $rel eq 'transposition' || $rel eq 'repetition' ) { # Check that the two readings do (for a repetition) or do not (for # a transposition) appear in the same witness. + # TODO this might be called before witness paths are set... my %seen_wits; map { $seen_wits{$_} = 1 } $c->reading_witnesses( $source ); foreach my $w ( $c->reading_witnesses( $target ) ) { @@ -697,6 +745,9 @@ sub related_readings { # Backwards compat if( $filter eq 'colocated' ) { $filter = sub { $_[0]->colocated }; + } elsif( !ref( $filter ) ) { + my $type = $filter; + $filter = sub { $_[0]->type eq $type }; } my %found = ( $reading => 1 ); my $check = [ $reading ]; @@ -752,7 +803,7 @@ sub merge_readings { $rel = $self->get_relationship( @$edge ); $self->_set_relationship( $rel, @vector ); } - $self->_make_equivalence( $deleted, $kept, 1 ); + $self->_make_equivalence( $deleted, $kept ); } ### Equivalence logic @@ -811,28 +862,22 @@ sub _is_disconnected { # Equate two readings in the equivalence graph sub _make_equivalence { - my( $self, $source, $target, $removing ) = @_; + my( $self, $source, $target ) = @_; # Get the source equivalent readings my $seq = $self->equivalence( $source ); my $teq = $self->equivalence( $target ); # Nothing to do if they are already equivalent... return if $seq eq $teq; - # Get the readings equivalent to source - my @sourcepool = @{$self->eqreadings( $seq )}; - # If we are removing the source reading entirely, don't push - # it into the target pool. - @sourcepool = grep { $_ ne $seq } @sourcepool if $removing; + my $sourcepool = $self->eqreadings( $seq ); # and add them to the target readings. - push( @{$self->eqreadings( $teq )}, @sourcepool ); - map { $self->set_equivalence( $_, $teq ) } @sourcepool; + push( @{$self->eqreadings( $teq )}, @$sourcepool ); + map { $self->set_equivalence( $_, $teq ) } @$sourcepool; # Then merge the nodes in the equivalence graph. foreach my $pred ( $self->equivalence_graph->predecessors( $seq ) ) { - $self->equivalence_graph->add_edge( $pred, $teq ) - unless $teq eq $pred; + $self->equivalence_graph->add_edge( $pred, $teq ); } foreach my $succ ( $self->equivalence_graph->successors( $seq ) ) { - $self->equivalence_graph->add_edge( $teq, $succ ) - unless $teq eq $succ; + $self->equivalence_graph->add_edge( $teq, $succ ); } $self->equivalence_graph->delete_vertex( $seq ); # TODO enable this after collation parsing is done @@ -946,9 +991,11 @@ sub _break_equivalence { my $c = $self->collation; foreach my $rdg ( @$newmembers ) { foreach my $rp ( $c->sequence->predecessors( $rdg ) ) { + next unless $self->equivalence( $rp ); $self->equivalence_graph->add_edge( $self->equivalence( $rp ), $newgroup ); } foreach my $rs ( $c->sequence->successors( $rdg ) ) { + next unless $self->equivalence( $rs ); $self->equivalence_graph->add_edge( $newgroup, $self->equivalence( $rs ) ); } } @@ -957,9 +1004,11 @@ sub _break_equivalence { my( %old_pred, %old_succ ); foreach my $rdg ( @$oldmembers ) { foreach my $rp ( $c->sequence->predecessors( $rdg ) ) { + next unless $self->equivalence( $rp ); $old_pred{$self->equivalence( $rp )} = 1; } foreach my $rs ( $c->sequence->successors( $rdg ) ) { + next unless $self->equivalence( $rs ); $old_succ{$self->equivalence( $rs )} = 1; } } @@ -1015,6 +1064,7 @@ sub rebuild_equivalence { $self->_clear_equivalence; $self->_clear_eqreadings; + $self->collation->tradition->_init_done(0); # Add the readings foreach my $r ( $self->collation->readings ) { my $rid = $r->id; @@ -1035,6 +1085,62 @@ sub rebuild_equivalence { next unless $relobj && $relobj->colocated; $self->_make_equivalence( @$rel ); } + $self->collation->tradition->_init_done(1); +} + +=head2 equivalence_ranks + +Rank all vertices in the equivalence graph, and return a hash reference with +vertex => rank mapping. + +=cut + +sub equivalence_ranks { + my $self = shift; + my $eqstart = $self->equivalence( $self->collation->start ); + my $eqranks = { $eqstart => 0 }; + my $rankeqs = { 0 => [ $eqstart ] }; + my @curr_origin = ( $eqstart ); + # A little iterative function. + while( @curr_origin ) { + @curr_origin = $self->_assign_rank( $eqranks, $rankeqs, @curr_origin ); + } + return( $eqranks, $rankeqs ); +} + +sub _assign_rank { + my( $self, $node_ranks, $rank_nodes, @current_nodes ) = @_; + my $graph = $self->equivalence_graph; + # Look at each of the children of @current_nodes. If all the child's + # parents have a rank, assign it the highest rank + 1 and add it to + # @next_nodes. Otherwise skip it; we will return when the highest-ranked + # parent gets a rank. + my @next_nodes; + foreach my $c ( @current_nodes ) { + warn "Current reading $c has no rank!" + unless exists $node_ranks->{$c}; + foreach my $child ( $graph->successors( $c ) ) { + next if exists $node_ranks->{$child}; + my $highest_rank = -1; + my $skip = 0; + foreach my $parent ( $graph->predecessors( $child ) ) { + if( exists $node_ranks->{$parent} ) { + $highest_rank = $node_ranks->{$parent} + if $highest_rank <= $node_ranks->{$parent}; + } else { + $skip = 1; + last; + } + } + next if $skip; + my $c_rank = $highest_rank + 1; + # print STDERR "Assigning rank $c_rank to node $child \n"; + $node_ranks->{$child} = $c_rank if $node_ranks; + push( @{$rank_nodes->{$c_rank}}, $child ) if $rank_nodes; + push( @next_nodes, $child ); + } + } + return @next_nodes; } ### Output logic