How do I find cycles in my object hierarchy?

问题:

There is a class Company, which has reference to another instance of Company to represent the parent. Lets say there are four companies c1, c2, c3 & c4 and c2, c3, c4 has parent company set as c1.

For example:

public class Company {
  public Company parent;

  public Company() { }
  public Company(Company parent) {
    this.parent = parent;
  }

  public static void main(String[] args) {
    Company c1 = new Company();
    Company c2 = new Company(c1);
    Company c3 = new Company(c1);
    Company c4 = new Company(c1);
}

If we set c2 as parent company of the c1:

c1.parent = c2;

then it will create a Cyclomatic Complexity infinite loop in the company hierarchy, which we have to avoid in our system.

We would like to be able to detect this in runtime. What is the best algorithm to check the cyclomatic complexity in objects of the same class in the above situation?

回答1:

Your task has nothing to do with cyclomatic complexity. Your entities basically form a graph and you want to detect cycle in it. The common way to do that is to perform a DFS.

You can find plenty of examples how to do that over the internet.

回答2:

I've resolved this problem programatically, creating a local Set of processed objects and letting it propagate as an input parameter on each call to the recursive method.

For example:

public void myMethod(Company c)
{
    Set<Company> visitedCompanies=new HashSet<Company>();
    visitedCompanies.add(c);
    myPrivateMethod(c, visitedCompanies);
}

private void myPrivateMethod(Company c, Set<Company> visitedCompanies)
{
    if (visitedCompanies.contains(c))
    {
        // Cylce detected
    }
    else
    {
        //... do some stuff

        // Go upwards in the hierarchy
        if (c.getParent()!=null)
        {
            visitedCompanies.add(c);
            myPrivateMethod(c.getParent(), visitedCompanies);
        }
    }

Of corse, you have to ensure first that your class Company is indexable: It properly overrides hashCode and equals.

Note that this algorithm can be implemented even outside of the Company abstraction (as in this example), as it propagates the Company object in each invokation as part of the traversing state (along with the set). This is not mandatory, since these methods could be part of the Company abstraction themselves, but it is mandatory that the set be propagated as an input parameter.

回答3:

You could set parent to private and change the value of parent using a method setParent(Company). Then:

public boolean setParent(Company parent) {
    Company curr = parent;
    while (curr != null) {
        if (curr.equals(this)) {
            return false; // Failed as cycle
        } else {
            curr = curr.getParent();
        }
    }
    this.parent = parent;
    return true;
}

It is in general bad practice to have public variables anyways as it breaks encapsulation.

If you cannot change the field to private, then:

public List<Company> hasCycle(List<Company> companies) {
    while (companies.size() > 0) {
        List<Company> cycle = new ArrayList<Company>();
        Company curr = companies.get(companies.length() - 1);
        cycle.add(curr);
        while (curr.parent != null) {
            curr = curr.parent;
            if (cycle.contains(curr)) {
                return cycle; // Cycle detected
            }
            cycle.add(curr);
        }
        companies.removeAll(cycle); // Remove all elements we traversed through just now
    }
    return null;
}

Edit: Changed return of hasCycle to return a List<Company> containing all the companies in a cycle for further processing (print them out, remove them etc).