X-Git-Url: http://git.shadowcat.co.uk/gitweb/gitweb.cgi?a=blobdiff_plain;f=lib%2FText%2FTradition%2FCollation%2FRelationshipStore.pm;h=3d98174fa5420692e639e73299ee8fdacd5838f1;hb=13e893dc2c0d9e482e4a8576d7c7d59e88866669;hp=2479d08193e92240f2e3f163bf4c790b7d100e79;hpb=83d5ac3af5c70f09ee081885efcba827fcef4cb4;p=scpubgit%2Fstemmatology.git

diff --git a/lib/Text/Tradition/Collation/RelationshipStore.pm b/lib/Text/Tradition/Collation/RelationshipStore.pm
index 2479d08..3d98174 100644
--- a/lib/Text/Tradition/Collation/RelationshipStore.pm
+++ b/lib/Text/Tradition/Collation/RelationshipStore.pm
@@ -2,13 +2,16 @@ package Text::Tradition::Collation::RelationshipStore;
 
 use strict;
 use warnings;
+use Text::Tradition::Error;
 use Text::Tradition::Collation::Relationship;
+use TryCatch;
 
 use Moose;
 
 =head1 NAME
 
-Text::Tradition::Collation::Reading - represents a reading (usually a word) in a collation.
+Text::Tradition::Collation::RelationshipStore - Keeps track of the relationships
+between readings in a given collation
     
 =head1 DESCRIPTION
 
@@ -17,6 +20,39 @@ texts, particularly medieval ones.  The RelationshipStore is an internal object
 of the collation, to keep track of the defined relationships (both specific and
 general) between readings.
 
+=begin testing
+
+use Text::Tradition;
+use TryCatch;
+
+use_ok( 'Text::Tradition::Collation::RelationshipStore' );
+
+# Add some relationships, and delete them
+
+my $cxfile = 't/data/Collatex-16.xml';
+my $t = Text::Tradition->new( 
+    'name'  => 'inline', 
+    'input' => 'CollateX',
+    'file'  => $cxfile,
+    );
+my $c = $t->collation;
+
+my @v1 = $c->add_relationship( 'n21', 'n22', { 'type' => 'lexical' } );
+is( scalar @v1, 1, "Added a single relationship" );
+is( $v1[0]->[0], 'n21', "Got correct node 1" );
+is( $v1[0]->[1], 'n22', "Got correct node 2" );
+my @v2 = $c->add_relationship( 'n24', 'n23', 
+	{ 'type' => 'spelling', 'scope' => 'global' } );
+is( scalar @v2, 2, "Added a global relationship with two instances" );
+@v1 = $c->del_relationship( 'n22', 'n21' );
+is( scalar @v1, 1, "Deleted first relationship" );
+@v2 = $c->del_relationship( 'n12', 'n13' );
+is( scalar @v2, 2, "Deleted second global relationship" );
+my @v3 = $c->del_relationship( 'n1', 'n2' );
+is( scalar @v3, 0, "Nothing deleted on non-existent relationship" );
+
+=end testing
+
 =head1 METHODS
 
 =head2 new( collation => $collation );
@@ -49,6 +85,35 @@ has 'graph' => (
     },
 	);
 	
+=head2 get_relationship
+
+Return the relationship object, if any, that exists between two readings.
+
+=cut
+
+sub get_relationship {
+	my $self = shift;
+	my @vector;
+	if( @_ == 1 && ref( $_[0] ) eq 'ARRAY' ) {
+		# Dereference the edge arrayref that was passed.
+		my $edge = shift;
+		@vector = @$edge;
+	} else {
+		@vector = @_;
+	}
+	my $relationship;
+	if( $self->graph->has_edge_attribute( @vector, 'object' ) ) {
+		$relationship = $self->graph->get_edge_attribute( @vector, 'object' );
+	} 
+	return $relationship;
+}
+
+sub _set_relationship {
+	my( $self, $relationship, @vector ) = @_;
+	$self->graph->add_edge( @vector );
+	$self->graph->set_edge_attribute( @vector, 'object', $relationship );
+}
+
 =head2 create
 
 Create a new relationship with the given options and return it.
