Page 184 - DCAP305_PRINCIPLES_OF_SOFTWARE_ENGINEERING

Principles of Software Engineering

Notes 9.1.1 Control Flow Graphs
Control sprint graphs describe the logic arrangement of software modules. A module corresponds
to a solitary function or subroutine in typical languages, has a single entry and exit point, and
is brilliant to be used as a design component via a call/return mechanism. This document uses
C as the language for examples, and in C a module is a function. Each flow graph consists of
nodes and edges. The nodes represent computational statements or expressions, and the edges
represent transfer of control between nodes.
Each possible execution path of a software module has a corresponding path from the entry to
the exit node of the module’s control flow graph. This correspondence is the foundation for the
structured testing methodology.
As an example, consider the C function in which implements Euclid’s algorithm for finding
greatest common divisors. The nodes are numbered A0 through A13. The control flow graph
is shown in, in which each node is numbered 0 through 13 and edges are shown by lines
connecting the nodes. Node 1 thus represents the decision of the “if” statement with the true
outcome at node 2 and the false outcome at the collection node 5. The decision of the “while”
loop is represented by node 7, and the upward flow of control to the next iteration is shown by
the dashed line from node 10 to node 7. The path resulting when the module is executed with
parameters 4 and 2, as in “Euclid.” Execution begins at node 0, the beginning of the module,
and proceeds to node 1, the decision node for the “if” statement. Since the test at node 1 is false,
execution transfers directly to node 5, the collection node of the “if” statement, and proceeds to
node 6. At node 6, the value of “r” is calculated to be 0, and execution proceeds to node 7, the
decision node for the “while” statement. Since the test at node 7 is false, execution transfers out
of the loop directly to node 11, 8 then proceeds to node 12, returning the result of 2. The actual
return is modelled by execution proceeding to node 13, the module exit node. (See Figure 9.1
and Figure 9.2)

Figure 9.1: Annotated Source Listing for Module “Euclid”

Definition of cyclomatic complexity v(G)
Cyclomatic complexity is defined for each module to been + 2, where and n are the number
of edges and nodes in the control flow graph, respectively. Thus, for the Euclid’s algorithm
example, the complexity is 3 Cyclomatic complexity is also known as v(G), where v refers to the
cyclomatic number in graph theory and G indicates that the complexity is a function of the graph.
The word “cyclomatic” comes from the number of fundamental (or basic) cycles in connected,
undirected graphs [BERGE]. More importantly, it also gives the number of independent Paths

178 LOVELY PROFESSIONAL UNIVERSITY