Lowest common ancestor similar algorithm for a graph

Question

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.

Answer 1

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$.