3

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.

3
  • Any graph traversal algorithm will solve your problem, see en.wikipedia.org/wiki/Graph_traversal
    – Doc Brown
    Commented Aug 21, 2015 at 7:59
  • @gnat The link you quote says that "algorithm and data structure concepts" are on-topic. That seems to be what the poster is asking about. +1 from me.
    – kiwiron
    Commented Aug 21, 2015 at 8:43
  • @kiwiron request for software recommendation was deleted out of the question, see revisions history
    – gnat
    Commented Aug 21, 2015 at 12:34

1 Answer 1

4

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).

1
  • 1
    Simple and accurate. I couldn't have written it better myself.
    – Neil
    Commented Aug 21, 2015 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.