code simplification for cycle detection in directed graph in Java [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

I have this following code which works fine to detect cycles in directed Graph. something I do not like here is return true appearing in conditional statement if (!t.isVisited && isCyclicDirected(t)). I am returning true whether or not the if statement passes true. I am looking to simplify this code for better readability. Thanks

public boolean isCyclicDirected(Vertex v){
  if (v.isVisited){
    return true;
  }
  v.setVisited(true);
  Iterator<Edge> e = v.adj.iterator();
  while (e.hasNext()){
    Vertex t = e.next().target;
    if (!t.isVisited && isCyclicDirected(t))
      return true;
    else return true;
  }
  return false;
}

The above code is derived from refactoring this code below

public boolean isCyclicDirected(Vertex v){
    if (v.isVisited){
        return true;
    }
    v.setVisited(true);
    Iterator<Edge> e = v.adj.iterator();
    while (e.hasNext()){
        Vertex t = e.next().target;
            if (!t.isVisited) {
                    if (isCyclicDirected(t))
                         return true;
            }

             else return true;
        }
        return false;
}

Answer 1

Your while loop is not a loop: in the code you have written, you get one adjacent vertex and then you immediately return based on whether it's cyclic or not, never touching the other vertices:

public boolean isCyclicDirected(Vertex v){
  if (v.isVisited){
    return true;
  }

  v.setVisited(true);
  Iterator<Edge> e = v.adj.iterator();
  while (e.hasNext()) {
    Vertex t = e.next().target;

    // This while loop never goes beyond the first element.
    // you get the first vertex, then return from the
    // entire function.

    if (!t.isVisited && isCyclicDirected(t))
      return true;
    else return true;

  }
  return false;
}

What you want instead is this to evaluate every vertex, return "true" if any of them are identifiably cyclic, otherwise exhaust your vertices and return "false":

public boolean isCyclicDirected(Vertex v){
  if (v.isVisited){
    return true;
  }
  v.setVisited(true);
  Iterator<Edge> e = v.adj.iterator();
  while (e.hasNext()) {
    Vertex t = e.next().target;
    // quick test:
    if (t.isVisited) {
      return true;
    }
    // elaborate, recursive test:
    if(isCyclicDirected(t)) {
      return true;
    }
  }
  // none of our adjacent vertices flag as cyclic
  return false;
}