# Path

De Software testing

## Concepts

- A path is a sequence of statements. <bib>vincenzi-etal:2007</bib>

- A path is a finite sequence of nodes <math>(n_1, n_2, . . . , n_k)</math>, <math>k >= 2</math>, so that there is an edge from <math>n_i</math> to <math>n_i + 1</math> for <math>i = 1, 2, ..., k − 1</math>. <bib>vincenzi-etal:2007</bib>

- A path of length k for a program graph <math>G = (N, E)</math> is a sequence of <math>k</math> edges, <math>k > 0</math>, <math>(e_1, e_2, ..., e_k)</math> that holds the following condition: given that <math>n_p</math>, <math>n_q</math>, <math>n_r</math>, and <math>n_s</math> are nodes belonging to <math>N</math>, and <math>0 < i < k</math>, if <math>e_i = (n_p, n_q)</math> and <math>e_{i+1} = (n_r, n_s)</math>, then <math>n_q = n_r</math>. <bib>mathur:2008, 50</bib>

## Facts

- For nodes n, m in N, m is said to be a descendant of n (and n an ancestor of m) if there is a path from n to m. <bib>mathur:2008, 50</bib>

- For nodes n, m in N, m is said to be a proper descendant of n (and n a prosper ancestor of m) if there is a path from n to m and n !=m. <bib>mathur:2008, 50</bib>

- If there is an edge (n, m) in E, then m is a successor of n and n the predecessor of m. <bib>mathur:2008, 50</bib>

- The set of all successor and predecessor nodes of n is denoted by succ(n) and pred(n), respectively. <bib>mathur:2008, 50</bib>

- The node Start has no ancestor and End has no descendant. <bib>mathur:2008, 50</bib>

- Given paths p = {n1, n2, ..., nt} and s = {i1, i2, ..., iu}, s is a subpath of p if for some 1 <= j <= t and j + u - 1 <= t, i1 = nj, i2 = nj+1, ..., iu = nj+u-1. <bib>mathur:2008, 50</bib>

- For nodes n and m in N, n dominates m if n lies on every path from Start to m. We write dom(n, m) when n dominates m. <bib>mathur:2008, 55</bib>

- For nodes n and m in N, n is the immediate dominator of m when n is the last dominator of m along a path from the Start to m. <bib>mathur:2008, 55</bib>

- For nodes n and m in N, n postdominates m if n lies on every path from m to the End node. We write pdom(n, m) when n postdominates m. <bib>mathur:2008, 55</bib>

- For nodes n and m in N, n is an immediate postdominator of m if n is the first postdominator along a path from m to End. <bib>mathur:2008, 55</bib>

- When n != m, we refer to these as strict dominator and strict postdominator relations.