No description, website, or topics provided.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
docs Rename the picture directory to docs Apr 30, 2017
src Fixing file permissions Apr 30, 2017
tests Fixing file permissions Apr 30, 2017
.travis.yml Add PSR-2 code standard check. Jun 13, 2016
LICENSE.md Fixing file permissions Apr 30, 2017
README.md Fixing file permissions Apr 30, 2017
build.xml Add PSR-2 code standard check. Jun 13, 2016
composer.json
phpunit.xml.dist Fixing file permissions Apr 30, 2017

README.md

Relaxedws/lca Build Status

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

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

This library uses clue/graph for creation of the graph and graphp/algorithms for Breadth First Traversal.

Install

The library can be installed via composer.

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

Example

After installation, we can perform a merge the following way:

<?php

require __DIR__ ."/vendor/autoload.php";

use Fhaculty\Graph\Graph;
use Relaxed\LCA\LowestCommonAncestor;

$graph = new Graph();

for ($i=1; $i<=6 ; $i++){
   $vertices['node_'.$i] = $graph->createVertex('node_'.$i);
}

$vertices['node_1']->createEdgeTo($vertices['node_2']);
$vertices['node_1']->createEdgeTo($vertices['node_5']);
$vertices['node_2']->createEdgeTo($vertices['node_3']);
$vertices['node_2']->createEdgeTo($vertices['node_4']);
$vertices['node_5']->createEdgeTo($vertices['node_6']);


$instance = new LowestCommonAncestor($graph);

$lca = $instance->find($vertices['node_3'], $vertices['node_4']);
$base = $lca->getId();

Contributing

We welcome anyone to use, test, or contribute back to this project. We have extensive test coverage, but as we all know there's always bugs in software. Please file issues or pull requests with your comments or suggestions.