Path Coverage

What Is Path Coverage? #

Path coverage requires that every unique execution path through a program or function is exercised at least once. A path is a complete sequence of statements from entry to exit.

Consider a function with two sequential if statements:

def process_order(amount, is_member):
    discount = 0

    if amount > 100:          # Decision 1
        discount = 10

    if is_member:             # Decision 2
        discount += 5

    return amount - discount

Statement coverage needs tests that execute every line — 2 tests could suffice.

Decision coverage needs both True and False for each decision — 2 tests suffice.

Path coverage needs every combination of paths through all decisions:

With 2 sequential decisions, we have 4 paths. With N sequential decisions, we have 2^N paths. This exponential growth is why full path coverage is often impractical.

The Path Explosion Problem #

Add a loop to the equation and paths become infinite:

def retry_request(url, max_retries=3):
    for attempt in range(max_retries):
        response = send_request(url)
        if response.status == 200:
            return response
    raise TimeoutError("Max retries exceeded")

The loop can execute 0, 1, 2, or 3 times. Each iteration adds a decision point. The number of distinct paths grows rapidly. For a loop that runs up to N times with M decisions inside, the total paths can reach M^N.

This is why practitioners use basis path testing instead of exhaustive path coverage.

Control Flow Graphs #

Before counting paths, represent the code as a control flow graph (CFG):

• Nodes represent statements or blocks of sequential statements
• Edges represent control flow between nodes
• Decision nodes have two or more outgoing edges

For the process_order function:

[Entry] → [discount=0] → <amount>100?>
    → Yes → [discount=10] → <is_member?>
    → No ────────────────→ <is_member?>
        → Yes → [discount+=5] → [return] → [Exit]
        → No ─────────────────→ [return] → [Exit]

Cyclomatic Complexity #

Cyclomatic complexity (introduced by Thomas McCabe in 1976) measures the number of linearly independent paths through a program. It provides the minimum number of test cases needed for basis path coverage.

Three equivalent formulas:

1. V(G) = E - N + 2 (E = edges, N = nodes)
2. V(G) = P + 1 (P = number of decision points/predicates)
3. V(G) = R (R = number of regions in the planar graph, including the outer region)

For process_order: 2 decisions → V(G) = 2 + 1 = 3? No — there are 4 paths. Cyclomatic complexity gives 3, which means 3 independent paths form the basis. The 4th path is a linear combination of the other 3.

Wait — let us be precise. The process_order function actually has V(G) = 3 using the edge/node formula (verify by drawing the CFG). But we identified 4 paths. The explanation: basis path testing finds the minimum set of independent paths that, combined, cover every edge. You may need additional paths beyond the basis set for complete path coverage.

Practical Cyclomatic Complexity Guidelines #

Most coding standards recommend keeping cyclomatic complexity below 10 per function. If it exceeds 10, the function is doing too much.

Basis Path Testing Method #

Tom McCabe’s basis path testing provides a systematic way to derive test cases:

Step 1: Draw the control flow graph.

Step 2: Calculate cyclomatic complexity V(G).

Step 3: Identify the basis set of independent paths. Start with the simplest path (typically the one that traverses the most “True” or “False” branches consistently), then vary one decision at a time.

Step 4: Create test cases for each basis path.

Example: Login Validation #

def validate_login(username, password, is_locked):
    if is_locked:                    # D1
        return "ACCOUNT_LOCKED"

    if not username:                 # D2
        return "USERNAME_REQUIRED"

    if len(password) < 8:           # D3
        return "PASSWORD_TOO_SHORT"

    return "VALID"

V(G) = 3 + 1 = 4 (three decisions plus one).

Basis paths:

1. D1=True → “ACCOUNT_LOCKED”
2. D1=False, D2=True → “USERNAME_REQUIRED”
3. D1=False, D2=False, D3=True → “PASSWORD_TOO_SHORT”
4. D1=False, D2=False, D3=False → “VALID”

Test cases:

Four test cases achieve basis path coverage.

Tools for Path Analysis #

• SonarQube — Reports cyclomatic complexity per function and file
• Lizard — Fast cyclomatic complexity analyzer supporting 20+ languages
• radon — Python-specific complexity analysis
• ESLint (complexity rule) — Enforces max cyclomatic complexity for JavaScript/TypeScript
• PMD — Java/Apex complexity analysis

# Lizard: analyze complexity of a project
lizard src/ --CCN 10 --warnings_only

# radon: Python complexity
radon cc my_module.py -a -nc

Exercise: Basis Path Testing #

Problem 1 #

Derive basis paths and test cases for this function:

def calculate_shipping(weight, distance, is_express):
    base_cost = 5.0

    if weight > 10:
        base_cost += weight * 0.5
    else:
        base_cost += weight * 0.3

    if distance > 500:
        base_cost *= 1.5

    if is_express:
        base_cost *= 2

    return round(base_cost, 2)

Problem 2 #

Calculate the cyclomatic complexity and determine how many basis path tests are needed:

def grade_student(score, attendance, has_extra_credit):
    if score >= 90:
        grade = "A"
    elif score >= 80:
        grade = "B"
    elif score >= 70:
        grade = "C"
    else:
        grade = "F"

    if attendance < 75:
        grade = "F"  # Override for poor attendance

    if has_extra_credit and grade != "F":
        grade = chr(ord(grade) - 1)  # Bump up one letter

    return grade

Path Coverage vs. Other Coverage Criteria #

Path coverage is the strongest criterion but is usually impractical for full coverage. Basis path testing provides a practical compromise.

When to Use Path Coverage #

Use basis path testing when:

• Testing critical algorithms (financial calculations, security logic)
• Code has moderate complexity (V(G) < 15)
• You need to justify test adequacy to auditors or reviewers
• Refactoring complex functions — paths help you understand what the code does

Skip full path coverage when:

• Functions have loops with many iterations
• Cyclomatic complexity exceeds 20 (refactor first)
• The code is simple enough that decision coverage suffices

Key Takeaways #

• Path coverage tests every unique execution path from entry to exit
• Full path coverage is impractical due to exponential path growth and infinite loop paths
• Cyclomatic complexity V(G) = P + 1 gives the minimum number of basis path tests
• Basis path testing is the practical approach — test independent paths, not all paths
• Keep cyclomatic complexity below 10 per function for testable, maintainable code
• Use tools like SonarQube, Lizard, or radon to measure complexity automatically