let stexaminer run without IDP server reachable
[scpubgit/stemmatology.git] / lib / Text / Tradition / Analysis.pm
index bcede08..d9612d7 100644 (file)
@@ -2,18 +2,24 @@ package Text::Tradition::Analysis;
 
 use strict;
 use warnings;
-use Benchmark;
-use Encode qw/ encode_utf8 /;
+use Algorithm::Diff;  # for word similarity measure
+use Encode qw/ decode_utf8 encode_utf8 /;
 use Exporter 'import';
 use Graph;
-use JSON qw/ encode_json decode_json /;
+use JSON qw/ to_json decode_json /;
 use LWP::UserAgent;
-use Text::Tradition;
+use Set::Scalar;
+use Text::Tradition::Analysis::Result;
+use Text::Tradition::Directory;
 use Text::Tradition::Stemma;
+use TryCatch;
 
 use vars qw/ @EXPORT_OK /;
 @EXPORT_OK = qw/ run_analysis group_variants analyze_variant_location wit_stringify /;
 
+my $SOLVER_URL = 'http://byzantini.st/cgi-bin/graphcalc.cgi';
+my $unsolved_problems = {};
+
 =head1 NAME
 
 Text::Tradition::Analysis - functions for stemma analysis of a tradition
@@ -103,7 +109,7 @@ my %expected_genealogical = (
        243 => 1,
 );
 
