X-Git-Url: http://git.shadowcat.co.uk/gitweb/gitweb.cgi?a=blobdiff_plain;f=lib%2FText%2FTradition%2FCollation%2FRelationshipStore.pm;h=d3ca9bf31f5dd85e3a0f2b68e3dca9d2d05b0fbc;hb=99ab95354ac3ce1f09b81e2b8a3fcd66fe6e83d9;hp=8517ac1314a3ec9952d660289d52cb90541c8e58;hpb=04482188230a9be8e9a1335dbfcd8e3160a5768d;p=scpubgit%2Fstemmatology.git

diff --git a/lib/Text/Tradition/Collation/RelationshipStore.pm b/lib/Text/Tradition/Collation/RelationshipStore.pm
index 8517ac1..d3ca9bf 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 )
@@ -260,21 +251,27 @@ 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;
-my $trel = $c1->get_relationship( '9,2', '9,3' );
+my $trel = $c1->get_relationship( 'r9.2', 'r9.3' );
 is( ref( $trel ), 'Text::Tradition::Collation::Relationship',
 	"Troublesome relationship exists" );
 is( $trel->type, 'collated', "Troublesome relationship is a collation" );
 
 # Try to make the link we want
 try {
-	$c1->add_relationship( '8,6', '10,3', { 'type' => 'orthographic' } );
+	$c1->add_relationship( 'r8.6', 'r10.3', { 'type' => 'orthographic' } );
 	ok( 1, "Added cross-collation relationship as expected" );
 } catch( Text::Tradition::Error $e ) {
 	ok( 0, "Existing collation blocked equivalence relationship: " . $e->message );
@@ -289,7 +286,7 @@ try {
 
 # Test 1.2: attempt merge of an identical reading
 try {
-	$c1->merge_readings( '9,3', '11,5' );
+	$c1->merge_readings( 'r9.3', 'r11.5' );
 	ok( 1, "Successfully merged reading 'pontifex'" );
 } catch ( Text::Tradition::Error $e ) {
 	ok( 0, "Merge of mergeable readings failed: $e->message" );
@@ -298,25 +295,39 @@ try {
 
 # Test 1.3: attempt relationship with a meta reading (should fail)
 try {
-	$c1->add_relationship( '8,1', '9,2', { 'type' => 'collated' } );
+	$c1->add_relationship( 'r8.1', 'r9.2', { 'type' => 'collated' } );
 	ok( 0, "Allowed a meta-reading to be used in a relationship" );
 } catch ( Text::Tradition::Error $e ) {
 	is( $e->message, 'Cannot set relationship on a meta reading', 
 		"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( '9,2', '9,3', { 'type' => 'lexical' } );
-my $trel2 = $c2->get_relationship( '9,2', '9,3' );
+$c2->add_relationship( 'r9.2', 'r9.3', { 'type' => 'lexical' } );
+my $trel2 = $c2->get_relationship( 'r9.2', 'r9.3' );
 is( ref( $trel2 ), 'Text::Tradition::Collation::Relationship',
 	"Created blocking relationship" );
 is( $trel2->type, 'lexical', "Blocking relationship is not a collation" );
 # This time the link ought to fail
 try {
-	$c2->add_relationship( '8,6', '10,3', { 'type' => 'orthographic' } );
+	$c2->add_relationship( 'r8.6', 'r10.3', { 'type' => 'orthographic' } );
 	ok( 0, "Added cross-equivalent bad relationship" );
 } catch ( Text::Tradition::Error $e ) {
 	like( $e->message, qr/witness loop/,
@@ -335,13 +346,13 @@ my $t3 = Text::Tradition->new( 'input' => 'Self', 'file' => 't/data/lf2.xml' );
 # Test 1: try to equate nodes that are prevented with an intermediate collation
 my $c3 = $t3->collation;
 try {
-	$c3->add_relationship( '36,4', '38,3', { 'type' => 'transposition' } );
+	$c3->add_relationship( 'r36.4', 'r38.3', { 'type' => 'transposition' } );
 	ok( 1, "Added straightforward transposition" );
 } catch ( Text::Tradition::Error $e ) {
 	ok( 0, "Failed to add normal transposition: " . $e->message );
 }
 try {
-	$c3->add_relationship( '36,3', '38,2', { 'type' => 'transposition' } );
+	$c3->add_relationship( 'r36.3', 'r38.2', { 'type' => 'transposition' } );
 	ok( 1, "Added straightforward transposition complement" );
 } catch ( Text::Tradition::Error $e ) {
 	ok( 0, "Failed to add normal transposition complement: " . $e->message );
@@ -349,7 +360,7 @@ try {
 
 # Test 3.2: try to make a transposition that could be a parallel.
 try {
-	$c3->add_relationship( '28,2', '29,2', { 'type' => 'transposition' } );
+	$c3->add_relationship( 'r28.2', 'r29.2', { 'type' => 'transposition' } );
 	ok( 0, "Added bad colocated transposition" );
 } catch ( Text::Tradition::Error $e ) {
 	like( $e->message, qr/Readings appear to be colocated/,
@@ -358,13 +369,13 @@ try {
 
 # Test 3.3: make the parallel, and then make the transposition again.
 try {
-	$c3->add_relationship( '28,3', '29,3', { 'type' => 'orthographic' } );
+	$c3->add_relationship( 'r28.3', 'r29.3', { 'type' => 'orthographic' } );
 	ok( 1, "Equated identical readings for transposition" );
 } catch ( Text::Tradition::Error $e ) {
 	ok( 0, "Failed to equate identical readings: " . $e->message );
 }
 try {
-	$c3->add_relationship( '28,2', '29,2', { 'type' => 'transposition' } );
+	$c3->add_relationship( 'r28.2', 'r29.2', { 'type' => 'transposition' } );
 	ok( 1, "Added straightforward transposition complement" );
 } catch ( Text::Tradition::Error $e ) {
 	ok( 0, "Failed to add normal transposition complement: " . $e->message );
@@ -415,8 +426,10 @@ sub add_relationship {
 			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
@@ -564,7 +577,9 @@ sub relationship_valid {
     my( $self, $source, $target, $rel, $mustdrop ) = @_;
     $mustdrop = [] unless $mustdrop; # in case we were passed nothing
     my $c = $self->collation;
-    if ( $rel eq 'transposition' || $rel eq 'repetition' ) {
+    ## Assume validity is okay if we are initializing from scratch.
+    return ( 1, "initializing" ) unless $c->tradition->_initialized;
+        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...
@@ -695,6 +710,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 ];
@@ -760,14 +778,14 @@ sub _remove_equivalence_node {
 	my $group = $self->equivalence( $node );
 	my $nodelist = $self->eqreadings( $group );
 	if( @$nodelist == 1 && $nodelist->[0] eq $node ) {
-		print STDERR "Removing equivalence $group for $node\n" if $node eq '451,2';
+		$self->equivalence_graph->delete_vertex( $group );
 		$self->remove_eqreadings( $group );
+		$self->remove_equivalence( $group );
 	} elsif( @$nodelist == 1 ) {
-		warn "DATA INCONSISTENCY in equivalence graph: " . $nodelist->[0] .
-			" in group that should have only $node";
+		throw( "DATA INCONSISTENCY in equivalence graph: " . $nodelist->[0] .
+			" in group that should have only $node" );
 	} else {
-		print STDERR "Removing $node from equivalence $group\n" if $node eq '451,2';
-		my @newlist = grep { $_ ne $node } @$nodelist;
+ 		my @newlist = grep { $_ ne $node } @$nodelist;
 		$self->set_eqreadings( $group, \@newlist );
 		$self->remove_equivalence( $node );
 	}
@@ -798,8 +816,6 @@ sub delete_equivalence_edge {
 	my( $self, $source, $target ) = @_;
 	my $seq = $self->equivalence( $source );
 	my $teq = $self->equivalence( $target );
-	print STDERR "Deleting equivalence edge $seq -> $teq for $source -> $target\n"
-		if grep { $_ eq '451,2' } @_;
 	$self->equivalence_graph->delete_edge( $seq, $teq );
 }
 
@@ -817,12 +833,8 @@ sub _make_equivalence {
 	my $teq = $self->equivalence( $target );
 	# Nothing to do if they are already equivalent...
 	return if $seq eq $teq;
-	print STDERR "Making equivalence for $source -> $target\n"
-		if grep { $_ eq '451,2' } @_;
 	my $sourcepool = $self->eqreadings( $seq );
 	# and add them to the target readings.
-	print STDERR "Moving readings '@$sourcepool' from group $seq to $teq\n"
-		if grep { $_ eq '451,2' } @_;	
 	push( @{$self->eqreadings( $teq )}, @$sourcepool );
 	map { $self->set_equivalence( $_, $teq ) } @$sourcepool;
 	# Then merge the nodes in the equivalence graph.
@@ -834,8 +846,8 @@ sub _make_equivalence {
 	}
 	$self->equivalence_graph->delete_vertex( $seq );
 	# TODO enable this after collation parsing is done
-# 	throw( "Graph got disconnected making $source / $target equivalence" )
-# 		if $self->_is_disconnected;
+	throw( "Graph got disconnected making $source / $target equivalence" )
+		if $self->_is_disconnected && $self->collation->tradition->_initialized;
 }
 
 =head2 test_equivalence
@@ -910,14 +922,8 @@ sub _break_equivalence {
 	map { $tng{$_} = 1 } $self->_find_equiv_without( $target, $source );
 	# If these groups intersect, they are still connected; do nothing.
 	foreach my $el ( keys %tng ) {
-		if( exists $sng{$el} ) {
-			print STDERR "Equivalence break $source / $target is a noop\n"
-				if grep { $_ eq '451,2' } @_;
-			return;
-		}
+		return if( exists $sng{$el} );
 	}
-	print STDERR "Breaking equivalence $source / $target\n"
-		if grep { $_ eq '451,2' } @_;
 	# If they don't intersect, then we split the nodes in the graph and in
 	# the hashes. First figure out which group has which name
 	my $oldgroup = $self->equivalence( $source ); # same as $target
@@ -950,9 +956,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 ) );
 		}
 	}
@@ -961,9 +969,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;
 		}
 	}
@@ -978,8 +988,8 @@ sub _break_equivalence {
 		}
 	}
 	# TODO enable this after collation parsing is done
-# 	throw( "Graph got disconnected breaking $source / $target equivalence" )
-# 		if $self->_is_disconnected;
+	throw( "Graph got disconnected breaking $source / $target equivalence" )
+		if $self->_is_disconnected && $self->collation->tradition->_initialized;
 }
 
 sub _find_equiv_without {
@@ -1041,6 +1051,61 @@ sub rebuild_equivalence {
 	}
 }
 
+=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
 
 sub _as_graphml {