Simple path and prime path software testing

Simple path

A simple path is a path in which any node can’t appear more than once but only starting and ending nodes can appear more than once.

In other words, we can say that “A path that does not repeat vertices or node is called a simple path”.

Prime Path

The prime path is basically a simple path and it does not appear as a sub-path of any other simple path.

Prime path are subset of simple paths.

round trip path
Figure: simple path, prime path

Simple Paths

In the figure, followings are the simple paths.

Length 0:

Following nodes represents simple paths with length 0 because having no outgoing edge.

Simple paths = [0], [1], [2], [3]

[0] is a simple path because [0] is not appearing more than once.

[1] is a simple path because [1] is not appearing more than once.

[2] is a simple path because [2] is not appearing more than once.

[3] is a simple path because [3] is not appearing more than once.

Length 1:

Following nodes represents simple paths with length 1 because having  total 1 outgoing edge.

Simple paths = [ 0, 1], [ 0, 2 ], [ 1, 3 ], [ 2, 3 ], [ 3, 0 ],

[ 0, 1] is a simple path because [0, 1] is not appearing more than once.

[ 0, 2 ] is a simple path because [0, 2] is not appearing more than once.

[ 1, 3 ] is a simple path because [1, 3] is not appearing more than once.

[ 2, 3 ] is a simple path because [2, 3] is not appearing more than once.

[ 3, 0 ] is a simple path because [3, 0] is not appearing more than once.

Length 2:

Following nodes represents simple paths with length 2 because having total 2 outgoing edges.

Simple paths = [ 0, 1, 3 ], [ 0, 2, 3 ], [ 1, 3, 0 ], [ 2, 3, 0 ],[ 3, 0, 1 ], [3, 0, 2 ],

Length 3:

Following nodes represents simple paths with length 3 because having total 3 outgoing edges.

Simple paths = [ 0, 1, 3, 0 ], [ 0, 2, 3, 0], [ 1, 3, 0, 1 ], [ 2, 3, 0, 2 ], [ 3, 0, 1, 3 ], [ 3, 0, 2, 3 ], [ 1, 3, 0, 2 ],[ 2, 3, 0, 1 ].

Prime Paths :

All of the following simple paths are the prime path.

does not appear as a sub-path of any other simple path.

[ 0, 2, 3, 0], [ 0, 1, 3, 0 ], [ 2, 3, 0, 2 ],  [ 1, 3, 0, 1 ], [ 3, 0, 2, 3 ], [ 3, 0, 1, 3 ], [ 2, 3, 0, 1 ] , [ 1, 3, 0, 2 ]

[ 0, 2, 3, 0] is a prime path because [ 0, 2, 3, 0] is a simple path and [ 0, 2, 3, 0] does not appear as a sub-path of any other simple path.

[ 0, 1, 3, 0 ] is a prime path because [ 0, 1, 3, 0 ]is a simple path and [ 0, 1, 3, 0 ] does not appear as a sub-path of any other simple path.

[ 2, 3, 0, 2 ] is a prime path because [ 2, 3, 0, 2 ] is a simple path and [ 2, 3, 0, 2 ] does not appear as a sub-path of any other simple path.

[ 1, 3, 0, 1 ] is a prime path because [ 1, 3, 0, 1 ] is a simple path and [ 1, 3, 0, 1 ] does not appear as a sub-path of any other simple path.

[ 1, 3, 0, 1 ] is a prime path because [ 1, 3, 0, 1 ] is a simple path and [ 1, 3, 0, 1 ] does not appear as a sub-path of any other simple path.

[ 3, 0, 2, 3 ] is a prime path because [ 3, 0, 2, 3 ] is a simple path and [ 3, 0, 2, 3 ] does not appear as a sub-path of any other simple path.

[ 3, 0, 1, 3 ] is a prime path because [ 3, 0, 1, 3 ] is a simple path and [ 3, 0, 1, 3 ] does not appear as a sub-path of any other simple path.

[ 2, 3, 0, 1 ] is a prime path because [ 2, 3, 0, 1 ] is a simple path and [ 2, 3, 0, 1 ] does not appear as a sub-path of any other simple path.

 [ 1, 3, 0, 2 ] is a prime path because  [ 1, 3, 0, 2 ] is a simple path and  [ 1, 3, 0, 2 ] does not appear as a sub-path of any other simple path.

Round-Trip Path

A Round-Trip Path is a path that starts and ends with the same nodes.

Prime path coverage criteria in software testing

According to prime path coverage(PPC), each prime path must be covered in test requirements.

Prime Path Coverage software testing

! represents that the simple path that cannot be extended more.

Possible reasons to stop the extension of simple path.

  • Reached a final node
  • if it is extended by one more , then it would create an internal loop, and it represents that it is no longer be a simple path.

* represents that the simple path is a loop and should not be extended further because if we extend it more than the simple path would have an internal loop, and  simple paths must not have such loop.

Steps

  1. Begin with all nodes of the graph created as a list as mentioned below;

[5]

[6]

[7]

[8]!

  1. Now we can extend each of the paths without a symbol to another node via a valid edge and we need to observe that if any of the simple paths need to be marked with the ‘*’ or ‘!’ .

[5]   [5, 6]

[6]   [6, 7]

[7]    [6, 8]!

[8]!   [7, 6]

  1. Continue step two until all simple paths cannot be expanded further.

Iteration 6 of Step 6:

[5]     [5, 6]    [5, 6, 7]!

[6]     [6, 7]    [5, 6, 8]!

[7]     [6, 8]    ! [6, 7, 6]*

[8]!    [7, 6]     [7, 6, 7]*

[7, 6, 8]!

[5, 6, 7] cannot be further extended because the only edge that can extend it is the 6 and the path will be [5, 6, 7, 6].

However, this gives us an internal loop because [5, 6, 7] is a path and if we again move back from 7 to 6, then it represents inner loop, and simple paths cannot have internal loops, thus [5, 6, 7] cannot be extended further.

  1. Remove all paths that are a sub path of another path. For example in this case [7, 6, 8] is a path and [7, 6, 7] is also a unique path at the bottom and [7, 6] is a sub path of [7, 6, 8] and [7, 6, 7] and a useful technique for removing the sub-paths is to start from longest length and go to shortest length.

[5]   [5, 6]  [5, 6, 7]!

[6]  [6, 7]  [5, 6, 8]!

[7]  [6, 8]!  [6, 7, 6]*

[8]!  [7, 6]  [7, 6, 7]*

[7, 6, 8]!

  1. The remaining paths are the simple paths that make up the test requirements that are needed to satisfy prime path coverage for the given graph.

Test Requirements are {[5, 6, 7], [5, 6, 8], [6, 7, 6], [7, 6, 7], [7, 6, 8]}

  1. If test paths are needed to be created, expand the given path as needed.

Note:  a test path must start with an initial node and end with a final node.

Multiple test requirements can be satisfied by one test path.

Example: [5, 6, 7] made in a test path is [5, 6, 7, 6, 8]. This test path would satisfy [5, 6, 7], [6, 7, 6], and [7, 6, 8].

Repeat this until your set of test paths satisfy all of the test requirements.

Some facts about PPC:

  • PPC subsumes node coverage.
  • PPC subsumes edge coverage.

More Similar Testing Tutorials