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: Part 2 continue...

How to determine Cyclomatic complexity?

1. Using the design or code as a foundation draws a corresponding flow graph. A flow graph is created using the symbols and construction rules. Then the complexity can be found out using any of the three ways mentioned above.
2. The Cyclomatic complexity, V(G) can be found out by applying data flow testing algorithms.
3. V(G) can also be determined without developing a flow graph, by counting all conditional statements in the procedure and adding 1(compound conditions count as two).
4. Cyclomatic complexity can be also found out by using a graph matrix. The control flow graph is used to develop a connection matrix. This matrix is used to determine the complexity.

Data flow testing

The data flow testing method select test paths of a program according to the locations of definitions and uses of variables in the program. A number of data flow testing strategies have been studied and compared. To illustrate the data flow testing approach, assume that each statement in the program is assigned a unique statement number and that each function does not modify its parameters or global variables. For a statement with S as its statement number,

DEF(S) = {X / statement S contains a definition of X}

USE(S) = {X / statement S contains a use of X}

If statement S is an I f or loop statement its DEF set is empty and its USE set is based on the condition of the statement S. The definition of variable X at statement S is said to be live at statement S’ if there exists a path from statement S to statement S’ that contains no other definition of X. a definition-use (DU) chain of variable X is of the form {X,S,S’} where S and S’ are statement numbers, X is in DEF(S) and USE(S’), and the definition of X in statement S is live at statement S’.

One simple data flow testing strategy is to require that every DU chain can be covered at least once. We refer to this strategy as the DU testing strategy. It has been shown that DU testing does not guarantee the coverage of all branches of a program. However a branch is not guaranteed to be covered by DU testing only in rare situations such as if-then-else constructs in which the then part has no definition of any variable and the else part does not exist. In this situation the else branch of the if statement is not necessarily covered by DU testing.

Data flow testing strategies are useful for selecting test paths of a program containing nested if and loop statements.

Aim of the project

Our aim is to design a software tool that will compute the Cyclomatic complexity for a programming language. Cyclomatic complexity is a software metric that provides a quantitative measure of the logical complexity of a program. We have to use the graph matrix as the operative data structure.

Specification

This software tool will take as its input, a program or code in C language and find out the Cyclomatic complexity of this program. The data structure used here is a graph matrix.

Design

As mentioned in the introduction part, there are different methods for finding the Cyclomatic complexity of a program. Here we are using graph matrix or connection matrix for finding out the complexity. The design of this software tool can be specified by the following steps.

1.First, we have to construct the flow chart of the program for which the complexity has to be found.

For drawing the flow chart, the conventional rules of flow charting must be used. The flow chart will depict the control flow of the program.

2.From the flow chart, construct the control flow graph.

Flow graph is notation for the representation of control flow. The flow graph depicts logical control flow.

Cont...