3
$\begingroup$

What algorithms/heuristics exist for efficiently determining the relative order between two elements in a partially ordered set?

In my case, the PO-set is stored as a directed acyclic graph where an edge is an happened before relation and I am streaming live data into this PO-set. Nodes usually have less than 5 backward edges, with 1 being the most common, and there will be at most 10^6 nodes. The newly inserted nodes usually have edges to the previously most recently inserted nodes.

I am usually doing this query just after I've added a node to the graph, to find the relative ordering between the inserted node and a few select other nodes, so the traversal paths tend to overlap a lot. I am also maintaining a total order of the PO-set as I go, which might be useful for this as well.

My current solution consists of starting at both nodes and moving backwards one step at a time from both simultaneously (or rather, one step for the left node, then one step for the right) until I find a common ancestor node, or run out of edges to traverse. This is not very fast, but I don't have that many elements in the set yet so it works for now.

The main problem is the worst case runtime of O(n) as n will grow in the future. Is there a way to do this faster?

$\endgroup$
1
$\begingroup$

This is the dynamic reachability problem for DAGs, where you only need to handle vertex/edge insertion (but not deletion). It's sometimes known as incremental reachability or incremental DAG reachability.

There's lots written in the research literature on the subject. Here are some pointers to get you started:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.