Yano Yano - 19 days ago 15
Java Question

JAVA - BFS to a limited friendship level in a graph

I am working on an undirected graph implementation for a simple social network. Users are represented using their IDs (Integers), and I need to find different levels of friendship.

I used the Adjacency List approach as my graph is very sparse. I used a hashmap to hold users and their friends:

Map<Integer, Set<Integer>> graph;


Using this implementation, I am able to find the first and second levels of friendship. However, I wrote a method that uses BFS to find if two users are fourth-level friends.

For example, if the graph contains following edges:

1-2

2-3

3-4

4-5

Then 1 and 5 are fourth-level friends, and my method should return true when 1 and 5 are passed to it as parameters.

The problem is that my method always returns false!

public boolean checkLevelBFS(Integer source, Integer dest) {
Queue<Integer> toVisitQueue = new LinkedList<>(graph.get(source));
Set<Integer> visited = new HashSet<>();
visited.add(source);
Integer inreaser = new Integer(-1); // indicator for level increase
toVisitQueue.add(inreaser);
int level = 1; // because we already passed the source and started from its children nodes
while (level <= 4 && !toVisitQueue.isEmpty()) {
Integer currentNode = toVisitQueue.remove();
if (currentNode.equals(dest)) {
return true;
}
if (visited.contains(currentNode)) {
continue;
}
if (currentNode.equals(inreaser)) {
level++;
toVisitQueue.add(inreaser);
continue;
}
visited.add(currentNode);
for (Integer child : graph.get(currentNode)) {
if (!visited.contains(child)){
toVisitQueue.add(child);
}
}
}
return false;
}


The part that makes the code return false is below:

public static void main(String[] args) {
Basics x = new Basics();
x.graph = new HashMap<>();

Set<Integer> s = new HashSet<>();

s.add(2);
x.graph.put(1, s);

s = new HashSet<>();
s.add(1);
s.add(3);
x.graph.put(2, s);

s = new HashSet<>();
s.add(2);
s.add(4);
x.graph.put(3, s);

s = new HashSet<>();
s.add(3);
s.add(5);
x.graph.put(4, s);

s = new HashSet<>();
s.add(4);
s.add(6);
x.graph.put(5, s);

s = new HashSet<>();
s.add(5);
x.graph.put(6, s);

if (!x.initialCheck(1, 5)) {
System.out.println("A new user is involved");
} else {
if (x.levelOneFriends(1, 5)) {
System.out.println("friends");
} else {
System.out.println("not friends");
if (x.levelTwoFriends(1, 5)) {
System.out.println("friends level 2");
} else {
System.out.println("not friends of level 2");
if (x.checkLevelBFS(1, 5)) {
System.out.println("YES - friends of level 4");
} else {
System.out.println("NO - not friends of level 4");
}
}
}
}
System.out.println(x.checkLevelBFS(1, 2));
System.out.println(x.checkLevelBFS(1, 3));
System.out.println(x.checkLevelBFS(1, 4));
System.out.println(x.checkLevelBFS(1, 5));
System.out.println(x.checkLevelBFS(1, 6));
}


Output:

not friends
not friends of level 2
NO - not friends of level 4
false
false
false
false
false


The first two lines are correct outputs, the third is not correct as 1 and 5 are frieds of level 4, and should print YES -

The following 'false' outputs are weird too!

'initialCheck' checks if any of the two users is not already in the graph.

'levelOneFriends' checks if the two objects are direct friends.

'levelTwoFriends' checks if the two objects are in the relation Friend of Friend.

Any help?

Thanks!

Answer

"The problem is that my method always returns false!"

But it doesn't! Your bug may be in some other place!!!

I'll be marking this as Works for me and closing the bug.

My code used for driving the tests.

class ExampleTest {
  Map<Integer, Set<Integer>> graph;  

  static public void main(String[] args) {
    ExampleTest x=new ExampleTest();
    x.graph=new HashMap<>();
    x.graph.put(1, new HashSet<>(Arrays.asList(2)));
    x.graph.put(2, new HashSet<>(Arrays.asList(3)));
    x.graph.put(3, new HashSet<>(Arrays.asList(4)));
    x.graph.put(4, new HashSet<>(Arrays.asList(5)));
    x.graph.put(5, new HashSet<>(Arrays.asList(6)));
    System.out.println(x.checkLevelBFS(1, 2)); // true
    System.out.println(x.checkLevelBFS(1, 3)); // true
    System.out.println(x.checkLevelBFS(1, 4)); // true
    System.out.println(x.checkLevelBFS(1, 5)); // true
    System.out.println(x.checkLevelBFS(1, 6)); // false
  }

  // verbatim copy of your method here
  public boolean checkLevelBFS(Integer source, Integer dest) {
    Queue<Integer> toVisitQueue = new LinkedList<>(graph.get(source));
    Set<Integer> visited = new HashSet<>();
    visited.add(source);
    Integer inreaser = new Integer(-1); // indicator for level increase
    toVisitQueue.add(inreaser);
    int level = 1; // because we already passed the source and started from its children nodes
    while (level <= 4 && !toVisitQueue.isEmpty()) {
      Integer currentNode = toVisitQueue.remove();
      if (currentNode.equals(dest)) {
        return true;
      }
      if (visited.contains(currentNode)) {
        continue;
      }
      if (currentNode.equals(inreaser)) {
        level++;
        toVisitQueue.add(inreaser);
        continue;
      }
      visited.add(currentNode);
      for (Integer child : graph.get(currentNode)) {
        if (!visited.contains(child)){
          toVisitQueue.add(child);
        }
      }
    }
    return false;
  }

}
Comments