Page 185 - DCAP305_PRINCIPLES_OF_SOFTWARE_ENGINEERING

Unit 9: Metrics

Notes
Figure 9.2: Control Flow Graph for Module “Euclid”

through strongly connected directed graphs. A strongly connected graph is one in which
each node can be reached from any other node by following directed edges in the Graph.
The cyclomatic number in graph theory is defined as n + 1. Program control flow Graphs are
not strongly connected, but they become strongly connected when a “virtual edge” Is added
connecting the exit node to the entry node. The cyclomatic complexity definition for Program
control flow graphs is derived from the cyclomatic number formula by simply adding one to
represent the contribution of the virtual edge. This definition makes the cyclomatic Complexity
equal the number of independent paths through the standard control flow graph model, and
avoids explicit mention of the virtual edge.
Control flow graph of with the virtual edge added as a dashed line. This virtual edge is not just
a mathematical convenience. Intuitively, it represents the control flow through the rest of the
program in which the module is used. It is possible to calculate the amount of (virtual) control
flow through the virtual edge by using the conservation of flow equations at the entry and
exit nodes, showing it to be the number of times that the module has been executed. For any
individual path through the module, this amount of flow is exactly one. Although the virtual
edge will not be mentioned again in this document, note that since its flow can be calculated
as a linear combination of the flow through the real edges, its presence or absence makes no
difference in determining the number of linearly independent paths through the module.
9.1.2 Characterization of v(G) Using a Basis set of Control Flow Paths

Cyclomatic complexity can be characterized as the number of elements of a foundation put of
control pours paths through the module. Some familiarity with linear algebra is required to
follow the details, but the point is that cyclomatic complexity is precisely the minimum number
of Paths that can, in (linear) combination, generate all probable paths through the module. To

LOVELY PROFESSIONAL UNIVERSITY 179