header

Program Information

Name: ShortestPath
Domain: Algorithm
Functionality: Calculating the shortest path
Input: $G$ is a graph randomly generated;  $\pi (G)$ is a permutation of G; $x$ and $y$ are different vertices in $G$; $x'$ and $y'$ are vertices in the graph $\pi (G)$ corresponding to $x$ and $y$.
Output: Let us assume that the output path  $ShortestPath(G,x,y)=(x,v_1,v_2,\dots , v_k,y)$ and the corresponding distance is $ ShortestPath(G,x,y).length $

Reference

 Metamorphic Testing and Beyond https://doi.org/10.1109/STEP.2003.18; 
An Effective Testing Method for End-User Programmers https://doi.org/10.1145/1082983.1083236; 
Metamorphic Testing:A New Approach for Generating Next Test Cases;  

MR Information

MR1------

Description:
Property: $ShortestPath(G,x,y).length=ShortestPath(\pi (G),x',y').length$
Source input: $(G,x,y)$
Source output: $ShortestPath(G,x,y)$
Follow-up input: $(\pi (G),x',y')$
Follow-up output: $ShortestPath(\pi (G),x',y')$
Input relation: $(G,x,y) \Rightarrow (\pi(G),x',y')$
Output relation: $ShortestPath(G,x,y).length=ShortestPath(\pi (G),x',y').length$
Pattern:

MR2------

Description:
Property: $ShortestPath(G,x,y).length=ShortestPath(G,y,x).length$
Source input: $(G,x,y)$
Source output: $ShortestPath(G,x,y)$
Follow-up input: $(G,y,x)$
Follow-up output: $ShortestPath(G,y,x)$
Input relation: $(G,x,y) \Rightarrow (G,y,x)$
Output relation: $ShortestPath(G,x,y).length=ShortestPath(G,y,x).length$
Pattern:

MR3------

Description:
Property: $ShortestPath(G,x,y).length=ShortestPath(G,x,v_i).length+ShortestPath(G,v_i,y).length $ for any $1 \leq i \leq k$
Source input: $(G,x,y)$
Source output: $ShortestPath(G,x,y)$
Follow-up input: $(G,x,v_i),(G,v_i,y)$
Follow-up output: $ShortestPath(G,x,v_i),ShortestPath(G,v_i,y)$
Input relation: $(G,x,y) \Rightarrow (G,x,v_i),(G,v_i,y)$
Output relation: $ShortestPath(G,x,y).length=ShortestPath(G,x,v_i).length+ShortestPath(G,v_i,y).length$
Pattern:

MR4------

Description:
Property: $ShortestPath(G,x,y).length=ShortestPath(G,y,v_i).length+ShortestPath(G,v_i,x).length $ for any $1 \leq i \leq k$
Source input: $(G,x,y)$
Source output: $ShortestPath(G,x,y)$
Follow-up input: $(G,y,v_i),(G,v_i,x)$
Follow-up output: $ShortestPath(G,y,v_i),ShortestPath(G,v_i,x)$
Input relation: $(G,x,y) \Rightarrow (G,y,v_i),(G,v_i,x)$
Output relation: $ShortestPath(G,x,y).length=ShortestPath(G,y,v_i).length+ShortestPath(G,v_i,x).length$
Pattern:

MR5------

Description:
Property: $ShortestPath(G,x,y).length=ShortestPath(G,x,v_1).length+ShortestPath(G,v_1,v_k).length+\\ ShortestPath(G,v_k,y).length $
Source input: $(G,x,y)$
Source output: $ShortestPath(G,x,y)$
Follow-up input: $(G,x,v_1),(G,v_1,v_k),(G,v_k,y)$
Follow-up output: $ShortestPath(G,x,v_1),ShortestPath(G,v_1,v_k),ShortestPath(G,v_k,y)$
Input relation: $(G,x,y) \Rightarrow (G,x,v_1),(G,v_1,v_k),(G,v_k,y)$
Output relation: $ShortestPath(G,x,y).length=ShortestPath(G,x,v_1).length+ShortestPath(G,v_1,v_k).length+\\ ShortestPath(G,v_k,y).length$
Pattern:

MR6------

Description:
Property: $ShortestPath(G,x,y).length=ShortestPath(G,y,v_k).length+ShortestPath(G,v_k,v_1).length+\\ ShortestPath(G,v_1,x).length $
Source input: $(G,x,y)$
Source output: $ShortestPath(G,x,y)$
Follow-up input: $(G,y,v_k),(G,v_k,v_1),(G,v_1,x)$
Follow-up output: $ShortestPath(G,y,v_k),ShortestPath(G,v_k,v_1),ShortestPath(G,v_1,x)$
Input relation: $(G,x,y) \Rightarrow (G,y,v_k),(G,v_k,v_1),(G,v_1,x)$
Output relation: $ShortestPath(G,x,y).length=ShortestPath(G,y,v_k).length+ShortestPath(G,v_k,v_1).length+\\ ShortestPath(G,v_1,x).length$ 
Pattern:
Insert title here