Software engineering- Halstead Software Science

Halstead complexity metrics were developed by the late Maurice Halstead as a means of determining a quantitative measure of complexity directly from the operators and operands in the module to measure a program module's complexity directly from source code.Among the earliest software metrics, they are strong indicators of code complexity.Halstead Science is an estimation technique to find out size, tiem and effort of a software

Number of Operators and Operands

Halstead´s metrics is based on interpreting the source code as a sequence of tokens and classifying each token to be an operator or an operand.

First we need to compute the following numbers, given the program:

• n1 = the number of distinct operators
• n2 = the number of distinct operands
• N1 = the total number of operators
• N2 = the total number of operands

The number of unique operators and operands (n1 and n2) as well as the total number of operators and operands (N1 and N2) are calculated by collecting the frequencies of each operator and operand token of the source program.

From these numbers, following measures can be calculated:

 Program length (N)

The program length (N) is the sum of the total number of operators and operands in the program:

        N = N1 + N2

Vocabulary size (n)

The vocabulary size (n) is the sum of the number of unique operators and operands:

        n = n1 + n2

Program volume (V)

The program volume (V) is the information contents of the program, measured in mathematical bits. It is calculated as the program length times the 2-base logarithm of the vocabulary size (n) :

        V = N * log2(n)
Halstead's volume (V) describes the size of the implementation of an algorithm. The computation of V is based on the number of operations performed and operands handled in the algorithm. Therefore V is less sensitive to code layout than the lines-of-code measures.
The volume of a function should be at least 20 and at most 1000. The volume of a parameterless one-line function that is not empty; is about 20. A volume greater than 1000 tells that the function probably does too many things.
The volume of a file should be at least 100 and at most 8000. These limits are based on volumes measured for files whose LOCpro and v(G) are near their recommended limits. The limits of volume can be used for double-checking.

Difficulty level (D)

The difficulty level or error proneness (D) of the program is proportional to the number of unique operators in the program.
D is also proportional to the ration between the total number of operands and the number of unique operands (i.e. if the same operands are used many times in the program, it is more prone to errors).

        D = ( n1 / 2 ) * ( N2 / n2 )

Program level (L)

The program level (L) is the inverse of the error proneness of the program.
I.e. a low level program is more prone to errors than a high level program.

        L = 1 / D

Effort to implement (E)

The effort to implement (E) or understand a program is proportional to the volume and to the difficulty level of the program.

        E = V * D

Estimated Program Length

According to Halstead, The first hypothesis of software science is that the length of a well

Structured program is a function only of the number of unique operators and operands.
the estimated lngth is denoted by N^

N^= n1log2n1+n2log2n2

Potential Volume:
Amongst all the programs, the one that has minimal size is said to have the potential volume, V*. Halstead argued that the minimal implementation of any algorithm was through a reference to a procedure that had been previously written. The implementation of this algorithm would then require nothing more than invoking the procedure and supplying the operands for its inputs and output parameters.
V*= (2+n2*) log2( 2+n2*)

Estimated program Level/difficulty

Halstead offered an alternate formula that estimates the program level.

L^ =2n2/n1N2

Hence, D =1 /L^

Effort:

Halstead hypothesized that the effort required to implement a program increases as the size of the program increases. It takes more effort to implement a program at a lower level than the higher level.

E= V/L^

Time to implement (T)

John stroud suggested that human mind is capable of making a limited number of elementary discriminations per second. Stroud claims that β (stroud number) ranges between 5 to 20. Since Effort uses elementary discriminations as its unit of measure, the programming time would be: T = E / β

β is normally set to 18 since this seemed to give best results in Halstead earliest experiments.

Cyclomatic complexity - Connection matrix

Connection Matrix  - cyclomatic complexity

Each node on the flow graph is identified by numbers, while each edge is identified by letters. A letter entry is made in the matrix to correspond to a connection between two nodes. For example node 3 is connected to node 4 by edge b.to this point, the graph matrix is nothing more than a tabular representation of a flow graph. However by adding a link weight to each matrix entry, the graph matrix can become a powerful tool for evaluating program control structure during testing. The link weight provides additional information about control flow. In its simplest form, the link weight is 1 (a connection exists) or 0(a connection does not exist). To illustrate we use the simplest weighting to indicate connections (0 or 1).

Each letter has been replaced with a 1, indicating that a connection exists (zeros have been excluded for clarity). Represented in this form, the graph matrix is called a connection matrix.

In the connection matrix, each row with two or more entries represents a predicate node. Therefore performing the arithmetic shown to the right of the connection matrix provides us with a method for determining Cyclomatic complexity.

Implementation

