如何在我的对象层次结构中找到循环？

Question

有一个class Company，它引用了另一个Company的实例来表示parent。假设有四家公司 c1、c2、c3 和 c4 并且 c2、c3、c4 有母公司设置为 c1.

例如：

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);
}

如果我们将 c2 设置为 c1 的母公司：

c1.parent = c2;

然后它将在公司层次结构中创建一个 Cyclomatic Complexity 无限循环，我们必须在我们的系统中避免这种情况。

我们希望能够在运行时检测到这个。在上述情况下检查相同 class 对象的圈复杂度的最佳算法是什么？

Answer 1

您可以将 parent 设置为 private 并使用方法 setParent(Company) 更改 parent 的值。那么：

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;
}

无论如何，拥有 public 变量通常是不好的做法，因为它会破坏封装。

如果您无法将字段更改为 private，则：

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;
}

编辑：将 hasCycle 的 return 更改为 return a List<Company> 包含一个循环中的所有公司以进行进一步处理（打印出来、删除它们等） .

Answer 2

您的任务与圈复杂度无关。您的实体基本上形成了一个图形，您想要检测其中的循环。常见的方法是执行 DFS.

您可以找到大量示例来了解如何做到这一点 over the internet。

Answer 3

我已经以编程方式解决了这个问题，创建了一个本地 Set 已处理对象，并让它在每次调用递归方法时作为输入参数传播。

例如：

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);
        }
    }

当然，您必须首先确保您的 class 公司是可索引的：它正确地覆盖了 hashCode 和 equals。

请注意，该算法甚至可以在 Company 抽象之外实现（如本例所示），因为它在每次调用中将 Company 对象传播为遍历状态的一部分（与集合一起）。这不是强制性的，因为这些方法本身可能是 Company 抽象的一部分，但是必须将集合作为输入参数传播。

如何在我的对象层次结构中找到循环？

How do I find cycles in my object hierarchy?

java

algorithm

cyclomatic-complexity

object-graph