Graph Theory-McCabe’s Cyclomatic Complexity

According to Graph Theory…

There are two types of graph mainly available..
1.Directed 2.Undirected.

Directed Graphs:
• a mathematical structure (with an appealing visual
representation) for representing things that are related
• consists of vertices (or nodes, or points), connected by
edges (or line segments, or arcs).

Vertices: A, B, C, D, E, F
Edges: (A,C), (A,C), (A,E), (B,C), (B,F), (C,D), (D,A), (E,F),

• Also: undirected graphs, rules restricting edges between
vertices, classification of vertices


Now the question comes like what is flowgraph?
Flowgraphs
• Directed graphs (flowgraphs) can be used to model control
flow of a program
• vertex = statement, edge = (A,B) if control flows from
statement A to B
• properties of flowgraphs may provide information about
properties of the code




in the exam the question comes like find out the complexity of the below written code:

Example:

public static boolean isPrime(int n) {
boolean prime = true;
int i = 2;
while (i < n) {
if (n % i == 0) {
prime = false;
}
i++;
}
return prime;
}

let us put notation over here:

as each of the line /statement is under flowgraph...i am putting A,B,C as the notation for the lines.Those will be my nodes where the controll of the pragramme will pass.

The graph looks like:

McCabe’s Cyclomatic Complexity Number (CCN)
• measures the number of linearly independent paths through
the flowgraph
• v(F) = e − n + 2, F the flowgraph of the code, n the number
of vertices, e the number of edges
• Intuition — the larger the CCN the “more complex” the code
• Various sources recommend a CCN of no more than 10-15
• Example: CCN = 8 − 7 + 2 = 3