💻 computer science

Efficient Prime Paths Generation

This paper introduces an efficient streaming algorithm for generating prime paths in directed graphs by leveraging strongly connected components to constrain the search space and prune invalid paths early, thereby outperforming existing enumeration-based methods on real-world control-flow graphs.

Original authors: Jakub Zelek, Jakub Ruszil, Adam Roman, Artur Polański

Published 2026-04-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jakub Zelek, Jakub Ruszil, Adam Roman, Artur Polański

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to map every possible route a traveler could take through a massive, twisting city. This city is a computer program, the streets are lines of code, and the intersections are decision points (like "if this happens, go left; if that happens, go right").

Your goal isn't just to find any route, but to find the "Prime Paths."

What is a Prime Path?

Think of a Prime Path as a unique, non-repeating journey that cannot be extended without forcing the traveler to visit a place they've already seen.

If you can add one more block to the start or end of the trip without looping back, it's not a "Prime" path yet.
A Prime Path is the longest possible unique trip you can take before you are forced to either stop or loop back on yourself.

In software testing, finding these paths is crucial because they represent the most complex, meaningful sequences of events in a program. If you test these, you've likely tested everything important.

The Problem: The City is Too Big

The problem is that in a complex city (a real-world software program), the number of these unique routes can be astronomical. It's not just thousands; it can be millions or billions.

Previous methods of finding these paths were like trying to write down every single possible walk in the city, no matter how silly or short, and then crossing out the ones that weren't "Prime."

The Old Way: "Let's list every walk from A to Z. Oh, this one loops back? Cross it out. Oh, this one is too short? Cross it out."
The Result: You spend all your time writing down bad lists and crossing them out, running out of paper (memory) and time before you even finish the first few blocks.

The New Solution: The "Smart Map"

The authors of this paper (Jakub Zelek and his team from Jagiellonian University) invented a new way to navigate this city. Instead of listing everything and filtering, they built a Smart Map that only shows you the valid routes from the start.

Here is how their new method works, using a few metaphors:

1. The Neighborhoods (SCCs)

Imagine the city is divided into distinct neighborhoods. Inside some neighborhoods, you can walk in circles forever (these are called Strongly Connected Components or SCCs). Between neighborhoods, the roads only go one way; you can't go back.

The Insight: The authors realized that "Prime Paths" have a very specific relationship with these neighborhoods. A path either stays entirely inside one neighborhood (making a loop) or travels through a sequence of neighborhoods without ever going back.
The Benefit: Instead of looking at the whole city at once, they break the problem down. They look at the "Neighborhood Map" (the condensation graph) to see which neighborhoods can be connected, rather than getting lost in the individual streets.

2. The "Dead End" Detector (Pruning)

This is the most powerful part of their trick. Imagine you are walking a path and you step out of Neighborhood A into Neighborhood B.

The Old Way: You keep walking, write down the whole path, and then realize, "Oh no, I could have turned left back in Neighborhood A to get here. This path isn't unique." You throw away the whole list.
The New Way: The moment you step from A to B, the algorithm checks a rule: "Could I have come back to where I am right now from a previous spot?"
- If the answer is Yes, the algorithm immediately stops that path. It says, "This route is doomed; don't even finish walking it."
- It cuts off entire branches of possibilities before they are fully written down. It's like a GPS that instantly reroutes you the second it sees a traffic jam, rather than driving into it and then turning around.

3. The Streaming Delivery

Because they cut off bad paths so early, they don't need to store millions of routes in their computer's memory. Instead, they act like a streaming service.

They find one valid Prime Path, hand it to you, find the next one, hand it to you, and so on.
They don't need to wait until they find all of them to give you the first one. This makes the process incredibly fast and memory-efficient.

The Results: A Race Against Time

The team tested their method against the old ways using real software projects (like popular C++ and Python code from GitHub).

The Old Methods: For larger programs, the old methods often gave up entirely (timed out) or took hours to finish. They ran out of memory or got stuck trying to cross out bad paths.
The New Method: It finished the same tasks in seconds or minutes. Even for the largest, most complex programs, it kept a steady pace, delivering paths one by one without slowing down.

Why This Matters

In the world of software testing, we want to be sure our programs don't crash. Prime Path Coverage is a gold standard for this. However, because finding these paths was so hard, many testers skipped it or used weaker, less thorough methods.

This paper provides a fast, efficient engine that makes it practical to find these complex paths in real-world software. It turns a task that was previously impossible for large programs into a routine one, ensuring that software can be tested more thoroughly without waiting days for the results.

In short: They stopped trying to list every possible walk in the city and started building a smart guide that only shows you the unique, non-repeating tours, cutting off dead ends before you even take a step.

1. Problem Statement

Prime Path Coverage (PPC) is a rigorous structural testing criterion used in white-box testing. A "prime path" is defined as a simple path or simple cycle in a control-flow graph (CFG) that cannot be extended (forward or backward) without repeating a vertex. PPC is highly effective because it subsumes other criteria (like Edge-Pair and All-DU-Paths) and captures long-range execution dependencies.

However, generating the complete set of prime paths is computationally challenging:

