| Home > Computer Science > Discrete Mathematics > Project
July 2002 |
| |
|
|
| 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... |
| TOP |
| |
|
| |
