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
+
+=head1 DESCRIPTION
+
+Parser module for Text::Tradition, given a GraphML file that describes
+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
+
+=head2 B<graphml_parse>( $init_opts )
-# Takes a GraphML string; returns a Graph::Easy object.
+parse( $init_opts );
-sub parse {
- my( $graph, $graphml_str ) = @_;
+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
+
+# 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 ) } );
+ # 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;
+}
- # 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];
- }
+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;
}
+ # Otherwise we got back a value. Return it.
+ return $data;
+}
+
+=head1 LICENSE
- # 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 );
- }
- }
+This package is free software and is provided "as is" without express
+or implied warranty. You can redistribute it and/or modify it under
+the same terms as Perl itself.
- # 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' );
- }
- foreach my $n ( $graph->nodes() ) {
- $n->set_attribute( 'class', 'variant' )
- unless $n->get_attribute( 'class' ) eq 'common';
- }
+=head1 AUTHOR
- # Now calculate graph positions.
- $graph->make_positions( \@common_nodes, $paths );
+Tara L Andrews, aurum@cpan.org
+
+=cut
-}
-
1;