@@ -61,13 +126,15 @@ sub create {
 	# Check to see if a relationship exists between the two given readings
 	my $source = delete $options->{'orig_a'};
 	my $target = delete $options->{'orig_b'};
-	my $rel;
-	if( $self->graph->has_edge( $source, $target ) ) {
-		$rel = $self->graph->get_edge_attribute( $source, $target, 'object' );
-		if( $rel->type ne $options->type ) {
-			warn "Relationship of type " . $rel->type 
-				. "already exists between $source and $target";
-			return;
+	my $rel = $self->get_relationship( $source, $target );
+	if( $rel ) {
+		if( $rel->type eq 'collated' ) {
+			# Always replace a 'collated' relationship with a more descriptive
+			# one, if asked.
+			$self->del_relationship( $source, $target );
+		} elsif( $rel->type ne $options->{'type'} ) {
+			throw( "Another relationship of type " . $rel->type 
+				. " already exists between $source and $target" );
 		} else {
 			return $rel;
 		}
@@ -79,8 +146,7 @@ sub create {
 	if( $rel && $rel->type eq $options->{'type'} ) {
 		return $rel;
 	} elsif( $rel ) {
-		warn 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'} );
-		return;
+		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;
@@ -97,13 +163,16 @@ non-locally.  Key on whichever reading occurs first alphabetically.
 
 sub add_scoped_relationship {
 	my( $self, $rel ) = @_;
-	my $r = $self->scoped_relationship( $rel->reading_a, $rel->reading_b );
+	my $rdga = $rel->type eq 'orthographic' ? $rel->reading_a : lc( $rel->reading_a );
+	my $rdgb = $rel->type eq 'orthographic' ? $rel->reading_b : lc( $rel->reading_b );	
+	my $r = $self->scoped_relationship( $rdga, $rdgb );
 	if( $r ) {
 		warn sprintf( "Scoped relationship of type %s already exists between %s and %s",
-			$r->type, $rel->reading_a, $rel->reading_b );
+			$r->type, $rdga, $rdgb );
 		return;
 	}
-	$self->scopedrels->{$rel->reading_a}->{$rel->reading_b} = $rel;
+	my( $first, $second ) = sort ( $rdga, $rdgb );
+	$self->scopedrels->{$first}->{$second} = $rel;
 }
 
 =head2 scoped_relationship( $reading_a, $reading_b )
@@ -138,68 +207,165 @@ add_relationship.
 sub add_relationship {
 	my( $self, $source, $source_rdg, $target, $target_rdg, $options ) = @_;
 
-	# Check the options
-	$options->{'scope'} = 'local' unless $options->{'scope'};
-	
-	my( $is_valid, $reason ) = 
-		$self->relationship_valid( $source, $target, $options->{'type'} );
-    unless( $is_valid ) {
-        return ( undef, $reason );
+	my $relationship;
+	my $thispaironly;
+	if( ref( $options ) eq 'Text::Tradition::Collation::Relationship' ) {
+		$relationship = $options;
+		$thispaironly = 1;  # If existing rel, set only where asked.
+	} else {
+		# Check the options
+		$options->{'scope'} = 'local' unless $options->{'scope'};
+		$options->{'scope'} = 'local' if $options->{'type'} eq 'collated';
+		$options->{'scope'} = 'local' if $options->{'type'} eq 'transposition';
+		
+		my( $is_valid, $reason ) = 
+			$self->relationship_valid( $source, $target, $options->{'type'} );
+		unless( $is_valid ) {
+			throw( "Invalid relationship: $reason" );
+		}
+		
+		# Try to create the relationship object.
+		$options->{'reading_a'} = $source_rdg->text;
+		$options->{'reading_b'} = $target_rdg->text;
+		$options->{'orig_a'} = $source;
+		$options->{'orig_b'} = $target;
+    	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 $otherrel = $self->scoped_relationship( $rdga, $rdgb );
+			if( $otherrel && $otherrel->type eq $options->{type}
+				&& $otherrel->scope eq $options->{scope} ) {
+				warn "Applying existing scoped relationship";
+				$relationship = $otherrel;
+			}
+    	}
+		$relationship = $self->create( $options ) unless $relationship;  # Will throw on error
     }
-    
-    # Try to create the relationship object.
-    $options->{'reading_a'} = $source_rdg->text;
-    $options->{'reading_b'} = $target_rdg->text;
-    $options->{'orig_a'} = $source;
-    $options->{'orig_b'} = $target;
-    my $relationship = $self->create( $options );
-	return( undef, "Relationship creation failed" ) unless $relationship;
+
 
 	# Find all the pairs for which we need to set the relationship.
-	my @vectors = ( [ $source, $target ] );	
-    if( $relationship->colocated && $relationship->nonlocal ) {
-    	my $c = $self->collation;
-    	# Set the same relationship everywhere we can, throughout the graph.
-    	my @identical_readings = grep { $_->text eq $relationship->reading_a }
-    		$c->readings;
-    	foreach my $ir ( @identical_readings ) {
-    		next if $ir->id eq $source;
-    		# Check to see if there is a target reading with the same text at
-    		# the same rank.
-    		my @itarget = grep 
-    			{ $_->rank == $ir->rank && $_->text eq $relationship->reading_b }
-    			$c->readings;
-    		if( @itarget ) {
-    			# We found a hit.
-    			warn "More than one reading with text " . $target_rdg->text
-    				. " at rank " . $ir->rank . "!" if @itarget > 1;
-    			push( @vectors, [ $ir->id, $itarget[0]->id ] );
-    		}
-    	}	
+	my @vectors = [ $source, $target ];
+    if( $relationship->colocated && $relationship->nonlocal && !$thispaironly ) {
+    	push( @vectors, $self->_find_applicable( $relationship ) );
     }
-    
+        
     # Now set the relationship(s).
     my @pairs_set;
     foreach my $v ( @vectors ) {
-    	if( $self->graph->has_edge( @$v ) ) {
-    		# Is it locally scoped?
-    		my $rel = $self->graph->get_edge_attribute( @$v );
+		my $rel = $self->get_relationship( @$v );
+    	if( $rel && $rel ne $relationship ) {
     		if( $rel->nonlocal ) {
-    			# TODO I think we should not be able to get here.
-    			warn "Found conflicting relationship at @$v";
-    		} else {
-    			warn "Not overriding local relationship set at @$v";
-    			next;
+    			throw( "Found conflicting relationship at @$v" );
+    		} elsif( $rel->type ne 'collated' ) {
+    			# Replace a collation relationship; leave any other sort in place.
+    			my $r1ann = $rel->has_annotation ? $rel->annotation : '';
+    			my $r2ann = $relationship->has_annotation ? $relationship->annotation : '';
+    			unless( $rel->type eq $relationship->type && $r1ann eq $r2ann ) {
+					warn sprintf( "Not overriding local relationship %s with global %s " 
+						. "set at %s -> %s (%s -> %s)", $rel->type, $relationship->type,
+						@$v, $rel->reading_a, $rel->reading_b );
+					next;
+				}
     		}
     	}
-    	$self->graph->add_edge( @$v );
-    	$self->graph->set_edge_attribute( @$v, 'object', $relationship );
+    	map { $self->_drop_collations( $_ ) } @$v;
+    	$self->_set_relationship( $relationship, @$v );
     	push( @pairs_set, $v );
     }
     
-    return( 1, @pairs_set );
+    return @pairs_set;
+}
+
+=head2 del_scoped_relationship( $reading_a, $reading_b )
+
+Returns the general (document-level or global) relationship that has been defined 
+between the two reading strings. Returns undef if there is no general relationship.
+
+=cut
+
+sub del_scoped_relationship {
+	my( $self, $rdga, $rdgb ) = @_;
+	my( $first, $second ) = sort( $rdga, $rdgb );
+	return delete $self->scopedrels->{$first}->{$second};
+}
+
+sub _find_applicable {
+	my( $self, $rel ) = @_;
+	my $c = $self->collation;
+	# TODO Someday we might use a case sensitive language.
+	my $lang = $c->tradition->language;
+	my @vectors;
+	my @identical_readings;
+	if( $rel->type eq 'orthographic' ) {
+		@identical_readings = grep { $_->text eq $rel->reading_a } 
+			$c->readings;
+	} else {
+		@identical_readings = grep { lc( $_->text ) eq lc( $rel->reading_a ) }
+			$c->readings;
+	}
+	foreach my $ir ( @identical_readings ) {
+		my @itarget;
+		if( $rel->type eq 'orthographic' ) {
+			@itarget = grep { $_->rank == $ir->rank 
+							  && $_->text eq $rel->reading_b } $c->readings;
+		} else {
+			@itarget = grep { $_->rank == $ir->rank 
+							  && lc( $_->text ) eq lc( $rel->reading_b ) } $c->readings;
+		}
+		if( @itarget ) {
+			# Warn if there is more than one hit with no orth link between them.
+			my $itmain = shift @itarget;
+			if( @itarget ) {
+				my %all_targets;
+				map { $all_targets{$_} = 1 } @itarget;
+				map { delete $all_targets{$_} } 
+					$self->related_readings( $itmain, 
+						sub { $_[0]->type eq 'orthographic' } );
+    			warn "More than one unrelated reading with text " . $itmain->text
+    				. " at rank " . $ir->rank . "!" if keys %all_targets;
+			}
+			push( @vectors, [ $ir->id, $itmain->id ] );
+		}
+	}
+	return @vectors;
 }
 
+=head2 del_relationship( $source, $target )
+
+Removes the relationship between the given readings. If the relationship is
+non-local, removes the relationship everywhere in the graph.
+
+=cut
+
+sub del_relationship {
+	my( $self, $source, $target ) = @_;
+	my $rel = $self->get_relationship( $source, $target );
+	return () unless $rel; # Nothing to delete; return an empty set.
+	my @vectors = ( [ $source, $target ] );
+	$self->_remove_relationship( $source, $target );
+	if( $rel->nonlocal ) {
+		# Remove the relationship wherever it occurs.
+		# Remove the relationship wherever it occurs.
+		my @rel_edges = grep { $self->get_relationship( @$_ ) == $rel }
+			$self->relationships;
+		foreach my $re ( @rel_edges ) {
+			$self->_remove_relationship( @$re );
+			push( @vectors, $re );
+		}
+		$self->del_scoped_relationship( $rel->reading_a, $rel->reading_b );
+	}
+	return @vectors;
+}
+
+sub _remove_relationship {
+	my( $self, @vector ) = @_;
+	$self->graph->delete_edge( @vector );
+}
+	
 =head2 relationship_valid( $source, $target, $type )
 
 Checks whether a relationship of type $type may exist between the readings given
@@ -214,6 +380,10 @@ sub relationship_valid {
     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.
+		# If we haven't made reading paths yet, take it on faith.
+		return( 1, "no paths yet" ) unless $c->sequence->successors( $c->start );
+		
+		# We have some paths, so carry on.
 		my %seen_wits;
 		map { $seen_wits{$_} = 1 } $c->reading_witnesses( $source );
 		foreach my $w ( $c->reading_witnesses( $target ) ) {
@@ -221,61 +391,154 @@ sub relationship_valid {
 				return ( 0, "Readings both occur in witness $w" ) 
 					if $rel eq 'transposition';
 				return ( 1, "ok" ) if $rel eq 'repetition';
+			}
+		}
+		# For transpositions, there should also be a path from one reading
+		# to the other.
+		if( $rel eq 'transposition' ) {
+			my( %sourceseq, %targetseq );
+			map { $sourceseq{$_} = 1 } $c->sequence->all_successors( $source );
+			map { $targetseq{$_} = 1 } $c->sequence->all_successors( $target );
+			return( 0, "Readings are parallel" )
+				unless $sourceseq{$target} || $targetseq{$source};
 		}
 		return $rel eq 'transposition' ? ( 1, "ok" )
 			: ( 0, "Readings occur only in distinct witnesses" );
-		}
-	} else {
+	} 
+	if( $rel ne 'repetition' ) {
 		# Check that linking the source and target in a relationship won't lead
-		# to a path loop for any witness.  First make a lookup table of all the
+		# to a path loop for any witness.  If they have the same rank then
+		# they are parallel by definition.
+		# For transpositions, we want the opposite result: it is only valid if
+		# the readings cannot be parallel.
+		my $sourcerank = $c->reading( $source )->has_rank
+			? $c->reading( $source )->rank : undef;
+		my $targetrank = $c->reading( $target )->has_rank
+			? $c->reading( $target )->rank : undef;
+		if( $sourcerank && $targetrank && $sourcerank == $targetrank ) {
+			return( 0, "Cannot transpose readings of same rank" )
+				if $rel eq 'transposition';
+			return( 1, "ok" );
+		}
+		
+		# Otherwise, first make a lookup table of all the
 		# readings related to either the source or the target.
 		my @proposed_related = ( $source, $target );
-		push( @proposed_related, $self->related_readings( $source, 'colocated' ) );
-		push( @proposed_related, $self->related_readings( $target, 'colocated' ) );
+		# Drop the collation links of source and target, unless we want to
+		# add a collation relationship.
+		my @dropped;
+		foreach my $r ( ( $source, $target ) ) {
+			push( @dropped, $self->_drop_collations( $r ) )
+				unless $rel eq 'collated';
+			push( @proposed_related, $self->related_readings( $r, 'colocated' ) );
+		}
+		# Also drop any collation links at intermediate ranks.
+		foreach my $rank ( $sourcerank+1 .. $targetrank-1 ) {
+			map { push( @dropped, $self->_drop_collations( $_ ) ) }
+				$c->readings_at_rank( $rank );
+		}
 		my %pr_ids;
 		map { $pr_ids{ $_ } = 1 } @proposed_related;
 	
-		# None of these proposed related readings should have a neighbor that
-		# is also in proposed_related.
+		# The cumulative predecessors and successors of the proposed-related readings
+		# should not overlap.
+		my %all_pred;
+		my %all_succ;
 		foreach my $pr ( keys %pr_ids ) {
-			foreach my $neighbor( $c->sequence->neighbors( $pr ) ) {
-				return( 0, "Would relate neighboring readings $pr and $neighbor" )
-					if exists $pr_ids{$neighbor};
+			map { $all_pred{$_} = 1 } $c->sequence->all_predecessors( $pr );
+			map { $all_succ{$_} = 1 } $c->sequence->all_successors( $pr );
+		}
+		foreach my $k ( keys %all_pred ) {
+			if( exists $all_succ{$k} ) {
+				$self->_restore_collations( @dropped );
+				return( 1, "ok" ) if $rel eq 'transposition';
+				return( 0, "Relationship would create witness loop" );
+			}
+		}
+		foreach my $k ( keys %pr_ids ) {
+			if( exists $all_pred{$k} || exists $all_succ{$k} ) {
+				$self->_restore_collations( @dropped );
+				return( 1, "ok" ) if $rel eq 'transposition';
+				return( 0, "Relationship would create witness loop" );
 			}
-		}		
+		}
+		if( $rel eq 'transposition' ) {
+			$self->_restore_collations( @dropped );
+			return ( 0, "Cannot transpose parallel readings" );
+		}
 		return ( 1, "ok" );
 	}
 }
 
-=head2 related_readings( $reading, $colocated_only )
+sub _drop_collations {
+	my( $self, $reading ) = @_;
+	my @deleted;
+	foreach my $n ( $self->graph->neighbors( $reading ) ) {
+		if( $self->get_relationship( $reading, $n )->type eq 'collated' ) {
+			$self->del_relationship( $reading, $n );
+			push( @deleted, [ $reading, $n ] );
+		}
+	}
+	return @deleted;
+}
+
+sub _restore_collations {
+	my( $self, @vectors ) = @_;
+	foreach my $v ( @vectors ) {
+		try {
+			$self->add_relationship( @$v, { 'type' => 'collated' } );
+		} catch ( Text::Tradition::Error $e ) {
+			warn "Could not restore collation " . join( ' -> ', @$v );
+		}
+	}
+}
+
+=head2 related_readings( $reading, $filter )
 
 Returns a list of readings that are connected via relationship links to $reading.
-If $colocated_only is true, restricts the list to those readings that are in the
-same logical location (and therefore have the same rank in the collation graph.)
+If $filter is set to a subroutine ref, returns only those related readings where
+$filter( $relationship ) returns a true value.
 
 =cut
 
 sub related_readings {
-	my( $self, $reading, $colocated ) = @_;
+	my( $self, $reading, $filter ) = @_;
 	my $return_object;
 	if( ref( $reading ) eq 'Text::Tradition::Collation::Reading' ) {
 		$reading = $reading->id;
 		$return_object = 1;
 	}
-	my @related = $self->graph->all_reachable( $reading );
-	if( $colocated ) {
-		my @colo;
-		foreach my $r ( @related ) {
-			my $obj = $self->graph->get_edge_attribute( $reading, $r, 'object' );
-			push( @colo, $r ) if $obj->colocated;
+	my @answer;
+	if( $filter ) {
+		# Backwards compat
+		if( $filter eq 'colocated' ) {
+			$filter = sub { $_[0]->colocated };
+		}
+		my %found = ( $reading => 1 );
+		my $check = [ $reading ];
+		my $iter = 0;
+		while( @$check ) {
+			my $more = [];
+			foreach my $r ( @$check ) {
+				foreach my $nr ( $self->graph->neighbors( $r ) ) {
+					if( &$filter( $self->get_relationship( $r, $nr ) ) ) {
+						push( @$more, $nr ) unless exists $found{$nr};
+						$found{$nr} = 1;
+					}
+				}
+			}
+			$check = $more;
 		}
-		@related = @colo;
+		delete $found{$reading};
+		@answer = keys %found;
+	} else {
+		@answer = $self->graph->all_reachable( $reading );
 	}
 	if( $return_object ) {
 		my $c = $self->collation;
-		return map { $c->reading( $_ ) } @related;
+		return map { $c->reading( $_ ) } @answer;
 	} else {
-		return @related;
+		return @answer;
 	}
 }
 
@@ -288,6 +551,8 @@ stops tracking the to-be-deleted reading.
 
 sub merge_readings {
 	my( $self, $kept, $deleted, $combined ) = @_;
+	# Delete any relationship between kept and deleted
+	$self->del_relationship( $kept, $deleted );
 	foreach my $edge ( $self->graph->edges_at( $deleted ) ) {
 		# Get the pair of kept / rel
 		my @vector = ( $kept );
@@ -297,22 +562,76 @@ sub merge_readings {
 		# If kept changes its text, drop the relationship.
 		next if $combined;
 			
-		# If kept / rel already has a relationship, warn and keep the old
-		if( $self->graph->has_edge( @vector ) ) {
-			warn sprintf( "Readings %s and %s have existing relationship; dropping link with %s", @vector, $deleted );
-			next;
-		}
+		# If kept / rel already has a relationship, just keep the old
+		my $rel = $self->get_relationship( @vector );
+		next if $rel;
 		
 		# Otherwise, adopt the relationship that would be deleted.
-		my $rel = $self->graph->get_edge_attribute( @$edge, 'object' );
-		$self->graph->add_edge( @vector );
-		$self->graph->set_edge_attribute( @vector, 'object', $rel );
+		$rel = $self->get_relationship( @$edge );
+		$self->_set_relationship( $rel, @vector );
 	}
 	$self->delete_reading( $deleted );
 }
 
-sub as_graphml { ## TODO
-	return;
+sub _as_graphml { 
+	my( $self, $graphml_ns, $xmlroot, $node_hash, $nodeid_key, $edge_keys ) = @_;
+	
+    my $rgraph = $xmlroot->addNewChild( $graphml_ns, 'graph' );
+	$rgraph->setAttribute( 'edgedefault', 'directed' );
+    $rgraph->setAttribute( 'id', 'relationships', );
+    $rgraph->setAttribute( 'parse.edgeids', 'canonical' );
+    $rgraph->setAttribute( 'parse.edges', scalar($self->graph->edges) );
+    $rgraph->setAttribute( 'parse.nodeids', 'canonical' );
+    $rgraph->setAttribute( 'parse.nodes', scalar($self->graph->vertices) );
+    $rgraph->setAttribute( 'parse.order', 'nodesfirst' );
+    
+    # Add the vertices according to their XML IDs
+    my %rdg_lookup = ( reverse %$node_hash );
+    foreach my $n ( sort _by_xmlid keys( %rdg_lookup ) ) {
+    	my $n_el = $rgraph->addNewChild( $graphml_ns, 'node' );
+    	$n_el->setAttribute( 'id', $n );
+    	_add_graphml_data( $n_el, $nodeid_key, $rdg_lookup{$n} );
+    }
+    
+    # Add the relationship edges, with their object information
+    my $edge_ctr = 0;
+    foreach my $e ( sort { $a->[0] cmp $b->[0] } $self->graph->edges ) {
+    	# Add an edge and fill in its relationship info.
+		my $edge_el = $rgraph->addNewChild( $graphml_ns, 'edge' );
+		$edge_el->setAttribute( 'source', $node_hash->{$e->[0]} );
+		$edge_el->setAttribute( 'target', $node_hash->{$e->[1]} );
+		$edge_el->setAttribute( 'id', 'e'.$edge_ctr++ );
+
+		my $rel_obj = $self->get_relationship( @$e );
+		foreach my $key ( keys %$edge_keys ) {
+			my $value = $rel_obj->$key;
+			_add_graphml_data( $edge_el, $edge_keys->{$key}, $value ) 
+				if defined $value;
+		}
+	}
+}
+
+sub _by_xmlid {
+	my $tmp_a = $a;
+	my $tmp_b = $b;
+	$tmp_a =~ s/\D//g;
+	$tmp_b =~ s/\D//g;
+	return $tmp_a <=> $tmp_b;
+}
+
+sub _add_graphml_data {
+    my( $el, $key, $value ) = @_;
+    return unless defined $value;
+    my $data_el = $el->addNewChild( $el->namespaceURI, 'data' );
+    $data_el->setAttribute( 'key', $key );
+    $data_el->appendText( $value );
+}
+
+sub throw {
+	Text::Tradition::Error->throw( 
+		'ident' => 'Relationship error',
+		'message' => $_[0],
+		);
 }
 
 no Moose;