lib/Traditions/Parser/GraphML.pm

   1 package Traditions::Parser::GraphML;
   2
   3 use strict;
   4 use warnings;
   5 use Traditions::Graph;
   6 use XML::LibXML;
   7 use XML::LibXML::XPathContext;
   8
   9
  10 # Takes a GraphML string; returns a Graph::Easy object.
  11
  12 sub parse {
  13     my( $graph, $graphml_str ) = @_;
  14
  15     my $parser = XML::LibXML->new();
  16     my $doc = $parser->parse_string( $graphml_str );
  17     my $collation = $doc->documentElement();
  18     my $xpc = XML::LibXML::XPathContext->new( $collation );
  19     $xpc->registerNs( 'g', 'http://graphml.graphdrawing.org/xmlns' );
  20
  21     # First get the ID keys, for witnesses and for collation data
  22     my %nodedata;
  23     my %witnesses;
  24     foreach my $k ( $xpc->findnodes( '//g:key' ) ) {
  25         # Each key has a 'for' attribute; the edge keys are witnesses, and
  26         # the node keys contain an ID and string for each node.
  27
  28         if( $k->getAttribute( 'for' ) eq 'node' ) {
  29             $nodedata{ $k->getAttribute( 'attr.name' ) } = $k->getAttribute( 'id' );
  30         } else {
  31             $witnesses{ $k->getAttribute( 'id' ) } = $k->getAttribute( 'attr.name' );
  32         }
  33     }
  34
  35     my $graph_el = $xpc->find( '/g:graphml/g:graph' )->[0];
  36
  37     # Add the nodes to the graph.  First delete the start node, because
  38     # GraphML graphs will have their own start nodes.
  39     $graph->del_node( $graph->start() );
  40     # Map from XML IDs to node name/identity
  41     my %node_name;
  42     # Keep track of whatever extra info we're passed
  43     my $extra_data = {};
  44     my @nodes = $xpc->findnodes( '//g:node' );
  45     foreach my $n ( @nodes ) {
  46         my $lookup_xpath = './g:data[@key="%s"]/child::text()';
  47         my $id = $xpc->findvalue( sprintf( $lookup_xpath, $nodedata{'number'} ), $n );
  48         my $label = $xpc->findvalue( sprintf( $lookup_xpath, $nodedata{'token'} ), $n );
  49         my $gnode = $graph->add_node( $id );
  50         $node_name{ $n->getAttribute('id') } = $id;
  51         $gnode->set_attribute( 'label', $label );
  52
  53         # Now get the rest of the data
  54         my $extra = {};
  55         my @keys = grep { $_ !~ /^(number|token)$/ } keys( %nodedata );
  56         foreach my $k ( @keys ) {
  57             my $data = $xpc->findvalue( sprintf( $lookup_xpath, $nodedata{ $k } ), $n );
  58             $extra->{ $k } = $data;
  59         }
  60         $extra_data->{ $id } = $extra;
  61     }
  62
  63     # Now add the edges.
  64     my @edges = $xpc->findnodes( '//g:edge' );
  65     foreach my $e ( @edges ) {
  66         my $from = $node_name{ $e->getAttribute('source') };
  67         my $to = $node_name{ $e->getAttribute('target') };
  68         # Label according to the witnesses present.
  69         my @wit_ids = $xpc->findnodes( './g:data/attribute::key', $e );
  70         my @wit_names = map { $witnesses{ $_->getValue() } } @wit_ids;
  71         my $label = join( ', ', @wit_names );
  72
  73         $graph->add_edge( $from, $to, $label );
  74     }
  75
  76     ## Reverse the node_name hash so that we have two-way lookup.
  77     my %node_id = reverse %node_name;
  78     ## TODO mark transpositions somehow.
  79
  80     # Find the beginning and end nodes of the graph.  The beginning node
  81     # has no incoming edges; the end node has no outgoing edges.
  82     my( $begin_node, $end_node );
  83     foreach my $gnode ( $graph->nodes() ) {
  84         print STDERR "Checking node " . $gnode->name . "\n";
  85         my @outgoing = $gnode->outgoing();
  86         my @incoming = $gnode->incoming();
  87
  88         unless( scalar @incoming ) {
  89             warn "Already have a beginning node" if $begin_node;
  90             my $node_xml_id = $node_id{ $gnode->name() };
  91             my @bn = $xpc->findnodes( '//g:node[@id="' . $node_xml_id . '"]' );
  92             warn "XPath did not find a node for id $node_xml_id"
  93                 unless scalar @bn;
  94             $begin_node = $bn[0];
  95             $graph->start( $gnode );
  96             $node_name{ 0 } = '#START#';
  97             $node_id{'#START#'} = 0;
  98         }
  99         unless( scalar @outgoing ) {
 100             warn "Already have an ending node" if $end_node;
 101             my $node_xml_id = $node_id{ $gnode->name() };
 102             my @bn = $xpc->findnodes( '//g:node[@id="' . $node_xml_id . '"]' );
 103             warn "XPath did not find a node for id $node_xml_id"
 104                 unless scalar @bn;
 105             $end_node = $bn[0];
 106         }
 107     }
 108
 109     # Now for each witness, walk the path through the graph.
 110     # Then we need to find the common nodes.
 111     # TODO This method is going to fall down if we have a very gappy
 112     # text in the collation.
 113     # TODO think about whether it makes more sense to do this in the
 114     # XML or in the graph. Right now it's the XML.
 115     my $paths = {};
 116     my @common_nodes;
 117     foreach my $wit ( keys %witnesses ) {
 118         my $node_id = $begin_node->getAttribute('id');
 119         my @wit_path = ( $node_name{ $node_id } );
 120         # TODO Detect loops at some point
 121         while( $node_id != $end_node->getAttribute('id') ) {
 122             # Find the node which is the target of the edge whose
 123             # source is $node_id and applies to this witness.
 124             my $xpath_expr = '//g:edge[child::g:data[@key="'
 125                 . $wit . '"] and attribute::source="'
 126                 . $node_id . '"]';
 127             my $next_edge = $xpc->find( $xpath_expr, $graph_el )->[0];
 128             $node_id = $next_edge->getAttribute('target');
 129             push( @wit_path, $node_name{ $node_id } );
 130         }
 131         $paths->{ $witnesses{ $wit }} = \@wit_path;
 132         if( @common_nodes ) {
 133             my @cn;
 134             foreach my $n ( @wit_path) {
 135                 push( @cn, $n ) if grep { $_ eq $n } @common_nodes;
 136             }
 137             @common_nodes = ();
 138             push( @common_nodes, @cn );
 139         } else {
 140             push( @common_nodes, @wit_path );
 141         }
 142     }
 143
 144     # Mark all the nodes as either common or not.
 145     foreach my $cn ( @common_nodes ) {
 146         print STDERR "Setting $cn as common node\n";
 147         $graph->node( $cn )->set_attribute( 'class', 'common' );
 148     }
 149     foreach my $n ( $graph->nodes() ) {
 150         $n->set_attribute( 'class', 'variant' )
 151             unless $n->get_attribute( 'class' ) eq 'common';
 152     }
 153
 154     # And then we have to calculate the position identifiers for
 155     # each word, keyed on the common nodes.  This will be 'fun'.
 156     # The end result is a hash per witness, whose key is the word
 157     # node and whose value is its position in the text.  Common
 158     # nodes are always N,1 so have identical positions in each text.
 159     my $wit_indices = {};
 160     my $positions = {};
 161     foreach my $wit ( values %witnesses ) {
 162         my $wit_matrix = [];
 163         my $cn = 0;
 164         my $row = [];
 165         foreach my $wn ( @{$paths->{$wit}} ) {
 166             if( $wn eq $common_nodes[$cn] ) {
 167                 $cn++;
 168                 push( @$wit_matrix, $row ) if scalar( @$row );
 169                 $row = [];
 170             }
 171             push( @$row, $wn );
 172         }
 173         push( @$wit_matrix, $row );
 174         # Now we have a matrix; we really want to invert this.
 175         my $wit_index;
 176         foreach my $li ( 1..scalar(@$wit_matrix) ) {
 177             foreach my $di ( 1..scalar(@{$wit_matrix->[$li-1]}) ) {
 178                 $wit_index->{ $wit_matrix->[$li-1]->[$di-1] } = "$li,$di";
 179                 $positions->{ "$li,$di" } = 1;
 180             }
 181         }
 182
 183         $wit_indices->{$wit} = $wit_index;
 184     }
 185     $graph->save_positions( $positions, $wit_indices );
 186 }
 187
 188 1;