Node order and walking

[Dirk Roorda]

Ok, a big LAF resource has been parsed by POIO, and the graph has been constructed in memory. 

Now you want to do things with it.

One of the first things is: walk through all nodes that correspond with a word, in primary-data-order, and output the values of a few selected features for each node.

In more general terms: take a subset of the graph, order the nodes in primary-data-order, and take feature values.

Or even more abstractly: take a projection of the primary data on the feature value space along an ordered subset of nodes.

This cannot easily be done, because of lack of order. The LAF model does not specify order much: only the outgoing edges of nodes are ordered, but nodes in general are not ordered.

Yet the LAF model defines an implicit, natural order on nodes (in fact there are several such orders possible). These orders come from the fact that the anchors into the primary data are (totally) ordered.

Let me define the left-to-right-outermost-innermost ordering, first on regions, then on nodes.

The regions: a region is an interval (begin, end) in anchor-space. You can state that intervals that start before other intervals come earlier and that intervals that contain other intervals come earlier.

Formally (b1, e1) < (b2, e2) is by definition { b1 < b2 } or { b1 == b2 and e2 < e1 }

This is a total order on regions.

Now a node is linked to one or more regions. How do two nodes compare in this ordering? 

Order the regions of both nodes. The compare the first regions of both nodes to each other with the above order on regions. The outcome is the order of the two nodes.

Now my question to you, Peter, is: is this order a useful notion, and is it worthwhile to make this order available through the graf-python API, either as a list or as an iterator?

[pbouda]

Yes, that definitely makes sense. I agree that there should be an order as proposed in graf-python. At the moment the nodes are already ordered in a list, but just in the order in which they are added to the GrAF. Afaik the SAX-Parser makes sure that they are added in the order of the XML file, for example.

I suggest that we create a second iterator for your proposed order. What to do with nodes that don't link to a region? Probably the iterator shoudl only return nodes that are linked to a region, then.