Find cyclic dependency [duplicate]

This question already has answers here: 开发者_如何学C Closed 10 years ago.

Possible Duplicate:

Finding all cycles in graph

I have a task I've been wrapping my brain around and still have a trouble inplementing it. Here it goes: There is a class:

public class Package {
private String name;
public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

private List<Package> dependencies;

public List<Package> getDependencies() {
    return dependencies;
}

public void setDependencies(List<Package> dependencies) {
    this.dependencies = dependencies;
}

public Package(String name){
    this.name = name;
    this.dependencies = new ArrayList<Package>();
}
  //any bunch of methods here))
}

And there is another one:

public class Project {
private String name;
private List<Package> packages = new ArrayList<Package>();

public boolean hasCyclic(){
    //**//implementation should be here
}

}

I need to find whether a list of packages in a project has a cyclic dependency or not. For example A->B->C->B - found, return true or A->C->Z->A - found, return true. First thing that comes to mind is to get all packages' names, sort them and find duplicates. But somewhere, deep in my brain, something tells me it is not the most optimal solution. Can you guys help me out here? Thank you so much in advance.

---

This is basically a "Detect Cycles in a Directed Graph" problem.

I can't beat this answer already posted in SO that explains how to solve this problem.

---

There is a cycle <==> The DFS forest (from any starting point) has a back branch.

Linear running time. Simple implementation.

---

Think of the project's dependencies as a tree, and then simply do a depth-first traversal of the tree, keeping track of the package name when you visit each node. If you encounter a duplicate name before the traversal reaches the furthest level it can, then you have a cyclic dependency.

---

There are a number of variants with varying memory/execution time characteristics. Some ideas are

• Put all dependencies in a HashMap, detecting cycles means to find find a non-null value in when performing the write check
• Use two "pointers" to traverse the list with one pointer faster than the other.
  • Either the pointers will terminate or one will eventually catch up in a cyclic loop such that the element at pointer A is the same as the element in pointer B.
• Provide checks at insertion time. When inserting a new element, traverse the list to see if element to insert is already present or not.

---

That's the code I've come up with. Seems to work)

package com.mycompany.app;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class Package {
private String name;
private List<Package> dependencies;
private List<String> allNames = new ArrayList<String>();
public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

public List<Package> getDependencies() {
    return dependencies;
}

public void setDependencies(List<Package> dependencies) {
    this.dependencies = dependencies;
}

public Package(String name){
    this.name = name;
    this.dependencies = new ArrayList<Package>();
}

public boolean hasPackages(){
    return !dependencies.isEmpty();
}

public List<String> getAllNames(){
    allNames = new ArrayList<String>();
    allNames.add(name);
    for (Package pkg : dependencies){
        if (pkg.hasPackages()){
            allNames.addAll(pkg.getAllNames());
        }
        else{
            allNames.add(pkg.getName());
        }
    }

    return allNames;
}

public Package addPackage(Package pkg){
    dependencies.add(pkg);
    return this;

}

public boolean hasCyclic(){
    List<String> names = getAllNames();
    Set<String> visited = new HashSet<String>();
    for (String name : names){
        if (visited.contains(name)){
            return true;
        }
        else{
            visited.add(name);
        }
    }
    return false;
}
}