7
\$\begingroup\$

I wrote a very simple implementation of cycle detection in an undirected graph; I'm not interested in applying it to any real-life case: it's just for explaining the basic idea behind cycle detection in a CS lesson.

I went for recursive DFS, and unlike other implementations I found on the internet, I used just one set for the visited nodes (instead of having a set for the visited nodes and another one for the ancestors):

boolean hasCycleDfs(Node current, Set<Node> visited) {

   if (visited.contains(current)) {
      return true;
   }

   visited.add(current);
   for (Node neighbour: current.neighbors) {
      if (hasCycleDfs(neighbour, visited)) {
         return true;
      }
   }
   visited.remove(current);
   
   return false;
}

I wrote a couple of tests and they're green:

   @Test
   public void test() {

      List<Node> nodes = IntStream
                .range(1, 8)
                .mapToObj(Node::new)
                .collect(Collectors.toList());

      Node n1 = nodes.get(0);
      Node n2 = nodes.get(1);
      Node n3 = nodes.get(2);
      Node n4 = nodes.get(3);
      Node n5 = nodes.get(4);
      Node n6 = nodes.get(5);
      Node n7 = nodes.get(6);

      n1.add(n2).add(n3);
      n2.add(n4);
      n3.add(n4).add(n6);
      n4.add(n6).add(n7);
      n5.add(n1);
      n6.add(n5);
      assertTrue(hasCycleDfs(n1, new HashSet<>()));

      cleanNodes(nodes);
      n1.add(n2);
      n2.add(n3);
      n3.add(n4);
      n4.add(n1);
      assertTrue(hasCycleDfs(n1, new HashSet<>()));

      cleanNodes(nodes);
      n1.add(n2).add(n5).add(n3);
      n2.add(n3).add(n5);
      n3.add(n4).add(n5);
      n4.add(n5);
      assertFalse(hasCycleDfs(n1, new HashSet<>()));

      cleanNodes(nodes);
      n1.add(n2).add(n3);
      n2.add(n3);
      assertFalse(hasCycleDfs(n1, new HashSet<>()));
   }

   void cleanNodes(List<Node> nodes) {
      nodes.forEach(Node::clearNeighbours);
   }

This is the Node class:

class Node {
   int val;
   Set<Node> neighbors = new HashSet<>();

   Node(int val) {
      this.val = val;
   }

   public Node add(Node child) {
      neighbors.add(child);
      return this;
   }

   public void clearNeighbours() {
      neighbors.clear();
   }

   @Override
   public String toString() {
      return "[" + val + "]";
   }

   @Override
   public boolean equals(Object o) {
      Node node = (Node) o;
      return val == node.val;
   }

   @Override
   public int hashCode() {
      return val * 31;
   }
}

Do you see any edge case I didn't take into account that will give a wrong answer?

\$\endgroup\$
0
2
\$\begingroup\$

The code looks clean and organized, but there is an issue with the implementation.

Undirected graph

Consider an undirected graph A - B:

  • B is neighbor of A
  • A is neighbor of B

Using the current implementation I would create the graph like this:

Node a = new Node(1);
Node b = new Node(2);

a.add(b);
b.add(a);

Such graph is not cyclic, but the method hasCycleDfs returns true.

unlike other implementations I found on the internet, I used just one set for the visited nodes (instead of having a set for the visited nodes and another one for the ancestors)

The reason for the set of ancestors is to handle this case.

Testing

  • Is good practice to have one method for test case, instead of a single method with all the tests. It will help you pinpoint the failing test quicker without having to look at the code.
  • Once you have multiple @Test methods, you can clean the state in a method annotated with @Before (@BeforeEach in Junit5) or simply recreate the graph from scratch every time.

Minor improvements

  • The methods of Node are public unlike the class and instance variables. Use the access modifiers consistently.
  • In a non‐academic context, the method hasCycleDfs should be private as it needs to be called with and empty set:
    boolean hasCycleDfs(Node current) {
        return hasCycleDfs(Node current, new HashSet<>());
    }
    private boolean hasCycleDfs(Node current, Set<Node> visited) {
        //...
    }
    

Rewrite

Actually, there is no need for a set of ancestors, a pointer to the parent is enough:

boolean hasCycleDfs(Node current, Set<Node> visited, Node parent) {
    visited.add(current);
    for (Node neighbour : current.neighbors) {
        if (!visited.contains(neighbour)) {
            if (hasCycleDfs(neighbour, visited, current)) {
                return true;
            }
        } else if (!neighbour.equals(parent)) {
            // If the node is visited and not parent of 
            // the current node, then there is a cycle
            return true;
        }
    }
    return false;
}

And you can use it like:

hasCycleDfs(n1, new HashSet<>(), null);
\$\endgroup\$
5
  • \$\begingroup\$ Thanks Marc, super useful review! \$\endgroup\$ – Andrea Iacono Nov 11 '20 at 8:39
  • \$\begingroup\$ @AndreaIacono glad I could help. Any reason for the downvote? \$\endgroup\$ – Marc Nov 11 '20 at 8:56
  • \$\begingroup\$ actually I pressed it by mistake while accepting your anwser, and now it doesn't allow me to edit anymore (unless you edit the answer). Can you edit it? \$\endgroup\$ – Andrea Iacono Nov 11 '20 at 9:21
  • \$\begingroup\$ I also realized that my tests are incosistent with the title of the question: they build a directed graph instead of an undirected graph \$\endgroup\$ – Andrea Iacono Nov 11 '20 at 9:23
  • \$\begingroup\$ @AndreaIacono edited the answer. Yeah, the tests seems to build a directed graph. An additional suggestion is to create a class Graph with a method addEdge(a,b) to simplify the graph creation. \$\endgroup\$ – Marc Nov 11 '20 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.