Automatic transformation of XML namespaces/Implementation/Precedences/Old answer

DAG is an abbreviation of directed acyclic graph.

Precedences system is a set of precedences where a precedence is a nonempty set (of transformations). A precedence is higher that another precedence (denoted ) if every element of is higher than every element of .

I will call axiomatic precedences system a pair of nonstrict partial order (generated by a given DAG) and the strict partial order and conforming to the formula:

.

Proposition Axiomatic precedence system can be instead characterized by the formula . (FIXME: in this formula has two different meanings.)

Proof Equivalently transforming, the formula we get:

Proposition Every axiomatic precedences system is isomorphic to a set-valued precedences system. (The reverse is obvious.)

Proof https://math.stackexchange.com/a/2600852/4876

Proposition If a pair of DAGs does not generate a system of precedences, then adding new edges to these DAGs cannot make it to generate a system of precedences.

Proof ??

We need to find the minimal order which contains a given (by the DAG) order and constitute a precedences system together with a given partial order . (FIXME: I (yet) cannot rule out that there may be multiple minimal orders!)

The algorithm

edit

An (edited) copy of a deleted https://cs.stackexchange.com answer by the user D.W.:

Let me first suggest what data structure to use to store these partial orders. I suggest you represent each partial order as a dag (directed acyclic graph), via its " Hasse diagram. In other words, you build a dag to represent the relationships that are given: if you're given  , you add an edge  .

The partial order represented by a dag is the transitive closure of that dag. You never need to explicitly build the transitive closure. Rather, given  , to test whether  , you do a reachability query: you check whether   is reachable from   in the graph (e.g., with DFS or BFS). If you're given a new relationship  , you add the edge   to the dag; also, you check whether   (i.e., whether   is reachable from  ), as if so, then this is no longer a partial order and there doesn't exist any partial order consistent with the relationships you've been given.

That covers how to store and manage these relationships.

Now let's consider how to handle the condition connecting these two partial orders. Let   represent the "is subclass of" relation, and   represent the "is higher than" relation. Then your condition is: if   and   and   then  .

You can maintain the partial orders to ensure that condition holds. We'll represent the   partial order with one dag; I'll write its edges using  . We'll represent the   partial order with a second dag; I'll write its edges using  . Any time we an edge   (in the dag for  ), we'll update it to represent all the other relationships implied by your condition. Naively, we could do this by iterating over all possible values of   and adding more edges to the dag for   as required by the condition. However, that would be a bit slow. I'll describe a more efficient way to achieve the same result.

Let's triple the number of nodes in the dag for  , i.e., triple the number of elements. For each element  , we'll create two more artificial elements   and  , with extra relationships according to the following rules: if  , then   and  ; and if  , then  . These encode the condition you want to enforce, as if   and  , then we'll have   and thus   will be implied.

So instead of enforcing your condition, we'll enforce my replacement rule. In particular, we enforce my rule as follows:

  • Any time a vertex   is added, add also edge  .
  • Any time a vertex   is added, add also edge  .
  • Any time you add an edge  , also add the edge  .
  • Any time you add an edge  , also add the edge  .

You now get two dags that interact: whenever you add an edge to the dag for  , you have to add some edges to the other dag as well. (Fortunately, the changes don't cascade: the two rules above only apply to unstarred elements, so when you add the edge  , it doesn't trigger adding any more edges.)

First, we will prove  . Let for example   and   (or we can have any number of steps). Then we have   and   and consequently  .

Let now prove  . Let for example   and   (or we can have any number of steps). Then we have  , thus  .

Now this gives a clean solution to your problem. Any time you learn about a new relationship, add it to the dag and make any additional changes required by the above rules. Any time you add an edge to the dag, immediately check to make sure the dag remains a partial order. If you want to know whether two elements are related, do a reachability query in the appropriate dag.

Since you never have to build the transitive closure explicitly, this should be pretty space-efficient. Adding edges to the dag can be done in   time. Reachability queries might take linear time, but perhaps that is OK.

If you want to make the reachability queries faster, then there are algorithms and data structures for that as well. You want algorithms for incremental reachability in a dag (also called dynamic reachability for dags). This has been studied in the literature. It's possible that one of those algorithms might be more efficient, but I'm not sure, and it will probably also be more complex to implement. See, e.g., https://cstheory.stackexchange.com/q/18787/5038, https://cstheory.stackexchange.com/q/25298/5038, Efficiently determine relative ordering between two elements in a PO-set, How to evaluate relations in a DAG?, https://cstheory.stackexchange.com/q/29/5038.