GSoC-2k16 Coding period - Week 1

Submitted by rakesh on Wed, 06/08/2016 - 22:47

After the successful completion of Community bonding period of Google Summer of Code 2016, Coding Period has been started. Although I already knew that it would be awesome but reality is much more amazing than I ever imagined.

Project : Solving content conflicts with merge algorithms in Drupal8.

As per the timeline break down, I had to work on creating a php library to find a common ancestor of two nodes. A common ancestor is a parent which both the nodes shares in the graph. Lowest Common ancestor is the closest common parent of both the nodes.

Task accomplished this week: The task I had to accomplish this week was "To find Lowest common ancestor from a Directed Acyclic Graph". I had to design a PHP Library using thegraph/algorithms repository which anyone could use in their code to find the lowest common parent of two nodes in a graph.

Approach: We used the Breadth First Search Algorithm to find the nodes in between root and the nodes for which the LCA is to be found. We intersected the results in the array and the first result in the resulting array is the LCA. This is working pretty fine for those nodes which has a single parent and for the nodes with multiple parents, It is returning the parent node which comes first as per BFS algorithm. My mentor Andrei Jechiu was a real great help in implementation of this Library. Not only he came up with this approach but also implemented it in such a clean way that I'd probably never have implemented.

Mentors: I was in touch with my mentors Dick OlssonAndrei Jechiu and Tim Millwood through Slack and IRC(#drupal8-ports, #drupal-google). My mentors are always there with a solution to my questions and it seems like somehow they already know about the problems which I will be facing in future as well. I guess my mentors are the perfect examples of "Guru".

Code: The code for the PHP Library can be found over github. One must install it through composer in order to install all dependencies as well

Tasks for this week: Now we have to write tests for this library and different use cases for different tree structures. Along with that we'd have to take care of multiple parents as well.