7
$\begingroup$

I'm working on a type system and hit upon a problem that seems similar to lowest common ancestor. Given two types, I need to find the smallest sequence of conversions which will result in the same target type. If I had a simple type tree I know how to get the result, but unfortunately I have a slightly more complex graph structure.

That graph has a few key points. It is unidirectional and no loops are ever formed. Due to an unlimited number of types however it cannot be produced statically. The distance of a path is generally quite low. It "feels" more like a tree with a bunch of shortcut edges.

Initially I looked at lowest common ancestor, but it is mainly described as a tree algorithm. I've not yet given up hope that I could adapt it. The other possibility would be a more generic path-finding algorithm.

I'm hoping somebody has seen this problem before, or a similar one, and can give me some references on how to further approach it. It seems familiar enough that I assume something must exist and I'm just searching for the wrong terms/names.


Here's my attempt to describe this more formally.

Let there be a graph $G = \{ V \}$ such that each vertex has a set of outgoing edges $V = \{ E=V_x \}$. Note, as the graph is dynamic, possibly infinite, there is no way to construct the form $G = \{V, E=(V_x,V_y)\}$ for the entire graph.

A path is formed from a vertex by following any of the available edges from that node. $Pnm_x = V_n, ..., V_m$. The length of this path is equal to the number of vertices in the sequence. There is no cycle possible. The set of all paths between two nodes is expressed as $Pnm = \{ V_n, ..., V_m \}$.

Note that $Pnm$ can be determined to be empty in a finite number of steps. Enumerating the entire $Pnm$ set is not practically possible.

The problem is finding the shortest path from two vertices to a third vertex. That is, given $V_a, V_b$, find $V_c$ such that paths $Pac_x$ and $Pbc_y$ exist and $length(Pac_x) + length(Pbc_y)$ is minimal.

$\endgroup$
  • 1
    $\begingroup$ A directed graph with no directed cycles is known as a DAG. In your case, you say that the graph contains no loops. Can it contain cycles? $\endgroup$ – Yuval Filmus Mar 18 '13 at 20:52
  • 1
    $\begingroup$ Also, can you state your problem more formally? Here is one possibility Given $x,y$, you're looking for a node $z$ that minimizes $d(z,x)+d(z,y)$, where $d$ is the directed distance. Also, given a node, can you enumerate all edges pointing at it, in other words, all immediate ancestors? $\endgroup$ – Yuval Filmus Mar 18 '13 at 20:54
  • 1
    $\begingroup$ I would have assumed one has to minimize $\max{d(z,x),d(z,y)}$. Does your lowest ancestor exist in every case (i.e.: Is there a "root" like java.lang.Object)? $\endgroup$ – frafl Mar 18 '13 at 21:40
  • $\begingroup$ Editted. Given a node, yes, you can enumerate all its immediate ancestors. No, there is no common root and no guarantee that two types have a common ancestor. $\endgroup$ – edA-qa mort-ora-y Mar 19 '13 at 4:12
  • 1
    $\begingroup$ Note that "you can enumerate all its immediate ancestors" doesn't imply that the number of immediate ancestors is finite, which is probably what you want to say. If the "find the shortest path" rule is just intended as an ad hoc way to resolve ambiguities in the type system, then it might turn out to have some undesirable properties. If on the other hand, you could show that it doesn't have undesirable properties if used appropriately, that would be an interesting result. Otherwise, the "least upper bound" in the poset would be the more natural interpretation of "lowest common ancestor". $\endgroup$ – Thomas Klimpel Mar 19 '13 at 8:15
5
$\begingroup$

If the lowest common ancestor of two types always exists and is unique, then your structure is a join-semilattice. Computing the lowest common ancestor is possible, but the worst case runtime complexity is not as good as I would have expected intuitively. I asked a related question some time ago, but was too lazy to write an answer after I found the relevant solution in the "literature". I just wrote the answer now, and it starts as follows:

This blogpost on lattice theory has a useful reference section, which contains among others "Lattice Theory with Applications" by Vijay K. Garg. Chapter 2 "Representing Posets" describes some data structures for representing posets, and discusses how to compute join(x,y) using such a data structure.

Here is the relevant part from chapter 2.3.1:

We now give an $O(n + |e_\prec|)$ algorithm to compute the join of two elements $x$ and $y$. The algorithm returns $null$ if the join does not exist. We first assume that we are using the cover relation. To compute $join(x,y)$, we proceed as follows:

  • Step 0: Color all nodes white.
  • Step 1: Color all nodes reachable from $x$ as grey. This can be done by a BFS or a DFS starting from node $x$.
  • Step 2: Do a BFS/DFS from node $y$. Color all grey nodes reached as black.
  • Step 3: We now determine for each black node $z$, the number of black nodes that point to $z$. Call this number $inBlack[z]$ for any node $z$. This step can be performed in $O(n + |e_\prec|)$ by going through the adjacency lists of all black nodes and maintaining cumulative counts for $inBlack$ array.
  • Step 4: We count the number of black nodes $z$ with $inBlack[z]$ equal to $0$. If there is exactly one node, we return that node as the answer. Otherwise, we return $null$.
$\endgroup$
  • $\begingroup$ This answer interprets the "lowest common ancestor" with respect to the partial order defined by the DAG. For the reading with respect to path lengths, we no longer have a semi-lattice, but the algorithm can still be adapted by only using BFS and interleaving both searches appropriately. The poset interpretation is still useful for determining whether there exists at least one "lowest common ancestor" candidate. $\endgroup$ – Thomas Klimpel Mar 19 '13 at 8:03

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.