# Path

Ir para: navegação, pesquisa

## Concepts

• A path is a finite sequence of nodes [itex](n_1, n_2, . . . , n_k)[/itex], [itex]k >= 2[/itex], so that there is an edge from [itex]n_i[/itex] to [itex]n_i + 1[/itex] for [itex]i = 1, 2, ..., k − 1[/itex]. <bib>vincenzi-etal:2007</bib>
• A path of length k for a program graph [itex]G = (N, E)[/itex] is a sequence of [itex]k[/itex] edges, [itex]k > 0[/itex], [itex](e_1, e_2, ..., e_k)[/itex] that holds the following condition: given that [itex]n_p[/itex], [itex]n_q[/itex], [itex]n_r[/itex], and [itex]n_s[/itex] are nodes belonging to [itex]N[/itex], and [itex]0 < i < k[/itex], if [itex]e_i = (n_p, n_q)[/itex] and [itex]e_{i+1} = (n_r, n_s)[/itex], then [itex]n_q = n_r[/itex]. <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.