Java: Finding friendship chains via recursion

Question

I'm currently working on a problem where I have to find friendship chains via recursion in Java. Statistically, a person knows another person over about 6 waypoints - which is the chain I am trying to find.

I've got a class "Person", which defines a name and direct friends:

public class Person
{
    private Person[] friendChain;
    private String name;

    public Person(String name, Person[] friendChain)
    {
        this.friendChain    = friendChain;
        this.name           = name;
    }

    public Person[] getFriends()
    {
        return this.friendChain;
    }

    public String getName()
    {
        return this.name;
    }

    public boolean isFriendWith(Person person)
    {
        for(Person p: this.friendChain)
        {
            if(p != null && person != null && p.getName().equals(person.getName())) 
                return true;
        }

        return false;
    }

    public boolean equals (Person person)
    {
        return this.name.equals(person.getName());
    }

    public String toString()
    {
        return this.getName();
    }
}

A diagram was given that gives an example chain, where arrows indicate a one-way or two-way relationship (as in Thomas knows Theresa, but Theresa doesn't know Thomas):

So basically my outcome should look similiar to something like this:

result = getFriendshipChain(adam, theresa);

result[0].getName(); // "Michael"
result[1].getName(); // "Kerstin"
result[2].getName(); // "Thomas"
result[3].getName(); // "Theresa"
result[4].getName(); // null
result[5].getName(); // null

I've done a lot of recursive programming in the past, but I just can't get my head into this right now - I'd appreciate any help!

You shouldn't think in terms of chains, but in terms of graphs. Find a graph library, make it that each person is a vertex, each friendship an edge and ask it to get the shortest path. Since you speak about directions, you should find a directed graph/ — Olivier Grégoire, Nov 18 '16 at 13:45
Some things about `Person#equals`. First you need to [satisfy the contract](http://stackoverflow.com/questions/3181339/right-way-to-implement-equals-contract). Second, you need to [override `hashcode`](http://stackoverflow.com/questions/27581/what-issues-should-be-considered-when-overriding-equals-and-hashcode-in-java). Finally, you should use it in `isFriendsWith`. — bradimus, Nov 18 '16 at 13:51
Why do you expect `result[2]` to only return Thomas? By your diagram, Krestin is friend's with Michael and Thomas, shouldn't this be considered when traversing your path? — px06, Nov 18 '16 at 13:57
@px06 The result array should contain the shortest path between to persons. While Kerstin knows Michael AND Thomas, We're looking at the chain from Adam to Theresa basically, which defines the direction of the relation. — Tekumi, Nov 18 '16 at 15:04

score 1 · Accepted Answer · answered Nov 18 '16 at 14:37

Here is an example but beware, this will only work if your graph has only one path like in your sample image

In case this isn't broad enough to suit your needs, at least the first and second steps (maybe the third also) should be helpful :

1) You only accept friendsChain in the constructor of Person, but how can you pass a chain of Person objects that haven't yet been created ? This is a cyclic creation dependency; I suggest to remove the problem with a lighter constructor, along with a setter for friendChain .

public Person(final String name) {

    this.name = name;
}

public void setFriendChain(final Person[] friendChain) {
    this.friendChain = friendChain;
}

2) Let's build Person objects and populate their friend chains

Person adam = new Person("Adam");
Person michael = new Person("Michael");
Person kerstin = new Person("Kerstin");
Person thomas = new Person("Thomas");
Person theresa = new Person("Theresa");

Person[] adamsFriends = { michael, kerstin };
adam.setFriendChain(adamsFriends);

Person[] michaelsFriends = { adam, kerstin };
michael.setFriendChain(michaelsFriends);

Person[] kerstinsFriends = { thomas, adam, michael };
kerstin.setFriendChain(kerstinsFriends);

Person[] thomasFriends = { kerstin, theresa };
thomas.setFriendChain(thomasFriends);

Person[] theresasFriends = { thomas };
theresa.setFriendChain(theresasFriends);

3) Let's build a recursive method to follow the friend chain (note that we use a List, because we don't know the final size of the chain) :

public void getFriendshipChain(final Person from, final Person to, final List<Person> friendshipChain) {

    friendshipChain.add(from);

    // We have found the target person, return
    if (from.equals(to)) {
        return;
    }

    // For every friend from that person
    for (Person friend : from.getFriendChain()) {

        // If we don't already have it in the list
        if (!friendshipChain.contains(friend)) {

            // follow this friend's chain
            getFriendshipChain(friend, to, friendshipChain);

        }
    }

}

4) Call it :

List<Person> result = new ArrayList<Person>();

getFriendshipChain(adam, theresa, result);

System.out.println(result);

I only accept friendsChain in the constructor due to the class "Person" being given to me - I wouldn't have done it like that, and you're absolutely right. You gave an awesome explanation and I absolutely understood everything of it and will use your code to get a solution, which I will then post here. Thank you a ton for your effort! — Tekumi, Nov 18 '16 at 15:07

Java: Finding friendship chains via recursion

1 Answers1