CODEWITHSUNDEEP
javagraphgraph-theory
user1277546
user1277546

Reputation: 8772

Graph Theory - Finding subgraphs

I'm writing a program that takes some input of names and looks at a tree of the following structure: 

                                                        John
                                                    /           \
                                                  Chris         Bob
                                                /   |   \        |  \
                                               Tom Ben  Anna    Jade  Ed
                                               /  \      |           /  \
                                            Will  Mark  Ant        Andy  Dan

The program should return the subtree where the root node is the lowest relationship/link between the inputted names.

If I input Mark and Ant, the program should return the following tree: 

                                                  Chris 
                                                /       \   
                                               Tom     Anna     
                                                  \      |         
                                                  Mark  Ant

If I input Will, Mark and Andy then the program should return the following tree: 

                                                        John
                                                    /           \
                                                  Chris         Bob
                                                /                   \
                                               Tom                   Ed
                                               /  \                  /  
                                            Will  Mark             Andy

I am using the following class for my tree nodes and connectivity: 

import java.util.ArrayList;
import java.util.List;

public class Person {
    private String name; 
    private List<Person> children;

    public Person(String name) { 
        this.name = name; 
        children = new ArrayList<Person>();
    }

    public String getName() {
        return name;
    }
    public List<Person> getChildren() {
        return children;
    }
    public void setName(String name) {
        this.name = name;
    }
    public void setChildren(List<Person> children) {
        this.children = children;
    }
    public void addChild(Person c) { 
        children.add(c);
    }
}

My question is how do I solve the problem of determining the common node (in the first instance it's Chris, and the second it's John) and also how to then use that name to get the subtree (common node and nodes below).

I'm also considering expanding on this to use a Neo4j database, but would like to work it out in this case first.

Thanks!

Upvotes: 1

Views: 855

Answers (1)

pedrosorio
pedrosorio

Reputation: 870

What you are looking for is the lowest common ancestor:

http://en.wikipedia.org/wiki/Lowest_common_ancestor

I could try to explain it in detail but I could never do it better and more comprehensively than this tutorial, which teaches you a number of different algorithms for solving that problem:

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

Upvotes: 1

Related Questions