Re: [agtk-devel] topological sorting of anchors

[Steven B. <sb...@un...>]

Mark Liberman wrote:
> It might be appropriate to use the 'sort' command and 'qsort' function
> as models.

I think this is an excellent suggestion for where we should start...

>  A.1------>A.2----->A.3   B.1----->B.2----->B.3
>  0.1                0.3   1.6               1.9
> 
> we can prove that B.2 must be later than A.2, but neither a topological
> sort nor a temporal sort (of the explicit kind at least) tells us this
> directly.

Note that prec (defined as in my last posting) will do this.  However, we
don't maintain this information in AGLIB, since it gets about as complex as
a truth maintenance system (updates can have non-local consequences; a
single unsetAnchorOffset may lead to having to retract unbounded amounts of
precedence data).

> It would also not be terribly hard to associate time ranges with nodes
> that lack time marks but are connected to nodes that do. Perhaps
> something like this is already done to ensure that new time marks are
> consistent with old ones?

No, but there's a paper which discusses this proposal in detail
(section 6, Bird, Buneman & Tan 2000, http://arXiv.org/abs/cs/0007023)

Pace my comments above, perhaps we need to think about how to integrate
this into AGLIB.  For some applications it will improve efficiency (but it
could be a significant overhead for others).

-S