-my $data = run_analysis( $tradition );
+my $data = run_analysis( $tradition, calcdsn => 'dbi:SQLite:dbname=t/data/analysis.db' );
 my $c = $tradition->collation;
 foreach my $row ( @{$data->{'variants'}} ) {
        # Account for rows that used to be "not useful"
@@ -137,10 +143,25 @@ is( $data->{'variant_count'}, 58, "Got right total variant number" );
 sub run_analysis {
        my( $tradition, %opts ) = @_;
        my $c = $tradition->collation;
+       my $aclabel = $c->ac_label;
 
        my $stemma_id = $opts{'stemma_id'} || 0;
        my @ranks = ref( $opts{'ranks'} ) eq 'ARRAY' ? @{$opts{'ranks'}} : ();
-       my @collapse = ref( $opts{'merge_types'} ) eq 'ARRAY' ? @{$opts{'merge_types'}} : ();
+       my $collapse = Set::Scalar->new();
+       if( $opts{'merge_types'} && ref( $opts{'merge_types'} ) eq 'ARRAY' ) {
+               $collapse->insert( @{$opts{'merge_types'}} );
+       } elsif( $opts{'merge_types'} ) {
+               $collapse->insert( $opts{'merge_types'} );
+       }
+       
+       # Make sure we have a lookup DB for graph calculation results; this will die
+       # if calcdir or calcdsn isn't passed.
+       my $dir;
+       if( exists $opts{'calcdir'} ) {
+               $dir = delete $opts{'calcdir'}
+       } elsif ( exists $opts{'calcdsn'} ) {
+               $dir = Text::Tradition::Directory->new( dsn => $opts{'calcdsn'} );
+       }
 
        # Get the stemma        
        my $stemma = $tradition->stemma( $stemma_id );
@@ -148,9 +169,10 @@ sub run_analysis {
        # Figure out which witnesses we are working with - that is, the ones that
        # appear both in the stemma and in the tradition. All others are 'lacunose'
        # for our purposes.
-       my @lacunose = $stemma->hypotheticals;
-       my @tradition_wits = map { $_->sigil } $tradition->witnesses;
-       push( @lacunose, _symmdiff( [ $stemma->witnesses ], \@tradition_wits ) );
+       my $lacunose = Set::Scalar->new( $stemma->hypotheticals );
+       my $stemma_wits = Set::Scalar->new( $stemma->witnesses );
+       my $tradition_wits = Set::Scalar->new( map { $_->sigil } $tradition->witnesses );
+       $lacunose->insert( $stemma_wits->symmetric_difference( $tradition_wits )->members );
 
        # Find and mark 'common' ranks for exclusion, unless they were
        # explicitly specified.
@@ -168,27 +190,40 @@ sub run_analysis {
        my %lacunae;
        my $moved = {};
        foreach my $rank ( @ranks ) {
-               my $missing = [ @lacunose ];
-               my $rankgroup = group_variants( $tradition, $rank, $missing, $moved, \@collapse );
+               my $missing = $lacunose->clone();
+               my $rankgroup = group_variants( $tradition, $rank, $missing, $moved, $collapse );
                # Filter out any empty rankgroups 
                # (e.g. from the later rank for a transposition)
                next unless keys %$rankgroup;
+               # Get the graph for this rankgroup
+               my $rankgraph = _graph_for_grouping( $stemma, $rankgroup, $missing, $aclabel );
                if( $opts{'exclude_type1'} ) {
                        # Check to see whether this is a "useful" group.
-                       my( $rdgs, $grps ) = _useful_variant( $rankgroup, 
-                               $stemma->graph, $c->ac_label );
-                       next unless @$rdgs;
+                       next unless _useful_variant( $rankgroup, $rankgraph, $aclabel );
                }
                push( @use_ranks, $rank );
-               push( @groups, $rankgroup );
+               push( @groups, { grouping => $rankgroup, graph => $rankgraph } );
                $lacunae{$rank} = $missing;
        }
        # Run the solver
-       my $answer = solve_variants( $stemma, @groups );
+       my $answer;
+       try {
+               $answer = solve_variants( $dir, @groups );
+       } catch ( Text::Tradition::Error $e ) {
+               if( $e->message =~ /IDP/ ) {
+                       # Something is wrong with the solver; make the variants table anyway
+                       $answer->{'variants'} = [];
+                       map { push( @{$answer->{'variants'}}, _init_unsolved( $_, 'IDP error' ) ) }
+                               @groups;
+               } else {
+                       # Something else is wrong; error out.
+                       $e->throw;
+               }
+       }
 
        # Do further analysis on the answer
        my $conflict_count = 0;
-       my $aclabel = $c->ac_label;
+       my $reversion_count = 0;
        foreach my $idx ( 0 .. $#use_ranks ) {
                my $location = $answer->{'variants'}->[$idx];
                # Add the rank back in
@@ -200,39 +235,52 @@ sub run_analysis {
                $location->{'missing'} = [ keys %lmiss ];
                
                # Run the extra analysis we need.
-               analyze_location( $tradition, $stemma->graph, $location, \%lmiss );
+               ## TODO We run through all the variants in this call, so
+               ## why not add the reading data there instead of here below?
+               my $graph = $groups[$idx]->{graph};
+               analyze_location( $tradition, $graph, $location, \%lmiss );
 
+               my @layerwits;
                # Do the final post-analysis tidying up of the data.
                foreach my $rdghash ( @{$location->{'readings'}} ) {
-                       $conflict_count++ 
-                               if exists $rdghash->{'conflict'} && $rdghash->{'conflict'};
+                       $conflict_count++ if $rdghash->{'is_conflict'};
+                       $reversion_count++ if $rdghash->{'is_reverted'};
                        # Add the reading text back in, setting display value as needed
                        my $rdg = $c->reading( $rdghash->{'readingid'} );
                        if( $rdg ) {
                                $rdghash->{'text'} = $rdg->text . 
                                        ( $rdg->rank == $rank ? '' : ' [' . $rdg->rank . ']' );
+                               $rdghash->{'is_ungrammatical'} = $rdg->grammar_invalid;
+                               $rdghash->{'is_nonsense'} = $rdg->is_nonsense;
                        }
                        # Remove lacunose witnesses from this reading's list now that the
                        # analysis is done 
                        my @realgroup;
                        map { push( @realgroup, $_ ) unless $lmiss{$_} } @{$rdghash->{'group'}};
                        $rdghash->{'group'} = \@realgroup;
-                       # TODO Record hypotheticals used to create group, if we end up
-                       # needing it
+                       # Note any layered witnesses that appear in this group
+                       foreach( @realgroup ) {
+                               if( $_ =~ /^(.*)\Q$aclabel\E$/ ) {
+                                       push( @layerwits, $1 );
+                               }
+                       }
                }
+               $location->{'layerwits'} = \@layerwits if @layerwits;
        }
        $answer->{'conflict_count'} = $conflict_count;
+       $answer->{'reversion_count'} = $reversion_count;
        
        return $answer;
 }
 
-=head2 group_variants( $tradition, $rank, $lacunose, @merge_relationship_types )
+=head2 group_variants( $tradition, $rank, $lacunose, $transposed, $merge_relationship_types )
 
 Groups the variants at the given $rank of the collation, treating any
-relationships in @merge_relationship_types as equivalent.  $lacunose should
-be a reference to an array, to which the sigla of lacunose witnesses at this 
-rank will be appended; $transposed should be a reference to a hash, wherein
-the identities of transposed readings and their relatives will be stored.
+relationships in the set $merge_relationship_types as equivalent. 
+$lacunose should be a reference to an array, to which the sigla of lacunose
+witnesses at this rank will be appended; $transposed should be a reference
+to a hash, wherein the identities of transposed readings and their
+relatives will be stored.
 
 Returns a hash $group_readings where $rdg is attested by the witnesses listed 
 in $group_readings->{$rdg}.
@@ -244,18 +292,18 @@ sub group_variants {
        my( $tradition, $rank, $lacunose, $transposed, $collapse ) = @_;
        my $c = $tradition->collation;
        my $aclabel = $c->ac_label;
+       my $table = $c->alignment_table;
        # Get the alignment table readings
        my %readings_at_rank;
-       my %is_lacunose; # lookup table for $lacunose
-       map { $is_lacunose{$_} = 1 } @$lacunose;
-       my @check_for_gaps;
+       my $check_for_gaps = Set::Scalar->new();
        my %moved_wits;
-       foreach my $tablewit ( @{$c->alignment_table->{'alignment'}} ) {
+       my $has_transposition;
+       foreach my $tablewit ( @{$table->{'alignment'}} ) {
                my $rdg = $tablewit->{'tokens'}->[$rank-1];
                my $wit = $tablewit->{'witness'};
                # Exclude the witness if it is "lacunose" which if we got here
                # means "not in the stemma".
-               next if $is_lacunose{$wit};
+               next if _is_lacunose( $wit, $lacunose, $aclabel );
                # Note if the witness is actually in a lacuna
                if( $rdg && $rdg->{'t'}->is_lacuna ) {
                        _add_to_witlist( $wit, $lacunose, $aclabel );
@@ -263,7 +311,7 @@ sub group_variants {
                } elsif( $rdg ) {
                        # If the reading has been counted elsewhere as a transposition, ignore it.
                        if( $transposed->{$rdg->{'t'}->id} ) {
-                               # TODO This doesn't cope with three-way transpositions
+                               # TODO Does this cope with three-way transpositions?
                                map { $moved_wits{$_} = 1 } @{$transposed->{$rdg->{'t'}->id}};
                                next;
                        }
@@ -272,84 +320,193 @@ sub group_variants {
                        # ...and grab any transpositions, and their relations.
                        my @transp = grep { $_->rank != $rank } $rdg->{'t'}->related_readings();
                        foreach my $trdg ( @transp ) {
-                               map { $moved_wits{$_} = 1 } $trdg->witnesses;
-                               $transposed->{$trdg->id} = [ $rdg->{'t'}->witnesses ];
+                               next if exists $readings_at_rank{$trdg->id};
+                               $has_transposition = 1;
+                               my @affected_wits = _table_witnesses( 
+                                       $table, $trdg, $lacunose, $aclabel );
+                               next unless @affected_wits;
+                               map { $moved_wits{$_} = 1 } @affected_wits;
+                               $transposed->{$trdg->id} = 
+                                       [ _table_witnesses( $table, $rdg->{'t'}, $lacunose, $aclabel ) ];
                                $readings_at_rank{$trdg->id} = $trdg;
                        }
                # ...or it is empty, ergo a gap.
                } else {
-                       push( @check_for_gaps, $wit );
+                       _add_to_witlist( $wit, $check_for_gaps, $aclabel );
                }
        }
-       my @gap_wits;
-       map { _add_to_witlist( $_, \@gap_wits, $aclabel ) 
-               unless $moved_wits{$_} } @check_for_gaps;
-       # TODO check for, and break into a new row, any doubled-up witness readings
-       #    after transposition...
-       # Group the readings, collapsing groups by relationship if needed
-       my %grouped_readings;
+       my $gap_wits = Set::Scalar->new();
+       map { _add_to_witlist( $_, $gap_wits, $aclabel ) 
+               unless $moved_wits{$_} } $check_for_gaps->members;
+               
+       # Group the readings, collapsing groups by relationship if needed.      
+       my $grouped_readings = {};
        foreach my $rdg ( values %readings_at_rank ) {
                # Skip readings that have been collapsed into others.
-               next if exists $grouped_readings{$rdg->id} && !$grouped_readings{$rdg->id};
+               next if exists $grouped_readings->{$rdg->id} 
+                       && $grouped_readings->{$rdg->id} eq 'COLLAPSE';
                # Get the witness list, including from readings collapsed into this one.
-               my @wits = $rdg->witnesses;
-               if( $collapse ) {
-                       my $filter = sub { my $r = $_[0]; grep { $_ eq $r->type } @$collapse; };
+               my @wits = _table_witnesses( $table, $rdg, $lacunose, $aclabel );
+               if( $collapse && $collapse->size ) {
+                       my $filter = sub { $collapse->has( $_[0]->type ) };
                        foreach my $other ( $rdg->related_readings( $filter ) ) {
-                               my @otherwits = $other->witnesses;
+                               my @otherwits = _table_witnesses( $table, $other, $lacunose, $aclabel );
                                push( @wits, @otherwits );
-                               $grouped_readings{$other->id} = 0;
+                               $grouped_readings->{$other->id} = 'COLLAPSE';
                        }
                }
-               # Filter the group to those witnesses in the stemma
-               my @use_wits;
-               foreach my $wit ( @wits ) {
-                       next if $is_lacunose{$wit};
-                       push( @use_wits, $wit );
-               }
-               $grouped_readings{$rdg->id} = \@use_wits;       
+               $grouped_readings->{$rdg->id} = Set::Scalar->new( @wits );
+       }
+       if( $gap_wits->members ) {
+               $grouped_readings->{'(omitted)'} = $gap_wits;
        }
-       $grouped_readings{'(omitted)'} = \@gap_wits if @gap_wits;
+       
        # Get rid of our collapsed readings
-       map { delete $grouped_readings{$_} unless $grouped_readings{$_} } 
-               keys %grouped_readings 
-               if $collapse;
+       map { delete $grouped_readings->{$_} if(
+                        $grouped_readings->{$_} eq 'COLLAPSE'
+                        || $grouped_readings->{$_}->is_empty ) } 
+               keys %$grouped_readings;
+               
+       # If something was transposed, check the groups for doubled-up readings
+       if( $has_transposition ) {
+               # print STDERR "Group for rank $rank:\n";
+               # map { print STDERR "\t$_: " . join( ' ' , @{$grouped_readings->{$_}} ) . "\n" } 
+               #       keys %$grouped_readings;
+               _check_transposed_consistency( $c, $rank, $transposed, $grouped_readings );
+       }
        
        # Return the result
-       return \%grouped_readings;
+       return $grouped_readings;
+}
+
+# Helper function to query the alignment table for all witnesses (a.c. included)
+# that have a given reading at its rank.
+sub _table_witnesses {
+       my( $table, $trdg, $lacunose, $aclabel ) = @_;
+       my $tableidx = $trdg->rank - 1;
+       my $has_reading = Set::Scalar->new();
+       foreach my $row ( @{$table->{'alignment'}} ) {
+               my $wit = $row->{'witness'};
+               next if _is_lacunose( $wit, $lacunose, $aclabel );
+               my $rdg = $row->{'tokens'}->[$tableidx];
+               next unless exists $rdg->{'t'} && defined $rdg->{'t'};
+               _add_to_witlist( $wit, $has_reading, $aclabel )
+                       if $rdg->{'t'}->id eq $trdg->id;
+       }
+       return $has_reading->members;
+}
+
+# Helper function to see if a witness is lacunose even if we are asking about
+# the a.c. version
+sub _is_lacunose {
+       my ( $wit, $lac, $acstr ) = @_;
+       if( $wit =~ /^(.*)\Q$acstr\E$/ ) {
+               $wit = $1;
+       }
+       return $lac->has( $wit );
 }
 
 # Helper function to ensure that X and X a.c. never appear in the same list.
 sub _add_to_witlist {
        my( $wit, $list, $acstr ) = @_;
-       my %inlist;
-       my $idx = 0;
-       map { $inlist{$_} = $idx++ } @$list;
        if( $wit =~ /^(.*)\Q$acstr\E$/ ) {
-               my $acwit = $1;
-               unless( exists $inlist{$acwit} ) {
-                       push( @$list, $acwit.$acstr );
+               # Don't add X a.c. if we already have X 
+               return if $list->has( $1 );
+       } else {
+               # Delete X a.c. if we are about to add X
+               $list->delete( $wit.$acstr );
+       }
+       $list->insert( $wit );
+}
+
+sub _check_transposed_consistency {
+       my( $c, $rank, $transposed, $groupings ) = @_;
+       my %seen_wits;
+       my %thisrank;
+       # Note which readings are actually at this rank, and which witnesses
+       # belong to which reading.
+       foreach my $rdg ( keys %$groupings ) {
+               my $rdgobj = $c->reading( $rdg );
+               # Count '(omitted)' as a reading at this rank
+               $thisrank{$rdg} = 1 if !$rdgobj || $rdgobj->rank == $rank;
+               map { push( @{$seen_wits{$_}}, $rdg ) } @{$groupings->{$rdg}};
+       }
+       # Our work is done if we have no witness belonging to more than one
+       # reading.
+       my @doubled = grep { scalar @{$seen_wits{$_}} > 1 } keys %seen_wits;
+       return unless @doubled;
+       # If we have a symmetric related transposition, drop the non-rank readings.
+       if( @doubled == scalar keys %seen_wits ) {
+               foreach my $rdg ( keys %$groupings ) {
+                       if( !$thisrank{$rdg} ) {
+                               my $groupstr = wit_stringify( $groupings->{$rdg} );
+                               my ( $matched ) = grep { $groupstr eq wit_stringify( $groupings->{$_} ) }
+                                       keys %thisrank;
+                               delete $groupings->{$rdg};
+                               # If we found a group match, assume there is a symmetry happening.
+                               # TODO think more about this
+                               # print STDERR "*** Deleting symmetric reading $rdg\n";
+                               unless( $matched ) {
+                                       delete $transposed->{$rdg};
+                                       warn "Found problem in evident symmetry with reading $rdg";
+                               }
+                       }
                }
+       # Otherwise 'unhook' the transposed reading(s) that have duplicates.
        } else {
-               if( exists( $inlist{$wit.$acstr} ) ) {
-                       # Replace the a.c. version with the main witness
-                       my $i = $inlist{$wit.$acstr};
-                       $list->[$i] = $wit;
-               } else {
-                       push( @$list, $wit );
+               foreach my $dup ( @doubled ) {
+                       foreach my $rdg ( @{$seen_wits{$dup}} ) {
+                               next if $thisrank{$rdg};
+                               next unless exists $groupings->{$rdg};
+                               # print STDERR "*** Deleting asymmetric doubled-up reading $rdg\n";
+                               delete $groupings->{$rdg};
+                               delete $transposed->{$rdg};
+                       }
                }
+               # and put any now-orphaned readings into an 'omitted' reading.
+               foreach my $wit ( keys %seen_wits ) {
+                       unless( grep { exists $groupings->{$_} } @{$seen_wits{$wit}} ) {
+                               $groupings->{'(omitted)'} = Set::Scalar->new()
+                                        unless exists $groupings->{'(omitted)'};
+                               _add_to_witlist( $wit, $groupings->{'(omitted)'}, $c->ac_label );
+                       }
+               }
+       }
+}
+
+# For the given grouping, return its situation graph based on the stemma.
+sub _graph_for_grouping {
+       my( $stemma, $grouping, $lacunose, $aclabel ) = @_;
+       my $acwits = [];
+       my $extant = {};
+       foreach my $gs ( values %$grouping ) {
+               map { 
+                       if( $_ =~ /^(.*)\Q$aclabel\E$/ ) {
+                               push( @$acwits, $1 ) unless $lacunose->has( $1 );
+                       } else {
+                               $extant->{$_} = 1 unless $lacunose->has( $_ );
+                       }
+               } $gs->members;
+       }
+       my $graph;
+       try {
+               # contig contains all extant wits and all hypothetical wits
+               # needed to make up the groups.
+               $graph = $stemma->situation_graph( $extant, $acwits );
+       } catch ( Text::Tradition::Error $e ) {
+               throw( "Could not extend graph with given extant and a.c. witnesses: "
+                       . $e->message );
+       } catch {
+               throw( "Could not extend graph with a.c. witnesses @$acwits" );
        }
+       return $graph;
 }
 
-=head2 solve_variants( $graph, @groups ) 
+=head2 solve_variants( $calcdir, @groups ) 
 
-Sends the set of groups to the external graph solver service and returns
-a cleaned-up answer, adding the rank IDs back where they belong.
+Looks up the set of groups in the answers provided by the external graph solver 
+service and returns a cleaned-up answer, adding the rank IDs back where they belong.
 
-The JSON has the form 
-  { "graph": [ stemmagraph DOT string without newlines ],
-    "groupings": [ array of arrays of groups, one per rank ] }
-    
 The answer has the form 
   { "variants" => [ array of variant location structures ],
     "variant_count" => total,
@@ -359,208 +516,120 @@ The answer has the form
 =cut
 
 sub solve_variants {
-       my( $stemma, @groups ) = @_;
-       my $aclabel = $stemma->collation->ac_label;
-
-       # Filter the groups down to distinct groups, and work out what graph
-       # should be used in the calculation of each group. We want to send each
-       # distinct problem to the solver only once.
-       # We need a whole bunch of lookup tables for this.
-       my $index_groupkeys = {};       # Save the order of readings
-       my $group_indices = {};         # Save the indices that have a given grouping
-       my $graph_problems = {};        # Save the groupings for the given graph
-
-       foreach my $idx ( 0..$#groups ) {
-               my $ghash = $groups[$idx];
-               my @grouping;
-               # Sort the groupings from big to little, and scan for a.c. witnesses
-               # that would need an extended graph.
-               my @acwits;   # note which AC witnesses crop up at this rank
-               my @idxkeys = sort { scalar @{$ghash->{$b}} <=> scalar @{$ghash->{$a}} }
-                       keys %$ghash;
-               foreach my $rdg ( @idxkeys ) {
-                       my @sg = sort @{$ghash->{$rdg}};
-                       push( @acwits, grep { $_ =~ /\Q$aclabel\E$/ } @sg );
-                       push( @grouping, \@sg );
-               }
-               # Save the reading order
-               $index_groupkeys->{$idx} = \@idxkeys;
-               
-               # Now associate the distinct group with this index
-               my $gstr = wit_stringify( \@grouping );
-               push( @{$group_indices->{$gstr}}, $idx );
-               
-               # Finally, add the group to the list to be calculated for this graph.
-               map { s/\Q$aclabel\E$// } @acwits;
-               my $graph = $stemma->extend_graph( \@acwits );
-               unless( exists $graph_problems->{"$graph"} ) {
-                       $graph_problems->{"$graph"} = { 'object' => $graph, 'groups' => [] };
+       my( @groups ) = @_;
+       
+       # Are we using a local result directory, or did we pass an empty value
+       # for the directory?
+       my $dir;
+       unless( ref( $groups[0] ) eq 'HASH' ) {
+               $dir = shift @groups;
+       }
+
+       ## For each graph/group combo, make a Text::Tradition::Analysis::Result
+       ## object so that we can send it off for IDP lookup.
+       my $variants = [];
+       my $genealogical = 0; # counter
+       # TODO Optimize for unique graph problems
+       my %problems;
+       foreach my $graphproblem ( @groups ) {
+               # Construct the calc result key and look up its answer
+               my $problem = Text::Tradition::Analysis::Result->new(
+                       graph => $graphproblem->{'graph'},
+                       setlist => [ values %{$graphproblem->{'grouping'}} ] );
+               if( exists $problems{$problem->object_key} ) {
+                       $problem = $problems{$problem->object_key};
+               } else {
+                       $problems{$problem->object_key} = $problem;
                }
-               push( @{$graph_problems->{"$graph"}->{'groups'}}, \@grouping );
+               $graphproblem->{'object'} = $problem;
        }
        
-       ## For each distinct graph, send its groups to the solver.
-       my $solver_url = 'http://byzantini.st/cgi-bin/graphcalc.cgi';
-       my $ua = LWP::UserAgent->new();
-       ## Witness map is a HACK to get around limitations in node names from IDP
-       my $witness_map = {};
-       ## Variables to store answers as they come back
-       my $variants = [ ( undef ) x ( scalar keys %$index_groupkeys ) ];
-       my $genealogical = 0;
-       foreach my $graphkey ( keys %$graph_problems ) {
-               my $graph = $graph_problems->{$graphkey}->{'object'};
-               my $groupings = $graph_problems->{$graphkey}->{'groups'};
-               my $json = encode_json( _safe_wit_strings( $graph, $stemma->collation,
-                       $groupings, $witness_map ) );
+       my %results;
+       if( $dir ) {
+               my $scope = $dir->new_scope;
+               map { $results{$_} = $dir->lookup( $_ ) || $problems{$_} } keys %problems;
+       } else {
+               my $json = JSON->new->allow_blessed->convert_blessed->utf8->encode( 
+                       [ values %problems ] );
                # Send it off and get the result
-               #print STDERR "Sending request: $json\n";
-               my $resp = $ua->post( $solver_url, 'Content-Type' => 'application/json', 
-                                                         'Content' => $json );                                                   
-               my $answer;
-               my $used_idp;
+               # print STDERR "Sending request: " . decode_utf8( $json ) . "\n";
+               my $ua = LWP::UserAgent->new();
+               my $resp = $ua->post( $SOLVER_URL, 'Content-Type' => 'application/json', 
+                                                         'Content' => $json ); 
+               my $answer;     
                if( $resp->is_success ) {
-                       $answer = _desanitize_names( decode_json( $resp->content ), $witness_map );
-                       $used_idp = 1;
+                       $answer = decode_json( $resp->content );
+                       throw( "Unexpected answer from IDP: $answer" ) unless ref( $answer ) eq 'ARRAY';
                } else {
-                       # Fall back to the old method.
-                       warn "IDP solver returned " . $resp->status_line . " / " . $resp->content
-                               . "; falling back to perl method";
-                       $answer = perl_solver( $graph, @$groupings );
+                       throw( "IDP solver returned " . $resp->status_line . " / " . $resp->content
+                               . "; cannot run graph analysis" );
                }
-               ## The answer is the evaluated groupings, plus a boolean for whether
-               ## they were genealogical.  Reconstruct our original groups.
-               foreach my $gidx ( 0 .. $#{$groupings} ) {
-                       my( $calc_groups, $result ) = @{$answer->[$gidx]};
-                       if( $result ) {
-                               $genealogical++;
-                               # Prune the calculated groups, in case the IDP solver failed to.
-                               if( $used_idp ) {
-                                       my @pruned_groups;
-                                       foreach my $cg ( @$calc_groups ) {
-                                               # This is a little wasteful but the path of least
-                                               # resistance. Send both the stemma, which knows what
-                                               # its hypotheticals are, and the actual graph used.
-                                               my @pg = _prune_group( $cg, $stemma, $graph );
-                                               push( @pruned_groups, \@pg );
-                                       }
-                                       $calc_groups = \@pruned_groups;
-                               }
-                       }
-                       # Retrieve the key for the original group that went to the solver
-                       my $input_group = wit_stringify( $groupings->[$gidx] );
-                       foreach my $oidx ( @{$group_indices->{$input_group}} ) {
-                               my @readings = @{$index_groupkeys->{$oidx}};
-                               my $vstruct = {
-                                       'genealogical' => $result,
-                                       'readings' => [],
-                               };
-                               foreach my $ridx ( 0 .. $#readings ) {
-                                       push( @{$vstruct->{'readings'}},
-                                               { 'readingid' => $readings[$ridx],
-                                                 'group' => $calc_groups->[$ridx] } );
-                               }
-                               $variants->[$oidx] = $vstruct;
-                       }
+               # One more sanity check
+               throw( "Something went wrong with answer symmetricity" )
+                       unless keys( %problems ) == @$answer;
+               # Convert the results
+               foreach my $a ( @$answer ) {
+                       my $r = Text::Tradition::Analysis::Result->new( $a );
+                       $results{$r->object_key} = $r;
                }
        }
        
-       return { 'variants' => $variants, 
-                        'variant_count' => scalar @$variants,
-                        'genealogical_count' => $genealogical };
-}
-
-#### HACKERY to cope with IDP's limited idea of what a node name looks like ###
-
-sub _safe_wit_strings {
-       my( $graph, $c, $groupings, $witness_map ) = @_;
-       # Parse the graph we were given into a stemma.
-       my $safegraph = Graph->new();
-       # Convert the graph to a safe representation and store the conversion.
-       foreach my $n ( $graph->vertices ) {
-               my $sn = _safe_witstr( $n );
-               if( exists $witness_map->{$sn} ) {
-                       warn "Ambiguous stringification $sn for $n and " . $witness_map->{$sn}
-                               if $witness_map->{$sn} ne $n;
+       # We now have a single JSON-encoded Result object per problem sent. Fold its
+       # answers into our variant info structure.
+       foreach my $graphproblem ( @groups ) {
+               my $result = $results{$graphproblem->{'object'}->object_key}
+                       || $graphproblem->{'object'};
+               
+               # Initialize the result structure for this graph problem
+               my $vstruct;
+               if( $result->status eq 'OK' ) {
+                       $vstruct = { readings => [] };
+                       push( @$variants, $vstruct );
                } else {
-                       $witness_map->{$sn} = $n;
+                       push( @$variants, _init_unsolved( $graphproblem, $result->status ) );
+                       next;
                }
-               $safegraph->add_vertex( $sn );
-               $safegraph->set_vertex_attributes( $sn, 
-                       $graph->get_vertex_attributes( $n ) );
-       }
-       foreach my $e ( $graph->edges ) {
-               my @safe_e = ( _safe_witstr( $e->[0] ), _safe_witstr( $e->[1] ) );
-               $safegraph->add_edge( @safe_e );
-       }
-       my $safe_stemma = Text::Tradition::Stemma->new( 
-               'collation' => $c, 'graph' => $safegraph );
+                               
+               # 1. Did the group evaluate as genealogical?
+               $vstruct->{genealogical} = $result->is_genealogical;
+               $genealogical++ if $result->is_genealogical;
                
-       # Now convert the witness groupings to a safe representation.
-       my $safe_groupings = [];
-       foreach my $grouping ( @$groupings ) {
-               my $safe_grouping = [];
-               foreach my $group ( @$grouping ) {
-                       my $safe_group = [];
-                       foreach my $n ( @$group ) {
-                               my $sn = _safe_witstr( $n );
-                               warn "Ambiguous stringification $sn for $n and " . $witness_map->{$sn}
-                                       if exists $witness_map->{$sn} && $witness_map->{$sn} ne $n;
-                               $witness_map->{$sn} = $n;
-                               push( @$safe_group, $sn );
-                       }
-                       push( @$safe_grouping, $safe_group );
+               # 2. What are the calculated minimum groupings for each variant loc?
+               foreach my $rid ( keys %{$graphproblem->{grouping}} ) {
+                       my $inputset = $graphproblem->{grouping}->{$rid};
+                       my $minset = $result->minimum_grouping_for( $inputset );
+                       push( @{$vstruct->{readings}}, { readingid => $rid, group => $minset } );
                }
-               push( @$safe_groupings, $safe_grouping );
+               
+               # 3. What are the sources and classes calculated for each witness?
+               $vstruct->{witcopy_types} = { $result->classes };
+               $vstruct->{reading_roots} = {};
+               map { $vstruct->{reading_roots}->{$_} = 1 } $result->sources;
+               
        }
        
-       # Return it all in the struct we expect.  We have stored the reductions
-       # in the $witness_map that we were passed.
-       return { 'graph' => $safe_stemma->editable( { 'linesep' => ' ' } ), 
-                        'groupings' => $safe_groupings };
-}
-
-sub _safe_witstr {
-       my $witstr = shift;
-       $witstr =~ s/\s+/_/g;
-       $witstr =~ s/[^\w\d-]//g;
-       return $witstr;
+       return { 'variants' => $variants, 
+                        'variant_count' => scalar @$variants,
+                        'genealogical_count' => $genealogical };
 }
 
-sub _desanitize_names {
-       my( $jsonstruct, $witness_map ) = @_;
-       my $result = [];
-       foreach my $grouping ( @$jsonstruct ) {
-               my $real_grouping = [];
-               foreach my $element ( @$grouping ) {
-                       if( ref( $element ) eq 'ARRAY' ) {
-                               # it's the groupset.
-                               my $real_groupset = [];
-                               foreach my $group ( @$element ) {
-                                       my $real_group = [];
-                                       foreach my $n ( @$group ) {
-                                               my $rn = $witness_map->{$n};
-                                               push( @$real_group, $rn );
-                                       }
-                                       push( @$real_groupset, $real_group );
-                               }
-                               push( @$real_grouping, $real_groupset );
-                       } else {
-                               # It is the boolean, not actually a group.
-                               push( @$real_grouping, $element );
-                       }
-               }
-               push( @$result, $real_grouping );
+sub _init_unsolved {
+       my( $graphproblem, $status ) = @_;
+       my $vstruct = { 'readings' => [] };
+       $vstruct->{'unsolved'} = $status;
+       foreach my $rid ( keys %{$graphproblem->{grouping}} ) {
+               push( @{$vstruct->{readings}}, { readingid => $rid, 
+                       group => [ $graphproblem->{grouping}->{$rid}->members ] } );
        }
-       return $result;
+       return $vstruct;
 }
 
-### END HACKERY ###
-
 =head2 analyze_location ( $tradition, $graph, $location_hash )
 
 Given the tradition, its stemma graph, and the solution from the graph solver,
 work out the rest of the information we want.  For each reading we need missing, 
-conflict, reading_parents, independent_occurrence, followed, not_followed, and follow_unknown.  Alters the location_hash in place.
+conflict, reading_parents, independent_occurrence, followed, not_followed,
+and follow_unknown.  Alters the location_hash in place.
 
 =cut
 
@@ -568,104 +637,82 @@ sub analyze_location {
        my ( $tradition, $graph, $variant_row, $lacunose ) = @_;
        my $c = $tradition->collation;
        
+       if( exists $variant_row->{'unsolved'} ) {
+               return;
+       }
+       my $reading_roots = delete $variant_row->{'reading_roots'};
+       my $classinfo = delete $variant_row->{'witcopy_types'};
+       
        # Make a hash of all known node memberships, and make the subgraphs.
        my $contig = {};
-       my $reading_roots = {};
        my $subgraph = {};
-       $DB::single = 1 if $variant_row->{id} == 6;
-       # Note which witnesses positively belong to which group
-    foreach my $rdghash ( @{$variant_row->{'readings'}} ) {
-       my $rid = $rdghash->{'readingid'};
-               map { $contig->{$_} = $rid } @{$rdghash->{'group'}};
-       }
+       my $acstr = $c->ac_label;
+       my @acwits;
        
-       # Now, armed with that knowledge, make a subgraph for each reading
-       # and note the root(s) of each subgraph.
-       foreach my $rdghash( @{$variant_row->{'readings'}} ) {
+       # Note which witnesses positively belong to which group. This information
+       # comes ultimately from the IDP solver.
+       # Also make a note of the reading's roots.
+    foreach my $rdghash ( @{$variant_row->{'readings'}} ) {
        my $rid = $rdghash->{'readingid'};
-        my %rdgwits;
-        # Make the subgraph.
-        my $part = $graph->copy;
-        my @todelete = grep { exists $contig->{$_} && $contig->{$_} ne $rid }
-               keys %$contig;
-        $part->delete_vertices( @todelete );
-        _prune_subtree( $part, $lacunose );
-               $subgraph->{$rid} = $part;
-               # Record the remaining lacunose nodes as part of this group, if
-               # we are dealing with a non-genealogical reading.
-               unless( $variant_row->{'genealogical'} ) {
-                       map { $contig->{$_} = $rid } $part->vertices;
-               }
-               # Get the reading roots.
-               map { $reading_roots->{$_} = $rid } $part->predecessorless_vertices;
+       my @roots;
+       foreach my $wit ( @{$rdghash->{'group'}} ) {
+               $contig->{$wit} = $rid;
+           if( $wit =~ /^(.*)\Q$acstr\E$/ ) {
+               push( @acwits, $1 );
+           }
+           if( exists $reading_roots->{$wit} && $reading_roots->{$wit} ) {
+               push( @roots, $wit );
+           }
+       }
+               $rdghash->{'independent_occurrence'} = \@roots;
        }
-       
+                       
        # Now that we have all the node group memberships, calculate followed/
     # non-followed/unknown values for each reading.  Also figure out the
     # reading's evident parent(s).
     foreach my $rdghash ( @{$variant_row->{'readings'}} ) {
         my $rid = $rdghash->{'readingid'};
-        # Get the subgraph
-        my $part = $subgraph->{$rid};
+        my $rdg = $c->reading( $rid );
+        my @roots = @{$rdghash->{'independent_occurrence'}};
+        my @reversions;
+        if( $classinfo ) {
+               @reversions = grep { $classinfo->{$_} eq 'revert' } 
+                       $rdghash->{'group'}->members;
+               $rdghash->{'reversions'} = \@reversions;
+        }
+        my @group = @{$rdghash->{'group'}};
         
         # Start figuring things out.  
-        my @roots = grep { $reading_roots->{$_} eq $rid } keys %$reading_roots;
-        $rdghash->{'independent_occurrence'} = \@roots;
-        $rdghash->{'followed'} = scalar( $part->vertices ) - scalar( @roots );
+        $rdghash->{'followed'} = scalar( @group ) 
+               - ( scalar( @roots ) + scalar( @reversions ) );
         # Find the parent readings, if any, of this reading.
-        my $rdgparents = {};
-        foreach my $wit ( @roots ) {
-               # Look in the main stemma to find this witness's extant or known-reading
-               # immediate ancestor(s), and look up the reading that each ancestor olds.
-                       my @check = $graph->predecessors( $wit );
-                       while( @check ) {
-                               my @next;
-                               foreach my $wparent( @check ) {
-                                       my $preading = $contig->{$wparent};
-                                       if( $preading ) {
-                                               $rdgparents->{$preading} = 1;
-                                       } else {
-                                               push( @next, $graph->predecessors( $wparent ) );
-                                       }
-                               }
-                               @check = @next;
-                       }
-               }
-               foreach my $p ( keys %$rdgparents ) {
-                       # Resolve the relationship of the parent to the reading, and
-                       # save it in our hash.
-                       my $pobj = $c->reading( $p );
-                       my $relation;
-                       my $prep = $pobj ? $pobj->id . ' (' . $pobj->text . ')' : $p;
-                       if( $pobj ) {
-                               my $rel = $c->get_relationship( $p, $rdghash->{readingid} );
-                               if( $rel ) {
-                                       $relation = { type => $rel->type };
-                                       if( $rel->has_annotation ) {
-                                               $relation->{'annotation'} = $rel->annotation;
-                                       }
-                               }
-                       }       
-                       $rdgparents->{$p} = { 'label' => $prep, 'relation' => $relation };
+        my $sourceparents = _find_reading_parents( $rid, $graph, $contig, @roots );
+               # Work out relationships between readings and their non-followed parent.
+               _resolve_parent_relationships( $c, $rid, $rdg, $sourceparents );
+               $rdghash->{'source_parents'} = $sourceparents;
+
+               if( @reversions ) {
+                       my $revparents = _find_reading_parents( $rid, $graph, $contig, @reversions );
+                       _resolve_parent_relationships( $c, $rid, $rdg, $revparents );
+                       $rdghash->{'reversion_parents'} = $revparents;
                }
-                       
-               $rdghash->{'reading_parents'} = $rdgparents;
                
                # Find the number of times this reading was altered, and the number of
                # times we're not sure.
                my( %nofollow, %unknownfollow );
-               foreach my $wit ( $part->vertices ) {
+               foreach my $wit ( @{$rdghash->{'group'}} ) {
                        foreach my $wchild ( $graph->successors( $wit ) ) {
-                               next if $part->has_vertex( $wchild );
-                               if( $reading_roots->{$wchild} && $contig->{$wchild} ) {
+                               if( $reading_roots->{$wchild} && $contig->{$wchild}
+                                       && $contig->{$wchild} ne $rid ) {
                                        # It definitely changed here.
                                        $nofollow{$wchild} = 1;
                                } elsif( !($contig->{$wchild}) ) {
                                        # The child is a hypothetical node not definitely in
                                        # any group. Answer is unknown.
                                        $unknownfollow{$wchild} = 1;
-                               } # else it's a non-root node in a known group, and therefore
-                                 # is presumed to have its reading from its group, not this link.
+                               } # else it is either in our group, or it is a non-root node in a 
+                                 # known group and therefore is presumed to have its reading from 
+                                 # its group, not this link.
                        }
                }
                $rdghash->{'not_followed'} = keys %nofollow;
@@ -673,310 +720,152 @@ sub analyze_location {
                
                # Now say whether this reading represents a conflict.
                unless( $variant_row->{'genealogical'} ) {
-                       $rdghash->{'conflict'} = @roots != 1;
+                       $rdghash->{'is_conflict'} = @roots != 1;
+                       $rdghash->{'is_reverted'} = scalar @reversions;
                }               
     }
 }
 
-
-=head2 perl_solver( $tradition, $rank, $stemma_id, @merge_relationship_types )
-
-** NOTE ** This method should hopefully not be called - it is not guaranteed 
-to be correct.  Serves as a backup for the real solver.
-
-Runs an analysis of the given tradition, at the location given in $rank, 
-against the graph of the stemma specified in $stemma_id.  The argument 
-@merge_relationship_types is an optional list of relationship types for
-which readings so related should be treated as equivalent.
-
-Returns a nested array data structure as follows:
-
- [ [ group_list, is_genealogical ], [ group_list, is_genealogical ] ... ]
-where the group list is the array of arrays passed in for each element of @groups,
-possibly with the addition of hypothetical readings.
-
-=cut
-
-sub perl_solver {
-       my( $graph, @groups ) = @_;
-       my @answer;
-       foreach my $g ( @groups ) {
-               push( @answer, _solve_variant_location( $graph, $g ) );
+sub _find_reading_parents {
+       my( $rid, $graph, $contig, @list ) = @_;
+       my $parenthash = {};
+       foreach my $wit ( @list ) {
+               # Look in the stemma graph to find this witness's extant or known-reading
+               # immediate ancestor(s), and look up the reading that each ancestor holds.
+               my @check = $graph->predecessors( $wit );
+               while( @check ) {
+                       my @next;
+                       foreach my $wparent( @check ) {
+                               my $preading = $contig->{$wparent};
+                               if( $preading && $preading ne $rid ) {
+                                       $parenthash->{$preading} = 1;
+                               } else {
+                                       push( @next, $graph->predecessors( $wparent ) );
+                               }
+                       }
+                       @check = @next;
+               }
        }
-       return \@answer;
+       return $parenthash;
 }
 
-sub _solve_variant_location {
-       my( $graph, $groups ) = @_;
-       # Now do the work.      
-    my $contig = {};
-    my $subgraph = {};
-    my $is_conflicted;
-    my $conflict = {};
-
-    # Mark each ms as in its own group, first.
-    foreach my $g ( @$groups ) {
-        my $gst = wit_stringify( $g );
-        map { $contig->{$_} = $gst } @$g;
-    }
-
-    # Now for each unmarked node in the graph, initialize an array
-    # for possible group memberships.  We will use this later to
-    # resolve potential conflicts.
-    map { $contig->{$_} = [] unless $contig->{$_} } $graph->vertices;
-    foreach my $g ( sort { scalar @$b <=> scalar @$a } @$groups ) {
-        my $gst = wit_stringify( $g );  # This is the group name
-        # Copy the graph, and delete all non-members from the new graph.
-        my $part = $graph->copy;
-        my @group_roots;
-        $part->delete_vertices( 
-            grep { !ref( $contig->{$_} ) && $contig->{$_} ne $gst } $graph->vertices );
-                
-        # Now look to see if our group is connected.
-               if( @$g > 1 ) {
-                       # We have to take directionality into account.
-                       # How many root nodes do we have?
-                       my @roots = grep { ref( $contig->{$_} ) || $contig->{$_} eq $gst } 
-                               $part->predecessorless_vertices;
-                       # Assuming that @$g > 1, find the first root node that has at
-                       # least one successor belonging to our group. If this reading
-                       # is genealogical, there should be only one, but we will check
-                       # that implicitly later.
-                       foreach my $root ( @roots ) {
-                               # Prune the tree to get rid of extraneous hypotheticals.
-                               $root = _prune_subtree_old( $part, $root, $contig );
-                               next unless $root;
-                               # Save this root for our group.
-                               push( @group_roots, $root );
-                               # Get all the successor nodes of our root.
-                       }
-               } else {
-                       # Dispense with the trivial case of one reading.
-                       my $wit = $g->[0];
-                       @group_roots = ( $wit );
-                       foreach my $v ( $part->vertices ) {
-                               $part->delete_vertex( $v ) unless $v eq $wit;
-                       }
-        }
-        
-        if( @group_roots > 1 ) {
-               $conflict->{$gst} = 1;
-               $is_conflicted = 1;
-        }
-        # Paint the 'hypotheticals' with our group.
-               foreach my $wit ( $part->vertices ) {
-                       if( ref( $contig->{$wit} ) ) {
-                               push( @{$contig->{$wit}}, $gst );
-                       } elsif( $contig->{$wit} ne $gst ) {
-                               warn "How did we get here?";
-                       }
-               }
-        
-        
-               # Save the relevant subgraph.
-               $subgraph->{$gst} = $part;
-    }
-    
-       # For each of our hypothetical readings, flatten its 'contig' array if
-       # the array contains zero or one group.  If we have any unflattened arrays,
-       # we may need to run the resolution process. If the reading is already known
-       # to have a conflict, flatten the 'contig' array to nothing; we won't resolve
-       # it.
-       my @resolve;
-       foreach my $wit ( keys %$contig ) {
-               next unless ref( $contig->{$wit} );
-               if( @{$contig->{$wit}} > 1 ) {
-                       if( $is_conflicted ) {
-                               $contig->{$wit} = '';  # We aren't going to decide.
+sub _resolve_parent_relationships {
+       my( $c, $rid, $rdg, $rdgparents ) = @_;
+       foreach my $p ( keys %$rdgparents ) {
+               # Resolve the relationship of the parent to the reading, and
+               # save it in our hash.
+               my $pobj = $c->reading( $p );
+               my $prep = $pobj ? $pobj->id . ' (' . $pobj->text . ')' : $p;
+               my $phash = { 'label' => $prep };
+               if( $pobj ) {
+                       my $rel = $c->get_relationship( $p, $rid );
+                       if( $rel ) {
+                               _add_to_hash( $rel, $phash );
+                       } elsif( $rdg ) {
+                               # First check for a transposed relationship
+                               if( $rdg->rank != $pobj->rank ) {
+                                       foreach my $ti ( $rdg->related_readings( 'transposition' ) ) {
+                                               next unless $ti->text eq $rdg->text;
+                                               $rel = $c->get_relationship( $ti, $pobj );
+                                               if( $rel ) {
+                                                       _add_to_hash( $rel, $phash, 1 );
+                                                       last;
+                                               }
+                                       }
+                                       unless( $rel ) {
+                                               foreach my $ti ( $pobj->related_readings( 'transposition' ) ) {
+                                                       next unless $ti->text eq $pobj->text;
+                                                       $rel = $c->get_relationship( $ti, $rdg );
+                                                       if( $rel ) {
+                                                               _add_to_hash( $rel, $phash, 1 );
+                                                               last;
+                                                       }
+                                               }
+                                       }
+                               }
+                               unless( $rel ) {
+                                       # and then check for sheer word similarity.
+                                       my $rtext = $rdg->text;
+                                       my $ptext = $pobj->text;
+                                       if( similar( $rtext, $ptext ) ) {
+                                               # say STDERR "Words $rtext and $ptext judged similar";
+                                               $phash->{relation} = { type => 'wordsimilar' };
+                                       } 
+                               }
                        } else {
-                               push( @resolve, $wit );                 
+                               $phash->{relation} = { type => 'deletion' };
                        }
-               } else {
-                       my $gst = pop @{$contig->{$wit}};
-                       $contig->{$wit} = $gst || '';
+                       # Get the attributes of the parent object while we are here
+                       $phash->{'text'} = $pobj->text if $pobj;
+                       $phash->{'is_nonsense'} = $pobj->is_nonsense;
+                       $phash->{'is_ungrammatical'} = $pobj->grammar_invalid;
+               } elsif( $p eq '(omitted)' ) {
+                       $phash->{relation} = { type => 'addition' };
                }
+               # Save it
+               $rdgparents->{$p} = $phash;
        }
-       
-    if( @resolve ) {
-        my $still_contig = {};
-        foreach my $h ( @resolve ) {
-            # For each of the hypothetical readings with more than one possibility,
-            # try deleting it from each of its member subgraphs in turn, and see
-            # if that breaks the contiguous grouping.
-            # TODO This can still break in a corner case where group A can use 
-            # either vertex 1 or 2, and group B can use either vertex 2 or 1.
-            # Revisit this if necessary; it could get brute-force nasty.
-            foreach my $gst ( @{$contig->{$h}} ) {
-                my $gpart = $subgraph->{$gst}->copy();
-                # If we have come this far, there is only one root and everything
-                # is reachable from it.
-                my( $root ) = $gpart->predecessorless_vertices;    
-                my $reachable = {};
-                map { $reachable->{$_} = 1 } $gpart->vertices;
-
-                # Try deleting the hypothetical node. 
-                $gpart->delete_vertex( $h );
-                if( $h eq $root ) {
-                       # See if we still have a single root.
-                       my @roots = $gpart->predecessorless_vertices;
-                       warn "This shouldn't have happened" unless @roots;
-                       if( @roots > 1 ) {
-                               # $h is needed by this group.
-                               if( exists( $still_contig->{$h} ) ) {
-                                       # Conflict!
-                                       $conflict->{$gst} = 1;
-                                       $still_contig->{$h} = '';
-                               } else {
-                                       $still_contig->{$h} = $gst;
-                               }
-                       }
-                } else {
-                       # $h is somewhere in the middle. See if everything
-                       # else can still be reached from the root.
-                                       my %still_reachable = ( $root => 1 );
-                                       map { $still_reachable{$_} = 1 }
-                                               $gpart->all_successors( $root );
-                                       foreach my $v ( keys %$reachable ) {
-                                               next if $v eq $h;
-                                               if( !$still_reachable{$v}
-                                                       && ( $contig->{$v} eq $gst 
-                                                                || ( exists $still_contig->{$v} 
-                                                                         && $still_contig->{$v} eq $gst ) ) ) {
-                                                       # We need $h.
-                                                       if( exists $still_contig->{$h} ) {
-                                                               # Conflict!
-                                                               $conflict->{$gst} = 1;
-                                                               $still_contig->{$h} = '';
-                                                       } else {
-                                                               $still_contig->{$h} = $gst;
-                                                       }
-                                                       last;
-                                               } # else we don't need $h in this group.
-                                       } # end foreach $v
-                               } # endif $h eq $root
-            } # end foreach $gst
-        } # end foreach $h
-        
-        # Now we have some hypothetical vertices in $still_contig that are the 
-        # "real" group memberships.  Replace these in $contig.
-               foreach my $v ( keys %$contig ) {
-                       next unless ref $contig->{$v};
-                       $contig->{$v} = $still_contig->{$v};
-               }
-    } # end if @resolve
-    
-    my $is_genealogical = keys %$conflict ? JSON::false : JSON::true;
-       my $variant_row = [ [], $is_genealogical ];
-       # Fill in the groupings from $contig.
-       foreach my $g ( @$groups ) {
-       my $gst = wit_stringify( $g );
-       my @realgroup = grep { $contig->{$_} eq $gst } keys %$contig;
-       push( @{$variant_row->[0]}, \@realgroup );
-    }
-    return $variant_row;
 }
 
-sub _prune_group {
-       my( $group, $stemma, $graph ) = @_;
-       my $lacunose = {};
-       map { $lacunose->{$_} = 1 } $stemma->hypotheticals;
-       map { $lacunose->{$_} = 0 } @$group;
-       # Make our subgraph
-       my $subgraph = $graph->copy;
-       map { $subgraph->delete_vertex( $_ ) unless exists $lacunose->{$_} }
-               $subgraph->vertices;
-       # ...and find the root.
-       # Now prune and return the remaining vertices.
-       _prune_subtree( $subgraph, $lacunose );
-       return $subgraph->vertices;
+sub _add_to_hash {
+       my( $rel, $phash, $is_transposed ) = @_;
+       $phash->{relation} = { type => $rel->type };
+       $phash->{relation}->{transposed} = 1 if $is_transposed;
+       $phash->{relation}->{annotation} = $rel->annotation
+               if $rel->has_annotation;
 }
 
-sub _prune_subtree {
-       my( $tree, $lacunose ) = @_;
-       
-       # Delete lacunose witnesses that have no successors
-    my @orphan_hypotheticals;
-    my $ctr = 0;
-    do {
-       die "Infinite loop on leaves" if $ctr > 100;
-       @orphan_hypotheticals = grep { $lacunose->{$_} } 
-               $tree->successorless_vertices;
-        $tree->delete_vertices( @orphan_hypotheticals );
-        $ctr++;
-    } while( @orphan_hypotheticals );
-       
-       # Delete lacunose roots that have a single successor
-       my @redundant_root;
-       $ctr = 0;
-       do {
-       die "Infinite loop on roots" if $ctr > 100;
-               @redundant_root = grep { $lacunose->{$_} && $tree->successors( $_ ) == 1 } 
-                       $tree->predecessorless_vertices;
-               $tree->delete_vertices( @redundant_root );
-               $ctr++;
-       } while( @redundant_root );
-}
+=head2 similar( $word1, $word2 )
 
-sub _prune_subtree_old {
-    my( $tree, $root, $contighash ) = @_;
-    # First, delete hypothetical leaves / orphans until there are none left.
-    my @orphan_hypotheticals = grep { ref( $contighash->{$_} ) } 
-        $tree->successorless_vertices;
-    while( @orphan_hypotheticals ) {
-        $tree->delete_vertices( @orphan_hypotheticals );
-        @orphan_hypotheticals = grep { ref( $contighash->{$_} ) } 
-            $tree->successorless_vertices;
-    }
-    # Then delete a hypothetical root with only one successor, moving the
-    # root to the first child that has no other predecessors.
-    while( $tree->successors( $root ) == 1 && ref $contighash->{$root} ) {
-        my @nextroot = $tree->successors( $root );
-        $tree->delete_vertex( $root );
-        ( $root ) = grep { $tree->is_predecessorless_vertex( $_ ) } @nextroot;
-    }
-    # The tree has been modified in place, but we need to know the new root.
-    $root = undef unless $root && $tree->has_vertex( $root );
-    return $root;
-}
-# Add the variant, subject to a.c. representation logic.
-# This assumes that we will see the 'main' version before the a.c. version.
-sub add_variant_wit {
-    my( $arr, $wit, $acstr ) = @_;
-    my $skip;
-    if( $wit =~ /^(.*)\Q$acstr\E$/ ) {
-        my $real = $1;
-        $skip = grep { $_ =~ /^\Q$real\E$/ } @$arr;
-    } 
-    push( @$arr, $wit ) unless $skip;
+Use Algorithm::Diff to get a sense of how close the words are to each other.
+This will hopefully handle substitutions a bit more nicely than Levenshtein.
+
+=cut
+
+#!/usr/bin/env perl
+
+sub similar {
+       my( $word1, $word2 ) = sort { length($a) <=> length($b) } @_;
+       my @let1 = split( '', lc( $word1 ) );
+       my @let2 = split( '', lc( $word2 ) );
+       my $diff = Algorithm::Diff->new( \@let1, \@let2 );
+       my $mag = 0;
+       while( $diff->Next ) {
+               if( $diff->Same ) {
+                       # Take off points for longer strings
+                       my $cs = $diff->Range(1) - 2;
+                       $cs = 0 if $cs < 0;
+                       $mag -= $cs;
+               } elsif( !$diff->Items(1) ) {
+                       $mag += $diff->Range(2);
+               } elsif( !$diff->Items(2) ) {
+                       $mag += $diff->Range(1);
+               } else {
+                       # Split the difference for substitutions
+                       my $c1 = $diff->Range(1) || 1;
+                       my $c2 = $diff->Range(2) || 1;
+                       my $cd = ( $c1 + $c2 ) / 2;
+                       $mag += $cd;
+               }
+       }
+       return ( $mag <= length( $word1 ) / 2 );
 }
 
 sub _useful_variant {
-       my( $group_readings, $graph, $acstr ) = @_;
-
-       # TODO Decide what to do with AC witnesses
+       my( $rankgroup, $rankgraph, $acstr ) = @_;
 
        # Sort by group size and return
        my $is_useful = 0;
-       my( @readings, @groups );   # The sorted groups for our answer.
-       foreach my $rdg ( sort { @{$group_readings->{$b}} <=> @{$group_readings->{$a}} } 
-               keys %$group_readings ) {
-               push( @readings, $rdg );
-               push( @groups, $group_readings->{$rdg} );
-               if( @{$group_readings->{$rdg}} > 1 ) {
+       foreach my $rdg ( keys %$rankgroup ) {
+               my @wits = $rankgroup->{$rdg}->members;
+               if( @wits > 1 ) {
                        $is_useful++;
                } else {
-                       my( $wit ) = @{$group_readings->{$rdg}};
-                       $wit =~ s/^(.*)\Q$acstr\E$/$1/;
-                       $is_useful++ unless( $graph->is_sink_vertex( $wit ) );
+                       $is_useful++ unless( $rankgraph->is_sink_vertex( $wits[0] )
+                               || $wits[0] =~ /\Q$acstr\E$/ );
                }
        }
-       if( $is_useful > 1 ) {
-               return( \@readings, \@groups );
-       } else {
-               return( [], [] );
-       }
+       return $is_useful > 1;
 }
 
 =head2 wit_stringify( $groups )
@@ -1001,18 +890,15 @@ sub wit_stringify {
     return join( ' / ', @gst );
 }
 
-sub _symmdiff {
-       my( $lista, $listb ) = @_;
-       my %union;
-       my %scalars;
-       map { $union{$_} = 1; $scalars{$_} = $_ } @$lista;
-       map { $union{$_} += 1; $scalars{$_} = $_ } @$listb;
-       my @set = grep { $union{$_} == 1 } keys %union;
-       return map { $scalars{$_} } @set;
-}
-
 1;
 
+sub throw {
+       Text::Tradition::Error->throw( 
+               'ident' => 'Analysis error',
+               'message' => $_[0],
+       );
+}
+
 =head1 LICENSE
 
 This package is free software and is provided "as is" without express