The control flow graph can be implemented using the adjacency matrix data structure. The procedure for creating the connection matrix from a control flow graph can be stated as a two dimensional array is declared. Its size is equal to the number of nodes in the flow graph.
construct the adjacency matrix Aij = 1 if there is an edge from node i to node j.
Aij = 0 if there is no edge.

The complexity can be found out from this adjacency matrix using the procedure below.

1. for each row, find out the number of 1’s in it. Sutract 1 from this. Save the result
2. after doing step 1 on all rows, sum the results and add 1. this will give the Cyclomatic complexity.

Software Engineering - McCabe's Cyclomatic metric

McCabe's Cyclomatic metric, V(G) of a graph "G" with "n" vertices and "e" edges is given by the following formula

V(G) = e – n + 2

Let us take an example of a program; wherein we associate it with a directed graph that has unique entry and exit nodes. Each node in the graph, G, corresponds to a block of statements in the program where flow is sequential and the arcs correspond to branches taken in the program. This graph is known as a "Flow Graph".

The Cyclomatic Complexity, V(G) provides us two things

1) To find the number of independent paths through the program.

2) To provide an upper bound for the number of test cases that must be executed in order to test the program thoroughly. The complexity measure is defined in terms of independent paths. It is defined as any path through the program that introduces at least one new set of processing statements or a new condition.

The following steps are usually followed

Step – 1: Construction of flow graph from the source code or flow charts.

Step – 2: Identification of independent paths.

Step – 3: Computation of Cyclomatic Complexity.

Step – 4: Test cases are designed.

Using the flow graph, an independent path can be defined as a path in the flow graph that has at least one edge that has not been traversed before in other paths. A set of independent paths that cover all the edges is a basic set. Once the basis set is formed, test cases should be written to execute all the paths in the basis set.

Properties of Cyclomatic Complexity

The following are the properties of Cyclomatic Complexity represented as V(G)

1) V(G) >= 1.

2) V(G) is the maximum number of independent paths in graph, G.

3) Inserting and deleting functional statements to G does not affect V(G).

4) G has only one path if and only if V(G) = 1.

5) Inserting a new row in G, increases V(G) by unity.

Let us see the meaning of V(G)
For small programs Cyclomatic Complexity can be calculated manually, but automated tools are essential as several thousands of lines of code are possible in each program in a project. It will be very difficult to manually create flow graphs for large programs.

There are several tools that are available in the market, which can compute Cyclomatic Complexity. Note that calculating the complexity of a module after it has been built and tested may be too late. It may not be possible to redesign a complex module after it has been tested. Thus, some basic complexity checks must be performed on the modules before embarking upon the testing (or even coding) phase. Based on the complexity number that emerges from using the tool, one can conclude what actions need to be taken for complexity measure using the table given below

Complexity No.	Corresponding Meaning of V(G)
1-10	1) Well-written code, 2) Testability is high, 3) Cost / effort to maintain is low
10-20	1) Moderately complex code, 2) Testability is medium, 3) Cost / effort to maintain is medium.
20-40	1) Very complex code, 2) Testability is low, 3) Cost / effort to maintain is high.
> 40	1) Not testable, 2) Any amount of money / effort to maintain may not be enough

Software engineering -Cyclomatic Complexity

Basis Path Testing : Basis path testing is a white box testing technique first proposed by Tom McCabe. The Basis path method enables to derive a logical complexity measure of a procedural design and use this measure as a guide for defining a basis set of execution paths. Test Cases derived to exercise the basis set are guaranteed to execute every statement in the program at least one time during testing.

Flow Graph Notation: The flow graph depicts logical control flow using a diagrammatic notation. Each structured construct has a corresponding flow graph symbol.

Cyclomatic Complexity: Cyclomatic complexity is a software metric that provides a quantitative measure of the logical complexity of a program. When used in the context of a basis path testing method, the value computed for Cyclomatic complexity defines the number for independent paths in the basis set of a program and provides us an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once.

An independent path is any path through the program that introduces at least one new set of processing statements or a new condition.

Computing Cyclomatic Complexity: Cyclomatic complexity has a foundation in graph theory and provides us with 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+2P Where E, is the number of flow graph edges, N is the number of flow graph nodes, P is independent component.

3. Cyclomatic complexity, V (G) for a flow graph, G is also defined as:
V (G) = Pie+1 where Pie is the number of predicate nodes contained in the flow graph G.

4. Graph Matrices: The procedure for deriving the flow graph and even determining a set of basis paths is amenable to mechanization. To develop a software tool that assists in basis path testing, a data structure, called a graph matrix can be quite useful.
A Graph Matrix is a square matrix whose size is equal to the number of nodes on the flow graph. Each row and column corresponds to an identified node, and matrix entries correspond to connections between nodes. The connection matrix can also be used to find the cyclomatic complexity