title: JAVA - BFS to a limited friendship level in a graph
body: <p>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.<br>
  I used the Adjacency List approach as my graph is very sparse. I used a hashmap to hold users and their friends:  </p>
  
  <pre><code>Map&lt;Integer, Set&lt;Integer&gt;&gt; graph;  
  </code></pre>
  
  <p>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.  </p>
  
  <p>For example, if the graph contains following edges:<br>
  1-2<br>
  2-3<br>
  3-4<br>
  4-5<br>
  Then 1 and 5 are fourth-level friends, and my method should return true when 1 and 5 are passed to it as parameters.  </p>
  
  <p><strong>The problem</strong> is that my method always returns false when it is called in the main, even if the method itself is tested and is correct! Here is the method, and again it is correct and working.  </p>
  
  <pre><code>public boolean checkLevelBFS(Integer source, Integer dest) {
      Queue&lt;Integer&gt; toVisitQueue = new LinkedList&lt;&gt;(graph.get(source));
      Set&lt;Integer&gt; visited = new HashSet&lt;&gt;();
      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 &lt;= 4 &amp;&amp; !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;
  }
  </code></pre>
  
  <p>The part that makes the code return false is below:  </p>
  
  <pre><code>public static void main(String[] args) {
      Basics x = new Basics();
      x.graph = new HashMap&lt;&gt;();
  
      Set&lt;Integer&gt; s = new HashSet&lt;&gt;();
  
      s.add(2);
      x.graph.put(1, s);
  
      s = new HashSet&lt;&gt;();
      s.add(1);
      s.add(3);
      x.graph.put(2, s);
  
      s = new HashSet&lt;&gt;();
      s.add(2);
      s.add(4);
      x.graph.put(3, s);
  
      s = new HashSet&lt;&gt;();
      s.add(3);
      s.add(5);
      x.graph.put(4, s);
  
      s = new HashSet&lt;&gt;();
      s.add(4);
      s.add(6);
      x.graph.put(5, s);
  
      s = new HashSet&lt;&gt;();
      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));
  }
  </code></pre>
  
  <p>Output:  </p>
  
  <pre><code>not friends
  not friends of level 2
  NO - not friends of level 4
  false
  false
  false
  false
  false
  </code></pre>
  
  <p>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 -<br>
  The following 'false' outputs are weird too!  </p>
  
  <p>'initialCheck' checks if any of the two users is not already in the graph.<br>
  'levelOneFriends' checks if the two objects are direct friends.<br>
  'levelTwoFriends' checks if the two objects are in the relation Friend of Friend.  </p>
  
  <p>Any help?</p>
  
  <p>Thanks!</p>