Project July 2002

Question 1:

Specify, design and implement a software tool that will compute the Cyclomatic complexity for the programming language of your choice. Use the graph matrix as the operative data structure in your design.

Answer:

Cyclomatic complexity is a software metric that provides a quantitative measure of the logical complexity of a program. When used in the context of basis path testing method, the value computed for Cyclomatic complexity defines the number of independent paths in the basis set of a program and provides us with an upper bound for the number of tests that must be conducted to ensure that all statements have been executed once. An independent path is any path through the program that introduces at least one new set of processing statements or a new condition. When stated in terms of a flow graph, an independent path must move along at least one edge that has not been traversed before the path is defined. For example, a set of independent paths for the flow graph given below

Path 1: 1-11

Path 2: 1-2-3-4-5-10-1-11

Path 3: 1-2-3-6-8-9-10-1-11

Path 4: 1-2-3-6-7-9-10-1-11

Each new path introduces a new edge. The path 1-2-3-4-5-10-1-2-3-6-8-9-10-1-11 is not considered to be an independent path because it is simply a combination of already specified paths and does not traverse any new edges. Paths 1, 2, 3 and 4 constitute a basis set for the for the above flow graph. That is, if tests can be designed to force execution of these paths(a basis set), every statement in the program will have been guaranteed to be executed at least one time and every condition will have been executed on its true and false sides. This basis set is not unique. In fact a number of different basis sets can be derived for a given procedural design.

Cyclomatic complexity has a foundation in graph theory and provides us with an extremely useful software metric. Complexity is computed in one of the three ways.

1. The number of regions of the flow graph corresponds to the Cyclomatic complexity.
2. Cyclomatic complexity, V(G), for a flow graph, G is defined as

V(G) = E – N + 2

Where E is the number of flow graph edges, N is the number of flow graph nodes.

3. Cyclomatic complexity, V(G) for a flow graph G is also defined as

V(G) = P + 1

Where P is the number of predicate nodes contained in the flow graph G.

Referring to the above figure, the Cyclomatic complexity can be computed using each of the algorithms.

1. the flow graph has four regions.
2. V(G) = 11 edges – 9 nodes + 2 = 4
3. V(G) = 3 predicate nodes + 1 = 4

Therefore the Cyclomatic complexity of the flow graph is 4. The value of V(G) provides us with an upper bound for the number of independent paths that form the basis set and by implication, an upper bound on the number of tests that must be designed and executed to guarantee coverage of all program statements.

Cont...