X-Git-Url: http://git.shadowcat.co.uk/gitweb/gitweb.cgi?a=blobdiff_plain;f=lib%2FText%2FTradition%2FParser%2FGraphML.pm;h=a4d57177aeac71ac07ff0e398cba8b95c2131fe7;hb=5ac9acd842b39856560430f8268b00364983a017;hp=19b294cbc6779ce18b4d0b3c7187709db04b5ed6;hpb=2ceca8c3211427df102bec429c6b6397dda8f9b4;p=scpubgit%2Fstemmatology.git diff --git a/lib/Text/Tradition/Parser/GraphML.pm b/lib/Text/Tradition/Parser/GraphML.pm index 19b294c..a4d5717 100644 --- a/lib/Text/Tradition/Parser/GraphML.pm +++ b/lib/Text/Tradition/Parser/GraphML.pm @@ -2,9 +2,14 @@ package Text::Tradition::Parser::GraphML; use strict; use warnings; +use Exporter 'import'; +use vars qw/ @EXPORT_OK $xpc /; + use XML::LibXML; use XML::LibXML::XPathContext; +@EXPORT_OK = qw/ graphml_parse /; + =head1 NAME Text::Tradition::Parser::GraphML @@ -12,183 +17,135 @@ Text::Tradition::Parser::GraphML =head1 DESCRIPTION Parser module for Text::Tradition, given a GraphML file that describes -a collation graph. For further information on the GraphML format for -text collation, see http://gregor.middell.net/collatex/ +a collation graph. Returns the information about the graph that has +been parsed out from the GraphML. This module is meant to be used +with a module (e.g. CollateX or Self) that interprets the specific +GraphML conventions of the source program. =head1 METHODS -=over - -=item B +=head2 B( $init_opts ) -parse( $graph, $graphml_string ); +parse( $init_opts ); -Takes an initialized Text::Tradition::Graph object and a string -containing the GraphML; creates the appropriate nodes and edges on the -graph. +Takes a set of Tradition initialization options, among which should be either +'file' or 'string'; parses that file or string and returns a list of nodes, edges, +and their associated data. =cut -sub parse { - my( $graph, $graphml_str ) = @_; +# Return graph -> nodeid -> { key1/val1, key2/val2, key3/val3 ... } +# -> edgeid -> { source, target, wit1/val1, wit2/val2 ...} + +sub graphml_parse { + my( $opts ) = @_; my $parser = XML::LibXML->new(); - my $doc = $parser->parse_string( $graphml_str ); - my $collation = $doc->documentElement(); - my $xpc = XML::LibXML::XPathContext->new( $collation ); + my $doc; + if( exists $opts->{'string'} ) { + $doc = $parser->parse_string( $opts->{'string'} ); + } elsif ( exists $opts->{'file'} ) { + $doc = $parser->parse_file( $opts->{'file'} ); + } else { + warn "Could not find string or file option to parse"; + return; + } + + my( $graphattr, $nodedata, $edgedata ) = ( {}, {}, {} ); + my $graphml = $doc->documentElement(); + $xpc = XML::LibXML::XPathContext->new( $graphml ); $xpc->registerNs( 'g', 'http://graphml.graphdrawing.org/xmlns' ); - # First get the ID keys, for witnesses and for collation data - my %nodedata; - my %witnesses; + # First get the ID keys, for node/edge data and for collation data foreach my $k ( $xpc->findnodes( '//g:key' ) ) { - # Each key has a 'for' attribute; the edge keys are witnesses, and - # the node keys contain an ID and string for each node. - - if( $k->getAttribute( 'for' ) eq 'node' ) { - $nodedata{ $k->getAttribute( 'attr.name' ) } = $k->getAttribute( 'id' ); - } else { - $witnesses{ $k->getAttribute( 'id' ) } = $k->getAttribute( 'attr.name' ); - } + # Each key has a 'for' attribute to say whether it is for graph, + # node, or edge. + my $keyid = $k->getAttribute( 'id' ); + my $keyname = $k->getAttribute( 'attr.name' ); + + # Keep track of the XML identifiers for the data carried + # in each node element. + my $dtype = $k->getAttribute( 'for' ); + if( $dtype eq 'graph' ) { + $graphattr->{$keyid} = $keyname; + } elsif( $dtype eq 'node' ) { + $nodedata->{$keyid} = $keyname; + } else { + $edgedata->{$keyid} = $keyname; + } } - my $graph_el = $xpc->find( '/g:graphml/g:graph' )->[0]; - - # Add the nodes to the graph. First delete the start node, because - # GraphML graphs will have their own start nodes. - $graph->del_node( $graph->start() ); - # Map from XML IDs to node name/identity - my %node_name; - # Keep track of whatever extra info we're passed - my $extra_data = {}; - my @nodes = $xpc->findnodes( '//g:node' ); - foreach my $n ( @nodes ) { - my $lookup_xpath = './g:data[@key="%s"]/child::text()'; - my $id = $xpc->findvalue( sprintf( $lookup_xpath, $nodedata{'number'} ), $n ); - my $label = $xpc->findvalue( sprintf( $lookup_xpath, $nodedata{'token'} ), $n ); - my $gnode = $graph->add_node( $id ); - $node_name{ $n->getAttribute('id') } = $id; - $gnode->set_attribute( 'label', $label ); - - # Now get the rest of the data - my $extra = {}; - my @keys = grep { $_ !~ /^(number|token)$/ } keys( %nodedata ); - foreach my $k ( @keys ) { - my $data = $xpc->findvalue( sprintf( $lookup_xpath, $nodedata{ $k } ), $n ); - $extra->{ $k } = $data; - } - $extra_data->{ $id } = $extra; - } + my @returned_graphs; + foreach my $graph_el ( $xpc->findnodes( '/g:graphml/g:graph' ) ) { + my $graph_hash = { 'nodes' => [], + 'edges' => [], + 'name' => $graph_el->getAttribute( 'id' ) }; + + my $node_reg = {}; + + # Read in graph globals (if any). + # print STDERR "Reading graphml global data\n"; + foreach my $dkey ( keys %$graphattr ) { + my $keyname = $graphattr->{$dkey}; + my $keyvalue = _lookup_node_data( $graph_el, $dkey ); + $graph_hash->{'global'}->{$keyname} = $keyvalue if defined $keyvalue; + } - # Now add the edges. - my @edges = $xpc->findnodes( '//g:edge' ); - foreach my $e ( @edges ) { - my $from = $node_name{ $e->getAttribute('source') }; - my $to = $node_name{ $e->getAttribute('target') }; - # Label according to the witnesses present. - my @wit_ids = $xpc->findnodes( './g:data/attribute::key', $e ); - my @wit_names = map { $witnesses{ $_->getValue() } } @wit_ids; - my $label = join( ', ', @wit_names ); - - $graph->add_edge( $from, $to, $label ); - } - - ## Reverse the node_name hash so that we have two-way lookup. - my %node_id = reverse %node_name; - - ## Record the nodes that are marked as transposed. - my $tr_xpath = '//g:node[g:data[@key="' . $nodedata{'identity'} . '"]]'; - my $transposition_nodes = $xpc->find( $tr_xpath ); - foreach my $tn ( @$transposition_nodes ) { - my $id_xpath = sprintf( './g:data[@key="%s"]/text()', - $nodedata{'identity'} ); - $graph->set_identical_node( $node_name{ $tn->getAttribute( 'id' ) }, - $node_name{ $xpc->findvalue( $id_xpath, - $tn ) } ); - } - - - # Find the beginning and end nodes of the graph. The beginning node - # has no incoming edges; the end node has no outgoing edges. - my( $begin_node, $end_node ); - foreach my $gnode ( $graph->nodes() ) { - print STDERR "Checking node " . $gnode->name . "\n"; - my @outgoing = $gnode->outgoing(); - my @incoming = $gnode->incoming(); - - unless( scalar @incoming ) { - warn "Already have a beginning node" if $begin_node; - my $node_xml_id = $node_id{ $gnode->name() }; - my @bn = $xpc->findnodes( '//g:node[@id="' . $node_xml_id . '"]' ); - warn "XPath did not find a node for id $node_xml_id" - unless scalar @bn; - $begin_node = $bn[0]; - $graph->start( $gnode ); - $node_name{ 0 } = '#START#'; - $node_id{'#START#'} = 0; - } - unless( scalar @outgoing ) { - warn "Already have an ending node" if $end_node; - my $node_xml_id = $node_id{ $gnode->name() }; - my @bn = $xpc->findnodes( '//g:node[@id="' . $node_xml_id . '"]' ); - warn "XPath did not find a node for id $node_xml_id" - unless scalar @bn; - $end_node = $bn[0]; - } + # Add the nodes to the graph hash. + # print STDERR "Reading graphml nodes\n"; + my @nodes = $xpc->findnodes( './/g:node', $graph_el ); + foreach my $n ( @nodes ) { + # Could use a better way of registering these + my $node_hash = {}; + foreach my $dkey ( keys %$nodedata ) { + my $keyname = $nodedata->{$dkey}; + my $keyvalue = _lookup_node_data( $n, $dkey ); + $node_hash->{$keyname} = $keyvalue if defined $keyvalue; + } + $node_reg->{$n->getAttribute( 'id' )} = $node_hash; + push( @{$graph_hash->{'nodes'}}, $node_hash ); + } + + # Now add the edges, and cross-ref with the node objects. + # print STDERR "Reading graphml edges\n"; + my @edges = $xpc->findnodes( './/g:edge', $graph_el ); + foreach my $e ( @edges ) { + my $from = $e->getAttribute('source'); + my $to = $e->getAttribute('target'); + + # We don't know whether the edge data is one per witness + # or one per witness type, or something else. So we just + # save it and let our calling parser decide. + my $edge_hash = { + 'source' => $node_reg->{$from}, + 'target' => $node_reg->{$to}, + }; + foreach my $wkey( keys %$edgedata ) { + my $wname = $edgedata->{$wkey}; + my $wlabel = _lookup_node_data( $e, $wkey ); + $edge_hash->{$wname} = $wlabel if $wlabel; + } + push( @{$graph_hash->{'edges'}}, $edge_hash ); + } + push( @returned_graphs, $graph_hash ); } + return @returned_graphs; +} - # Now for each witness, walk the path through the graph. - # Then we need to find the common nodes. - # TODO This method is going to fall down if we have a very gappy - # text in the collation. - # TODO think about whether it makes more sense to do this in the - # XML or in the graph. Right now it's the XML. - my $paths = {}; - my @common_nodes; - foreach my $wit ( keys %witnesses ) { - my $node_id = $begin_node->getAttribute('id'); - my @wit_path = ( $node_name{ $node_id } ); - # TODO Detect loops at some point - while( $node_id != $end_node->getAttribute('id') ) { - # Find the node which is the target of the edge whose - # source is $node_id and applies to this witness. - my $xpath_expr = '//g:edge[child::g:data[@key="' - . $wit . '"] and attribute::source="' - . $node_id . '"]'; - my $next_edge = $xpc->find( $xpath_expr, $graph_el )->[0]; - $node_id = $next_edge->getAttribute('target'); - push( @wit_path, $node_name{ $node_id } ); - } - $paths->{ $witnesses{ $wit }} = \@wit_path; - if( @common_nodes ) { - my @cn; - foreach my $n ( @wit_path) { - push( @cn, $n ) if grep { $_ eq $n } @common_nodes; - } - @common_nodes = (); - push( @common_nodes, @cn ); - } else { - push( @common_nodes, @wit_path ); - } - } - # Mark all the nodes as either common or not. - foreach my $cn ( @common_nodes ) { - print STDERR "Setting $cn as common node\n"; - $graph->node( $cn )->set_attribute( 'class', 'common' ); +sub _lookup_node_data { + my( $xmlnode, $key ) = @_; + my $lookup_xpath = './g:data[@key="%s"]/child::text()'; + my $data = $xpc->find( sprintf( $lookup_xpath, $key ), $xmlnode ); + # If we get back an empty nodelist, we return undef. + if( ref( $data ) ) { + return undef unless $data->size; + return $data->to_literal->value; } - foreach my $n ( $graph->nodes() ) { - $n->set_attribute( 'class', 'variant' ) - unless $n->get_attribute( 'class' ) eq 'common'; - } - - # Now calculate graph positions. - $graph->make_positions( \@common_nodes, $paths ); - + # Otherwise we got back a value. Return it. + return $data; } -=back - =head1 LICENSE This package is free software and is provided "as is" without express