# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Find the lowest common ancestors for pairs of vertices in a graph

Contributed by:
Nikolay Murzin

ResourceFunction["LowestCommonAncestors"][ returns a list of the lowest common ancestors of vertices | |

ResourceFunction["LowestCommonAncestors"][ returns an Association of lowest common ancestors for each distinct pair of vertices in a graph | |

ResourceFunction["LowestCommonAncestors"][ returns the common ancestors for each vertex pair { | |

ResourceFunction["LowestCommonAncestors"][ returns lowest common ancestors for a vertex |

Lowest common ancestor is also known as "least", "most recent" or "last" common ancestor.

The lowest common ancestor for a pair of vertices in a graph is their shared ancestor located farthest from the graph root. The graph root is defined as a graph sink of a subgraph induced by the set of common ancestors shared by this pair.

ResourceFunction["LowestCommonAncestors"] works for arbitrary graphs.

LowestCommonAncestors returns a list of vertices for a pair, as there could be zero or more than one lowest common ancestor.

ResourceFunction["LowestCommonAncestors"][*g*,{*v*,*w*}] is equivalent to ResourceFunction["LowestCommonAncestors"][*g*,*v*,*w*].

Find a list of lowest common ancestors for a pair of vertices in a graph:

In[1]:= |

Out[1]= |

Find all lowest common ancestors for a list of pairs of vertices:

In[2]:= |

Out[2]= |

Find all lowest common ancestors for all pairs that contain a given vertex:

In[3]:= |

Out[3]= |

Find all lowest common ancestors for every pair of vertices:

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]= |

Measure an average time and spatial distance between pairs of events in a causal graph using longest distance to their lowest common ancestor:

In[6]:= |

Out[6]= |

- 1.0.0 – 01 November 2022

This work is licensed under a Creative Commons Attribution 4.0 International License