| 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 - 3
Flow graph notation
Flow graph is the notation for the representation of control flow. The flow graph depicts logical control flow using the notation illustrated below. |
| |
| Sequence |
 |
| if |
 |
| While |
 |
| Until |
 |
| Case |
 |
| Each structured construct has a corresponding flow graph symbol. Each circle called a flow graph node represents one or more procedural statements. A sequence of process boxes and a decision diamond can map into a single node. The arrows in the flow graph called edges or links represent flow of control and are analogous to flowchart arrows. An edge must terminate at a node even if the node does not represent any procedural statements. Areas bound by edges and nodes are called regions. When counting regions we include the area outside the graph as a region. In the C language the conditional constructs are if, while, case etc. When compound conditions are encountered in a procedural design, the generation of a flow graph becomes slightly more complicated. A compound condition occurs when one or more Boolean operators is present in a conditional statement. A separate node is created for each of the conditions a and b in the statement if a OR b. Each node that contains a condition is called a predicate node and is characterized by two or more edges emanating from it.
3. From the control flow graph, create the connection matrix.
The connection matrix is a kind of graph matrix.
Graph matrices
The procedure for deriving the flow graph and even determining a set of basis paths is amenable to mechanization. To develop a soft ware 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 (ie number of rows and columns) 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 (an edge) between nodes. An example of a flow graph and its corresponding graph matrix is shown here.
Cont... |
| TOP |
| |
|
