1 package Text::Tradition::Parser::GraphML;
6 use XML::LibXML::XPathContext;
10 Text::Tradition::Parser::GraphML
14 Parser module for Text::Tradition, given a GraphML file that describes
15 a collation graph. For further information on the GraphML format for
16 text collation, see http://gregor.middell.net/collatex/
24 parse( $graph, $graphml_string );
26 Takes an initialized Text::Tradition::Graph object and a string
27 containing the GraphML; creates the appropriate nodes and edges on the
33 my( $collation, $graphml_str ) = @_;
35 my $parser = XML::LibXML->new();
36 my $doc = $parser->parse_string( $graphml_str );
37 my $graphml = $doc->documentElement();
38 my $xpc = XML::LibXML::XPathContext->new( $graphml );
39 $xpc->registerNs( 'g', 'http://graphml.graphdrawing.org/xmlns' );
41 # First get the ID keys, for witnesses and for collation data
44 foreach my $k ( $xpc->findnodes( '//g:key' ) ) {
45 # Each key has a 'for' attribute; the edge keys are witnesses, and
46 # the node keys contain an ID and string for each node.
48 if( $k->getAttribute( 'for' ) eq 'node' ) {
49 $nodedata{ $k->getAttribute( 'attr.name' ) } = $k->getAttribute( 'id' );
51 $witnesses{ $k->getAttribute( 'id' ) } = $k->getAttribute( 'attr.name' );
55 my $graph_el = $xpc->find( '/g:graphml/g:graph' )->[0];
57 # Add the nodes to the graph. First delete the start node, because
58 # GraphML graphs will have their own start nodes.
59 $collation->del_reading( $collation->start() );
60 # Map from XML IDs to node name/identity
62 # Keep track of whatever extra info we're passed
64 my @nodes = $xpc->findnodes( '//g:node' );
65 foreach my $n ( @nodes ) {
66 my $lookup_xpath = './g:data[@key="%s"]/child::text()';
67 my $id = $xpc->findvalue( sprintf( $lookup_xpath, $nodedata{'number'} ), $n );
68 my $label = $xpc->findvalue( sprintf( $lookup_xpath, $nodedata{'token'} ), $n );
69 my $gnode = $collation->add_reading( $id );
70 $node_name{ $n->getAttribute('id') } = $id;
71 $gnode->set_attribute( 'label', $label );
73 # Now get the rest of the data
75 my @keys = grep { $_ !~ /^(number|token)$/ } keys( %nodedata );
76 foreach my $k ( @keys ) {
77 my $data = $xpc->findvalue( sprintf( $lookup_xpath, $nodedata{ $k } ), $n );
78 $extra->{ $k } = $data;
80 $extra_data->{ $id } = $extra;
84 my @edges = $xpc->findnodes( '//g:edge' );
85 foreach my $e ( @edges ) {
86 my $from = $node_name{ $e->getAttribute('source') };
87 my $to = $node_name{ $e->getAttribute('target') };
88 # Label according to the witnesses present.
89 my @wit_ids = $xpc->findnodes( './g:data/attribute::key', $e );
90 my @wit_names = map { $witnesses{ $_->getValue() } } @wit_ids;
91 my $label = join( ', ', @wit_names );
93 $collation->add_path( $from, $to, $label );
96 ## Reverse the node_name hash so that we have two-way lookup.
97 my %node_id = reverse %node_name;
99 ## Record the nodes that are marked as transposed.
100 my $tr_xpath = '//g:node[g:data[@key="' . $nodedata{'identical'} . '"]]';
101 my $transposition_nodes = $xpc->find( $tr_xpath );
102 foreach my $tn ( @$transposition_nodes ) {
103 my $id_xpath = sprintf( './g:data[@key="%s"]/text()',
104 $nodedata{'identical'} );
105 $collation->reading( $node_id{ $tn->getAttribute( 'id' ) } )->
106 set_identical( $collation->reading(
107 $node_name{ $xpc->findvalue( $id_xpath, $tn ) } ) );
111 # Find the beginning and end nodes of the graph. The beginning node
112 # has no incoming edges; the end node has no outgoing edges.
113 my( $begin_node, $end_node );
114 foreach my $gnode ( $collation->readings() ) {
115 print STDERR "Checking node " . $gnode->name . "\n";
116 my @outgoing = $gnode->outgoing();
117 my @incoming = $gnode->incoming();
119 unless( scalar @incoming ) {
120 warn "Already have a beginning node" if $begin_node;
121 my $node_xml_id = $node_id{ $gnode->name() };
122 my @bn = $xpc->findnodes( '//g:node[@id="' . $node_xml_id . '"]' );
123 warn "XPath did not find a node for id $node_xml_id"
125 $begin_node = $bn[0];
126 $collation->start( $gnode );
127 $node_name{ $begin_node->getAttribute( 'id' ) } = '#START#';
128 $node_id{'#START#'} = $begin_node->getAttribute( 'id' );
130 unless( scalar @outgoing ) {
131 warn "Already have an ending node" if $end_node;
132 my $node_xml_id = $node_id{ $gnode->name() };
133 my @bn = $xpc->findnodes( '//g:node[@id="' . $node_xml_id . '"]' );
134 warn "XPath did not find a node for id $node_xml_id"
140 # Now for each witness, walk the path through the graph.
141 # Then we need to find the common nodes.
142 # TODO This method is going to fall down if we have a very gappy
143 # text in the collation.
144 # TODO think about whether it makes more sense to do this in the
145 # XML or in the graph. Right now it's the XML.
148 foreach my $wit ( keys %witnesses ) {
149 my $node_id = $begin_node->getAttribute('id');
150 my @wit_path = ( $node_name{ $node_id } );
151 # TODO Detect loops at some point
152 while( $node_id ne $end_node->getAttribute('id') ) {
153 # Find the node which is the target of the edge whose
154 # source is $node_id and applies to this witness.
155 my $xpath_expr = '//g:edge[child::g:data[@key="'
156 . $wit . '"] and attribute::source="'
158 my $next_edge = $xpc->find( $xpath_expr, $graph_el )->[0];
159 print STDERR " - at $wit / $node_id\n";
160 $node_id = $next_edge->getAttribute('target');
161 push( @wit_path, $node_name{ $node_id } );
163 $paths->{ $witnesses{ $wit }} = \@wit_path;
164 if( @common_nodes ) {
166 foreach my $n ( @wit_path) {
167 push( @cn, $n ) if grep { $_ eq $n } @common_nodes;
170 push( @common_nodes, @cn );
172 push( @common_nodes, @wit_path );
176 # Mark all the nodes as either common or not.
177 foreach my $cn ( @common_nodes ) {
178 print STDERR "Setting $cn as common node\n";
179 $collation->reading( $cn )->set_attribute( 'class', 'common' );
181 foreach my $n ( $collation->readings() ) {
182 $n->set_attribute( 'class', 'variant' )
183 unless $n->get_attribute( 'class' ) eq 'common';
186 # Now calculate graph positions.
187 # $collation->make_positions( \@common_nodes, $paths );
195 This package is free software and is provided "as is" without express
196 or implied warranty. You can redistribute it and/or modify it under
197 the same terms as Perl itself.
201 Tara L Andrews, aurum@cpan.org