recursive call in looping a list

Question

I m trying to loop a list of users to find a person. Every person has a friends list. So i m using recursive call to check if the person is in someones friends list.

My Junit test is look like

@Test
    public void IsInFriendsCicle() throws UserAlreadyInFriendListException, NoFriendFoundException, UsersNotConnectedException {
        User one = new UserImpl("John","Snow");
        User two = new UserImpl("Richard","Gerns");
        User three = new UserImpl("Natalie","Portman");
        User four = new UserImpl("Brad","Pitt");
        User five = new UserImpl("Angelina","Jolie");
        one.addFriend(two);
        two.addFriend(three);
        three.addFriend(four);
        four.addFriend(five);
        assertTrue(one.isInFriendsCycle(five, one.getFriends(), new Stack()));

    } 

So as it can be seen here, i want to know if Angelina is in the friends list of john. So it supposed to give back true. The responsible method is for that :

public boolean isInFriendsCycle(User userToFind, ArrayList<User> list, Stack stack){
    Stack s = stack;
    ArrayList<User> groupList = list;
    if(groupList.contains(userToFind)){
        return true;
    }else{
        for (User user : groupList) {
            if(!s.contains(user)){
                s.push(user);
                if(user.getFriends().contains(userToFind)){
                    return true;
                }else{
                    return isInFriendsCycle(userToFind, user.getFriends(), s);
                }
                }
        }       
    }
    return false;
}

So the class is :

public class UserImpl implements User{

    private String name;
    private String surname;
    private static int count = 0;
    private int id;
    private ArrayList<User> friends;
    private ArrayList<Message> messagebox;
    final static Logger logger = Logger.getLogger(UserImpl.class);

    public UserImpl(String name, String surname) {

        this.name = name;
        this.surname = surname;
        this.id = ++count;
        this.friends = new ArrayList<User>();
        this.messagebox = new ArrayList<Message>();
    }
@Override
    public User addFriend(User person) throws UserAlreadyInFriendListException,IllegalArgumentException{
        if(this.getFriends().contains(person)){
            throw new UserAlreadyInFriendListException("user is already in the friendlist");
        }else if(person == null || this.equals(person) ){
            throw new IllegalArgumentException("parameter is null or user trying to add himself as friend");    
        }else{
            this.getFriends().add(person);
            person.getFriends().add(this);
            logger.debug(this.name + " added the user "+person.getName());
            return person;
        }

    }
@Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final UserImpl other = (UserImpl) obj;

        if (this.id != other.id) {
            return false;
        }
        return true;
    }
}

There is a problem with stack somehow. I m using it to mark the persons so i dont get in the infinitive loop. There is a reason for passing user.getFriends() so it should stay in that way. Any help will be appreciated !

Answer 1

I'd implement it as follows:

private Set<User> friends = new HashSet<User>();

public void addFriend(User friend) {
    friends.add(friend);
}

public boolean isImmediateFriend(User user) {
    return friends.contains(user);
}

public boolean isInFriendNetwork(User user) {
    Set<User> visited = new HashSet<>();
    List<User> stack = new LinkedList<>();

    stack.push(this);

    while (!stack.isEmpty()) {
       User current = stack.removeFirst();
       if (current.isImmediateFriend(user)) {
          return true;
       }
       visited.add(current);

       for (User friend : current.getFriends()) {
          // never visit the same user twice
          if (!visited.contains(friend)) {
             stack.addLast(friend);
          }
       }
    }
    return false;
}

Answer 2

replace

return isInFriendsCycle(userToFind, user.getFriends(), s);

with

if (isInFriendsCycle(userToFind, user.getFriends(), s)) return true;

As you have it, you prematurely exit if you didn't find it in the first branch of the recursive call. You don't want that - you want to continue until you find it, or there is nothing left to search through.

As an aside - your unit test wasn't helping you as you made the nesting too deep. If you had a few unit tests, first testing a friend-friend, then a friend-friend-friend, etc., you would have started to see where it was going wrong.

Also, as another aside: I would not use Stack (it is a legacy class) use Deque instead, which is the Java 6+ replacement. However in this case I would use a Set<User> in the form HashSet<User> as it fits your use case and probably performance requirements. I would also make the list variable types a List<User> not an ArrayList<User> inside your UserImpl class and isInFriendsCycle method, just to concentrate on the contracts and not the implementation.

Answer 3

Pseudocode for the recursive algorithm with marking:

IsFriendOf(A, B):
    if A == B:
        return True

    B.Marked= True
    for all C in B.Friends:
        if not C.Marked and IsFriendOf(A, C):
            B.Marked= False
            return True

    B.Marked= False
    return False