Geek Answers Handbook

How to find loops in an object hierarchy?

There is a Company class that references another instance of Company to represent parent . Suppose there are four companies: c1 , c2 , c3 and c4 and c2 , c3 , c4 has a parent company like c1 .

For instance:

 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 installed c2 as the parent company c1 :

 c1.parent = c2;

then it will create an endless cycle of Cyclomatic Complexity in the hierarchy of the company, which we should avoid in our system.

We would like to discover this at runtime . What is the best algorithm for checking the cyclic complexity of objects of the same class in the above situation?

+4
source share
3 answers

Your task has nothing to do with cyclic complexity. Your objects basically form a graph, and you want to detect a cycle in it. A common way to do this is to run DFS .

You can find many examples of how to do this over the Internet .

+6
source

I solved this problem programmatically by creating a local Set processed objects and letting it propagate as an input parameter for every call to the recursive method.

For instance:

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

From corsa, you need to make sure that your class company is indexed: it correctly overrides hashCode and equals .

Please note that this algorithm can be implemented even outside the abstraction of the Company (as in this example), since it distributes the Company object in each call as part of the move state (together with the set). This is not necessary, as these methods may be part of the abstractions of the Company themselves, but it is imperative that the set be distributed as an input parameter.

+1
source

You can set parent to private and change the parent value using the setParent(Company) method. 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; }

As a rule, bad practice has public variables, since it interrupts 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: The hasCycle return has been hasCycle to return a List<Company> containing all the companies in the loop for further processing (print them, delete, etc.).

0
source

More articles:


All Articles