| 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 - 4
Flow Graph
Graph
matrix
Referring to the figure, 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).
But link weights can be assigned
other, more interesting properties.
The probability that a link (edge)
will be executed.
The processing time expended during
traversal of a link.
The memory required during traversal
of a link.
The resources required during
traversal of a link.
To illustrate we use the simplest
weighting to indicate connections
(0 or 1). The graph matrix in
the above figure is redrawn as
below.
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.
4. From the connection
matrix, find out the Cyclomatic
complexity.
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.
Cont...
|
