Prime Path Generator

Prime Path Generator is a prime path generator used to generate prime paths.

It is aimed to be faster than brute-force method.

What is prime path

A path p is prime if p is a maximal simple path, i.e. p cannot be extended without losing simplicity.

• What is difference between Prime Path Testing and Path Testing? - Stack Overflow
• Prime-Path-Coverage.pdf (virginia.edu)
• Minimum Number of Test Paths for Prime Path and Other Structural Coverage Criteria (inria.fr)

How does this tool work faster

The brute-force method

The brute-force method is:

1. generate all simple paths
2. check every simple path to get prime paths

It contains a lot of unnecessary steps. For example:

0 → 1
↓   ↓
2 → 3

There are only two prime paths 013 023. But the brute-force method will check 0 1 2 3 01 02 13 23 013 023.

We can do better

This tool will not check all simple paths. It focuses on the vertices with 0 indegree or 0 outdegree:

0 → 1{3}
↓
2{3}

0{13, 23}

{013, 023}

What about cycles

0 → 1
↑   ↓
3 ← 2

The brute-force method will check 0 1 2 3 01 ...

But this tool knows that there are 4 prime paths in a 4-length cycle:

[01230]123
0[12301]23
01[23012]3
012[30123]

What about mixed paths

0 → 1 → 4
↑   ↓
3 ← 2

step 1

0 → 1{4}
↑   ↓
3 ← 2

step2

As a cycle:

0 → 1
↑   ↓
3 ← 2

[01230]123
0[12301]23
01[23012]3
012[30123]

step3

As not a cycle:

0 → 1{4}
↑
3 ← 2

23014

The full algorithm is a bit more complicated. See the source code if you are curious.

Why is the result right

There is no formal proof yet.

The unit tests show that this tool generates the same result as the brute-force method, at least for test data.

Alternatives

• heshenghuan/Prime-Path-Coverage
  • Python 2.7
  • unfriendly usage
  • no license