Graph Traversal Problem

Traversal of complex data structures concerns browsing trees or graphs. The problem can be stated as the Plan Generation Problem (PGP), regarding graphs.

Let $S$ denote the set of nodes (states), $O$ be the set of arcs (operators), and let $s_{I}$ and $s_{G}$ be the initial state and the desired goal state, respectively. For simplicity of problem statement assume that if two nodes $s_{i}, s_{j}\in S$ are connected directly with and arc $o_{ij}\in O$, there is no other arc connecting these nodes. The simplest mathematical formulation of the Plan Generation Problem is as follows.

A Plan Generation Problem $P$ is the four-tuple:

$$P = (S,O,s_{I},s_{G}),$$

where $s_{I}, s_{G} \in S$ and $O\subseteq S\times S$. A solution to a PGP defined as above is any finite sequence of operators $OP = \langle o_{1}, o_{2},\ldots, o_{n-1} \rangle$, $o_{1}, o_{2},\ldots, o_{n-1}\in O$, such that

$$o_{i}(s_{i}) = s_{i+1},$$ (2.1)

for $i = 1,2,\ldots, n$, where $s_{I} = s_{1}$ and $s_{n} = s_{G}$.

Note that the solution $OP$ defines in a unique way a finite sequence of states $PS = \langle s_{1}, s_{2},\ldots, s_{n} \rangle$, such that $s_{1} = s_{I}$, $s_{1}, s_{2},\ldots, s_{n} \in S$, $s_{n} = s_{G}$. The sequence forms a solution path in the graph. Note that the above problem is indeterministic one - there can be one or more solutions or no solution may satisfy the constraints. Alternatively, one may require to find all such sequences.

A related problem, which is still in C1, is browsing a tree structure. There are the following basic tree analysis problems:

• for a given node $s$ find all its descendant nodes (or a subtree with $s$ being its root node),
• for a given node $s$ find all its antecedents (or a path from $s$ to the root node),
• for a given node $s$ find all leaves of the subtree with $s$ being its root,
• for two given nodes $r$ and $s$ check if $s$ is a descendant of $r$ (if there is a path from $r$ to $s$),
• for all of the above one can specify the depth $n$ creating a class of problems with limited depth of search.

Note that solving the above problems require a Plan Generation Problem solving component.

A tree $T$ is a finite, non-empty set of nodes, partitioned into two disjoint subsets: a single node $r$ and sets that are trees:

$$T = {r} \cup T_1 \cup T_2 \cup \ldots \cup T_n$$ (2.2)

with the following properties:

1. A designated node of the set $r$, is called the root of the tree.
2. The remaining nodes are partitioned into $n \geq 0$ subsets: $T_1, T_2, \ldots T_n$, each of which is a tree.

Let $t$ be a descendant of $k$ in some tree $T={s} \cup T_1 \cup T_2 \cup \ldots \cup T_p$ then:

$$\exists T_q: T_q = {k} \cup T_1 \cup T_2 \cup \ldots \cup T_m \wedge t \in T_1 \cup T_2 \cup \ldots \cup T_m$$ (2.3)

and $T_q \subset T$. In such a case $k$ is called antecedent of $t$.