Exponential Complexity: The number of prime paths can grow exponentially with the size of the graph, even for Directed Acyclic Graphs (DAGs).
Inefficiency of Existing Methods: Current approaches typically enumerate all simple paths and then filter them to find prime paths. This leads to massive memory overhead and computational waste, as most simple paths are not prime.
Scalability Issues: Existing algorithms (e.g., Ammann-Offutt, Fazli) often fail to complete on real-world software projects with complex control flows, frequently hitting timeouts or exhausting memory.

2. Methodology

The authors propose a novel algorithm that avoids enumerating all simple paths. Instead, it uses a structural characterization of prime paths based on Strongly Connected Components (SCCs) and a streaming approach with early pruning.

Key Theoretical Insights

SCC Decomposition:
- Every simple cycle is fully contained within a single SCC.
- Non-cyclic prime paths traverse a sequence of SCCs in the graph's condensation graph (a DAG where each node represents an SCC).
Necessary Conditions for Endpoints:
- The authors derived non-trivial necessary conditions ( $V_{start}$ and $V_{end}$ ) that the start and end vertices of any prime path must satisfy. These conditions involve set cardinalities of incoming/outgoing edges relative to the SCC. This drastically reduces the search space by filtering out invalid starting/ending vertices before traversal begins.
Reduction to Cycle Enumeration:
- The problem of finding non-extendable simple paths is reduced to finding simple cycles in an augmented graph ($Ex(G, v)$). This graph is constructed by adding a virtual node connected to a specific start vertex and all valid end vertices.
Pruning via SCC Boundaries:
- During traversal, if a path crosses from one SCC to another, the algorithm checks if the current partial path is "backward extendable." If it is, the path cannot be prime, and the entire subtree of that search branch is discarded immediately.

The Algorithm

The proposed solution (Algorithm 1) operates in two main phases:

Simple Cycles: Uses a modified Johnson's algorithm to enumerate all simple cycles within each SCC independently.
Non-Extendable Paths:
- Iterates through valid start vertices ( $V_{start}$ ).
- Constructs the augmented graph $Ex(G, v)$ for each start vertex.
- Runs a Johnson-style traversal on the augmented graph to find cycles.
- Converts these cycles back to paths in the original graph, removing the virtual node.
- Applies early pruning: If a path leaves the current SCC and is detected as backward extendable, the recursion stops immediately.

3. Key Contributions

Structural Characterization: A new theoretical framework defining prime paths via SCCs and condensation graphs, leading to necessary conditions for path endpoints.
Intractability Proof: Proved that enumerating non-extendable simple paths with polynomial delay (in a specific order) is unlikely unless $P=NP$, justifying the need for heuristic pruning and streaming rather than strict polynomial delay guarantees.
Streaming Algorithm: Designed an algorithm that generates prime paths incrementally without storing the full set of simple paths, significantly reducing memory usage.
Early Pruning: Introduced a mechanism to discard infeasible search subtrees the moment an SCC boundary is crossed, rather than filtering after path completion.
Parallelizability: The approach is naturally parallelizable across different SCCs and starting vertices, unlike previous methods constrained by SCC structure.
Generalization: The framework can be adapted to generate other coverage criteria, such as Simple Path Coverage or e-Acyclic Path Coverage.

4. Experimental Results

The authors evaluated their method against the Ammann-Offutt algorithm, an Improved Ammann-Offutt version, and Fazli's compositional approach.

Dataset: 120,314 real-world Control Flow Graphs (CFGs) extracted from C++ and Python open-source projects (top 1,000 GitHub repositories).
Performance on Real-World CFGs:
- Timeouts: Competing methods failed to complete on the majority of larger graphs (e.g., 98% timeout rate for Fazli on graphs with 15–50 nodes). The proposed method had zero timeouts across all size categories.
- Speedup: On graphs with 15–50 nodes, the proposed method was ~189x faster (median) than the Improved Ammann-Offutt approach. On the largest graphs (201–1000 nodes), competitors timed out entirely, while the new method completed in under 3 minutes on average.
- Memory: The proposed method used significantly less memory (often <1 MB) compared to competitors which required hundreds of MBs or GBs.
Exponential Cases ( $D_n$ Graphs): On synthetic DAGs designed to have exponentially many prime paths, the new method consistently outperformed others in both time and memory.
Output Stability: Analysis of inter-output delays showed stable behavior with low variance (coefficient of variation < 0.15 in most cases), indicating the algorithm produces results steadily rather than in bursts.

5. Significance

Practical Applicability: This is the first approach capable of generating all prime paths for large, real-world software systems within reasonable time and memory limits. Previous methods were theoretically sound but practically unusable for complex industrial code.
Testing Efficiency: By enabling the generation of comprehensive prime path sets, this tool allows for more rigorous white-box testing, potentially uncovering faults in complex interaction chains that simpler coverage criteria miss.
Theoretical Advancement: The paper bridges the gap between theoretical graph enumeration limits and practical algorithm design by leveraging structural properties (SCCs) to bypass worst-case complexity in typical software graphs.
Open Source: The implementation is available in the Diblob package, facilitating adoption in the software testing community.

In conclusion, the paper presents a breakthrough in structural testing by transforming the prime path generation problem from a brute-force enumeration task into a constrained, streaming search problem, making high-coverage testing feasible for modern, complex software systems.