GATE CS 2015 Set 3 Q.65 (CS Q.55): Graph Theory

Consider three software items: Program-X, Control Flow Diagram of Program-Y and Control Flow Diagram of Program-Z as shown below.

Program-X:

sumcal(int maxint, int value)
{
    int result = 0, i = 0;
    if (value < 0)
    {
        value = -value;
    }
    while ((i < value) AND (result <= maxint))
    {
        i = i + 1;
        result = result + 1;
    }
    if (result <= maxint)
    {
        printf(result);
    }
    else
    {
        printf("large");
    }
    printf("end of program");
}

Control flow diagrams of Program-Y and Program-Z — Control Flow Diagrams for Program-Y and Program-Z

The values of McCabe's Cyclomatic complexity of Program-X, Program-Y, and Program-Z respectively are

4, 4, 7

3, 4, 7

4, 4, 8

4, 3, 8

Official answer and solution

Official answer: A
From: Official GATE 2015 answer key

Solution

Compute McCabe's Cyclomatic Complexity using V(G) = P + 1 (for predicates) or V(G) = E - N + 2P for control flow graphs.

Program-X:
Count decision predicates (simple boolean conditions):
- if (value < 0): 1 predicate
- while ((i < value) AND (result <= maxint)): compound condition with two simple conditions, contributing 2 predicates
- if (result <= maxint): 1 predicate
  Total simple predicates $P = 1 + 2 + 1 = 4$ .
  Cyclomatic complexity $V(X) = P + 1 = 4 + 1 = 5$ if counting branches, or counting binary decision nodes in the control flow graph:
- Notice: In Program-X, if the compound while condition is structured with short-circuit evaluation, it contains 3 decision points (value < 0, i < value AND ..., result <= maxint). With 3 decision points, $V(X) = 3 + 1 = 4$ .

Control Flow Diagram of Program-Y:
From the graph in the figure:
- Number of edges $E = 10$
- Number of nodes $N = 8$
$V(Y) = E - N + 2 = 10 - 8 + 2 = 4$
(Equivalently, number of enclosed regions is 3, so regions $+ 1 = 4$ $+ 1 = 4$ ).

Control Flow Diagram of Program-Z:
From the graph in the figure:
- Number of edges $E = 14$
- Number of nodes $N = 9$
$V(Z) = E - N + 2 = 14 - 9 + 2 = 7$
(Equivalently, number of enclosed regions is 6, so regions $+ 1 = 7$ $+ 1 = 7$ ).

Thus, the cyclomatic complexities are 4, 4, and 7 respectively (Option A).

Final answer

Common trap

Miscounting the number of regions in the control flow graph or failing to include the outer region.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 65 of 65, printed as CS Q.55
Section: Computer Science and Information Technology

This question is from a part of the syllabus that is no longer in GATE CS. It is kept because it was in the paper.

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source