How to calculate number of indirect dependencies of a class?

Question

Most of the static code analysis tools which analyse class dependencies generate dependency pairs of classes where each pair represents a direct dependency between two classes. Given those dependency pairs, it is straight forward to calculate number of direct dependencies of a particular class. However, if we have to compute number of indirect dependencies of a class, I realized that the algorithm is fairly complex. Let me clarify what I mean by indirect dependency:

We have following direct dependency class pairs:

Class A depends on Class B

Class B depends on Class C

Class B depends on Class D

In this case, class A depends directly on class B and indirectly on classes C and D.

I would define number of direct dependencies for class A as 1 and number of indirect dependencies for class A as 2.

I would like to compute indirect dependencies for each and every class in the systems that I analyse.

The complexity arises mainly due to cyclic dependencies.

For example, if we were to compute number of indirect dependencies for class A:

Scenario 1:

A -> B

B -> C

C -> D

D -> B

Scenario 2:

A -> B

B -> C

B -> D

C -> E

D -> F

E -> G

F -> G

G -> H

Scenario 3:

A -> B

B -> C

C -> A

Can this be solved by using graph theory? For example, represent all dependency pairs using a directed graph and calculate recursive sum of outdegrees of adjacent nodes. Any other ideas are welcome.

Let me know what is the best way to get it.

Answer 1

Calculating the direct dependencies is very straightforward. So for your purposes I'd recommend finding the count of all dependencies, then if you're interested in indirect only, you can just subtract the number of direct from the total.

The algorithm isn't too tricky, and in pseudocode would look something like:

count = 0
visited = [ ]
toVisit = [ startNode ]
while(toVisit not empty)
{
    current = toVisit.Pop
    for(dependency in current.dependencies)
    {
        if(dependency not in visited)
            toVisit.Push(dependency)
    }
    visited.Push(current)
    count++;
}

You're just traversing the graph, keeping track of all nodes already visited to make sure you don't revisit them (avoiding issues arising due to circular dependencies).