Page 186 - DCAP305_PRINCIPLES_OF_SOFTWARE_ENGINEERING

Principles of Software Engineering

Notes see this, consider the following mathematical model, which gives a vector space corresponding
to each flow graph. Each path has an associated row vector, with the elements corresponding to
edges in the flow graph. The value of each element is the number of times the edge is traversed
by the path.
Consider the path described in through the graph edges in the graph, the vector has 15 elements.
Seven of the edges are traversed exactly once as part of the path, so those elements have value
1. The other eight edges were not traversed as part of the path, so they have value 0.
Considering a set of several paths gives a matrix in which the columns correspond to edges and
the rows correspond to paths. From linear algebra, it is known that each matrix has a unique
rank (number of linearly independent rows) that is less than or equal to the number of columns.
This means that no matter how many of the (potentially infinite) number of possible paths are
added to the matrix, the rank can never exceed the number of edges in the graph. In fact, the
maximum value of this rank is exactly the cyclomatic complexity of the graph. A minimal set of
vectors (paths) with maximum rank is known as a basis, and a basis can also be described as a
linearly independent set of vectors that generate all vectors in the space by linear combination.
This means that the cyclomatic complexity is the number of paths in any independent set of
paths that generate all possible paths by linear combination.

Given any set of paths, it is possible to determine the rank by doing Gaussian Elimination on
the associated matrix. The rank is the number of non-zero rows once elimination is complete.
If no rows are driven to zero during elimination, the original paths are linearly independent.
If the rank equals the cyclomatic complexity, the original set of paths generates all paths by
linear combination. If both conditions hold, the original set of paths is a basis for the flow graph.
There are a few important points to note about the linear algebra of control flow paths. First,
although every path has a corresponding vector, not every vector has a corresponding path.
This is obvious, for example, for a vector that has a zero value for all elements corresponding
to edges out of the module entry node but has a nonzero value for any other element cannot
correspond to any path. Slightly less obvious, but also true, is that linear combinations of vectors
that correspond to actual paths may be vectors that do not correspond to actual paths. This follows
from the non-obvious fact that it is always possible to construct a basis consisting of vectors
that correspond to actual paths, so any vector can be generated from vectors corresponding to
actual paths. This means that one cannot just find a basis set of vectors by algebraic methods
and expect them to correspond to paths one must use a path-oriented technique such as that to
get a basis set of paths. Finally, there are a potentially infinite number of basis sets of paths for
a given module. Each basis set has the same number of paths in it (the cyclomatic complexity),
but there is no limit to the number of different sets of basis paths. For example, it is possible to
start with any path and construct a basis that contains
The details of the theory behind cyclomatic complexity are too mathematically complicated to be
used directly during software development. However, the good news is that this mathematical
Insight yields an effective operational testing method in which a concrete basis set of Paths is
tested: structured testing.
Example of v(G) and basis paths
Control flow graph for module “Euclid” with the fifteen edges numbered n0 to 14 along with
the fourteen nodes numbered 0 to 13. Since the cyclomatic complexity is 3(15 - 14 + 2), there is
a basis set of three paths. One such basis set consists of paths B1 through B3. (See Figure 9.3)

180 LOVELY PROFESSIONAL UNIVERSITY