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?
You could set
parent
toprivate
and change the value ofparent
using a methodsetParent(Company)
. Then:It is in general bad practice to have
public
variables anyways as it breaks encapsulation.If you cannot change the field to
private
, then:Edit: Changed return of
hasCycle
to return aList<Company>
containing all the companies in a cycle for further processing (print them out, remove them etc).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.
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:
Of corse, you have to ensure first that your class Company is indexable: It properly overrides
hashCode
andequals
.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.