PHPackages                             relaxedws/lca - PHPackages - PHPackages  [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register)

1. [Directory](/)
2. /
3. [Utility & Helpers](/categories/utility)
4. /
5. relaxedws/lca

AbandonedArchivedLibrary[Utility & Helpers](/categories/utility)

relaxedws/lca
=============

Library used to find lowest common ancestor in graphs.

1.0.0(9y ago)5758.2k2GPL-3.0+PHP

Since Apr 30Pushed 9y agoCompare

[ Source](https://github.com/relaxedws/lca)[ Packagist](https://packagist.org/packages/relaxedws/lca)[ RSS](/packages/relaxedws-lca/feed)WikiDiscussions master Synced 3w ago

READMEChangelogDependencies (2)Versions (2)Used By (0)

Relaxedws/lca [![Build Status](https://camo.githubusercontent.com/9ab776a4511a0bf2c92030dedf33807dcc4e5ff123c73d871a0290e11cd0382f/68747470733a2f2f7472617669732d63692e6f72672f72656c6178656477732f6c63612e7376673f6272616e63683d6d6173746572)](https://travis-ci.org/relaxedws/lca)
====================================================================================================================================================================================================================================================================================

[](#relaxedwslca-)

A PHP Library to find Lowest Common ancestor from a Directed Acyclic Graph.

Insight
-------

[](#insight)

This library is built to find the Lowest Common ancestor from a Directed Acyclic graph. It first creates a graph and then stores the parents of a node(let's call it node1) in an array(call it array1). To find the parents of node1, we use [Breadth First Search](https://en.wikipedia.org/wiki/Breadth-first_search) traversal in reverse order, i.e, From node1 to root. Same is done with node2. Then we find the LCA by the intersection of elements from array1 and array2. The first node returned by the intersection is the LCA of the 2 nodes.

Dependencies
------------

[](#dependencies)

This library uses [clue/graph](https://github.com/clue/graph) for creation of the graph and [graphp/algorithms](https://github.com/graphp/algorithms)for Breadth First Traversal.

Install
-------

[](#install)

The library can be installed via [composer](http://getcomposer.org).

```
{
  "name": "myorg/mylib",
  "description": "A library depending on relaxed/lca",
  "require": {
    "relaxedws/lca": "dev-master"
  }
}
```

Example
-------

[](#example)

After [installation](#install), we can perform a merge the following way:

```