\section{Algorithm for obtaining \texorpdfstring{$r$}{r}-stage adjacency matrices}
\label{sec: r-stage adjacency}
Here we present a dynamic programming algorithm for computing \mbox{$r$-stage} adjacency matrices using a static network. We begin by showing how we can use previous stage neighbours to find subsequent ones. We use the following notions. 
\begin{definition} \label{def: neighbourhood distance}
Let $i$ and $j$ be two nodes in the graph $\mathcal{G}$, and let $\mathcal{N}_r (i)$ denote the set of \mbox{$r$-stage} neighbours of node $i$. We define the distance between a node $j \in \mathcal{K}$ and the set $\mathcal{N}_r (i)$ as 
\begin{equation*}
    \delta \{j, \mathcal{N}_r (i) \} := \min_{k \in \mathcal{N}_r (i)} \big \{ \delta (j, k) \big \} . 
\end{equation*}
\end{definition}
Note that since the graph is finite, every non-empty set of \mbox{$r$-stage} neighbours is finite so the minimum above is well defined. Also, by definition of \mbox{$r$-stage} adjacency we have that $\delta \{i, \mathcal{N}_r (i) \} = r$ for all $i \in \mathcal{K}$. If a node is disconnected from the graph, then we use the convention that its distance to any other node is infinite, i.e., if $i$ has no one-stage neighbours, then $\delta \{j, \mathcal{N}_r (i) \} = +\infty$ for all nodes $j \neq i$, and $r = 1, \dots, r_{\max}$. Thus, said node has no \mbox{$r$-stage} neighbours.
\begin{proposition} \label{prop: rstage one}
Let $\mathcal{G} = (\mathcal{K}, \mathcal{E})$ be a finite undirected simple graph (i.e., undirected edges with no self-loops). Assume that the shortest path between nodes $i$ and $j$ has a distance larger than $r \in \mathbb{N}$ (i.e., $\delta(i, j) > r$). Then,
\begin{equation*}
    \delta(i, j) = \delta \{j, \mathcal{N}_r (i) \} + \delta \{i, \mathcal{N}_r (i) \} .
\end{equation*}
\end{proposition}
\begin{proof}
Since $\delta(i, j) > r$ we know that $j \notin \mathcal{N}_s (i)$ for $s \in \{1, \dots, r\}$. Thus, the shortest path between $i$ and $j$ is longer than the paths between $i$ and any of its \mbox{$r$-stage} neighbours, thus, for all $k \in \mathcal{N}_r (i)$ we have that
\begin{equation*}
    \delta(i, j) > \delta(i, k). 
\end{equation*}
Now any path from $i$ to $j$ must pass through one \mbox{$r$-stage} neighbour, otherwise, we would have that $j \in \mathcal{N}_s (i)$ for some $s \in \{1, \cdots, r - 1\}$ and get the contradiction $\delta(i, j) < r$. In other words, since the shortest path to node $j$ takes at least $(r + 1)$ steps it must pass through one of the \mbox{$r$-stage} neighbours. Hence, all paths between $i$ and $j$ that do not cycle and/or reverse direction pass through at least one of the \mbox{$r$-stage} neighbours of node $i$. The length of these paths is
\begin{equation*}
    \delta(i, k) + \delta (j, k) = r + \delta (j, k) \geq r + \delta \{j, \mathcal{N}_r (i) \},
\end{equation*}
for all $k \in \mathcal{N}_r (i)$. Thus, the shortest path between $i$ and $j$ is the one we get by connecting the path between the closest \mbox{$r$-stage} neighbour of node $i$ to node $j$ with node $i$, otherwise, the path connecting the set $\mathcal{N}_r (i)$ with $j$ would have a smaller distance than the shortest path between $i$ and $j$ if $j \notin \mathcal{N}_s (i)$ for $s \in \{1, \dots, r\}$, which is a contradiction. Thus, we have that
\begin{equation*}
    \delta(i, j) = \delta \{i, \mathcal{N}_r (i) \} + \delta \{j, \mathcal{N}_r (i) \} .
\end{equation*}
\end{proof}
Informally, the proof above exploits the "nested" structure of \mbox{$r$-stage} neighbourhood sets. If we represent a node $i$ as the centre of a ball and identify all of its \mbox{1-stage} neighbours as points inside the circle with radius one centred at $i$, then as we increase the radius to $r$ we connect node $i$ to its \mbox{$r$-stage} neighbours. Each set of \mbox{$r$-stage} neighbours corresponds to the nodes that fall inside the area between the circle with radius $r$ and the circle with radius $(r - 1)$.
\par
We are interested in computing the \mbox{$r$-stage} set of neighbours sequentially, to do so we make use of Proposition \ref{prop: rstage one} and Proposition \ref{prop: rstage two} below.
\begin{proposition} \label{prop: rstage two}
    Let $i$ and $j$ be two nodes in the graph $\mathcal{G}$. Assume that $j \notin \mathcal{N}_s (i)$ for $s \in \{1, \dots, r - 1\}$, then node $j$ is an \mbox{$r$-stage} neighbour of node $i$ if and only if there exists a node $k$ such that $k$ is a \mbox{$1$-stage} neighbour of node $j$ and a \mbox{$(r - 1)$-stage} neighbour of node $i$. In essence, if $j \notin  \bigcup_{q = 1}^{r - 1} \mathcal{N}_{q} (i)$, then
    \begin{equation*}
        j \in \mathcal{N}_r (i) \iff \exists k \in \mathcal{N}_1 (j) \cap \mathcal{N}_{r - 1} (i) .
    \end{equation*}
\end{proposition}
\begin{proof}
    ($\Rightarrow$),
    we begin with the if part. 
    If node $j \in \mathcal{N}_r (i)$, then 
    \begin{align*}
        \delta (i, j) &= r \\
        &= r - 1 + 1 \\
        &= \delta \{i, \mathcal{N}_{r - 1} (i) \}  + 1 .
    \end{align*}
Now, by Proposition \ref{prop: rstage one}, we have that
\begin{equation*}
    \delta \{i, \mathcal{N}_{r - 1} (i) \}  + 1 = \delta \{i, \mathcal{N}_{r - 1} (i) \}  +  \delta \{j, \mathcal{N}_{r - 1} (i) \}.
\end{equation*}
So $\delta \{j, \mathcal{N}_{r - 1} (i) \} = 1$. Thus, there exists at least one $k \in \mathcal{N}_{r - 1} (i)$ such that $\delta (j, k) = 1$, hence, $k \in \mathcal{N}_1 (j) \cap \mathcal{N}_{r - 1} (i)$. 
\newline
($\Leftarrow$), we proceed with the only if. 
Let $k \in \mathcal{N}_1 (j) \cap \mathcal{N}_{r - 1} (i)$. Then, 
\begin{align*}
    \delta(i, k) &= r - 1 , \\
    \delta (j, k) &= 1 .
\end{align*}
By assumption $\delta \{j, \mathcal{N}_{r - 1} (i) \} \geq 1$, thus, 
\begin{equation*}
    \delta \{j, \mathcal{N}_{r - 1} (i) \} = \delta (j, k) = 1,
\end{equation*}
and, using Proposition \ref{prop: rstage one}, we have that
\begin{align*}
    \delta (i, j) &= \delta \{i, \mathcal{N}_{r - 1} (i) \}  +  \delta \{j, \mathcal{N}_{r - 1} (i) \} \\
    &= r - 1 + 1 \\
    &= r .
\end{align*}
Therefore, $j$ is a \mbox{$r$-stage} neighbour of node $i$, i.e., $j \in \mathcal{N}_r (i)$.
\end{proof}
%Connect these propositions to the adjacency matrices and set up the algos
Recall that if $\delta (i, j) = r$, then $j \in \mathcal{N}_r(i)$ and $i \in \mathcal{N}_{r}(j)$. Also, by Proposition \ref{prop: rstage two}, we can find \mbox{$r$-stage} neighbours by checking the set $\mathcal{N}_{r -1} (\cdot)$ of \mbox{$(r-1)$-stage} neighbours. We use the following subroutines to find all \mbox{$q$-stage} adjacency matrices for $q \in \{1, \dots, r\}$. 
\begin{algorithm}[H]
\caption{Check if $i$ and $j$ are $r$-stage neighbours}
\label{alg: base routine}
\begin{algorithmic}[1] 
\Require $j \notin \mathcal{N}_q (i)$ for all $q \in \{1, \dots, r - 1\}$
\Procedure{\mbox{$r$-stage-adjacent} }{$\bmat{S}_{r - 1}, \bmat{S}_1, i, j$}
\State $\text{out} \gets \text{FALSE} $
\For{$k \in \{1, \dots, |\mathcal{K}| \}$}
\If{$[\bmat{S}_1]_{jk} = 1$} \Comment{Check if $k \in \mathcal{N}_{1} (j)$}
    \If{$[\bmat{S}_{r - 1}]_{ik} = 1$} \Comment{Check if $k \in \mathcal{N}_{r - 1} (i)$}
        \State $\text{out} \gets \text{TRUE} $  \Comment{By Proposition \ref{prop: rstage two}, $j \in \mathcal{N}_r (i)$}
        \State \textbf{break}
    \EndIf
\EndIf
\EndFor
\State \textbf{return:} out
\EndProcedure
\end{algorithmic}
\end{algorithm}
Algorithm \ref{alg: base routine} computes whether or not $i$ and $j$ are \mbox{$r$-stage} neighbours if $j \notin \mathcal{N}_q (i)$ for $q \in \{1, \dots, r - 1\}$. To keep track of this condition we use the connection matrix $\bmat{C}$ which has entries $[\bmat{C}]_{ij} = 1$ if $j \in  \bigcup_{q = 1}^{r - 1} \mathcal{N}_{q} (i) $, otherwise, $[\bmat{C}]_{ij} = 0$ (i.e., $[\bmat{C}]_{ij} = 1$ if the distance between nodes $i$ and $j$ is less than or equal to $r -1$). Note that if $\mathcal{G}$ is connected, then there exists $r \in \mathbb{N}$ such that all off-diagonal entries in $\bmat{C}$ are equal to one. Hence, $\bmat{C}$ keeps track of previous stage neighbours when computing \mbox{$r$-stage} neighbours sequentially, and we have that 
\begin{equation*}
    \sum_{j = 1}^{|\mathcal{K}|} [\bmat{C}]_{ij} = \left | \bigcup_{q = 1}^{r - 1} \mathcal{N}_{q} (i) \right |,
\end{equation*}
for all nodes $i \in \mathcal{K}$. The following algorithm computes $\bmat{S}_r$ as a function of {$\bmat{S}_{r - 1}, \bmat{S}_1$ and $\bmat{C}$.
\begin{algorithm}[H]
\caption{Compute the \mbox{$r$-stage} adjacency matrix}
\label{alg: second routine}
\begin{algorithmic}[1]
\Procedure{\mbox{$r$-stage-matrix} }{$\bmat{S}_{r - 1}, \bmat{S}_1, \bmat{C}$}
\State $\bmat{S}_r \gets \bmat{0}$
\For{$i \in \{1, \cdots, |\mathcal{K}| - 1 \}$}
    \For{$j \in \{i, \cdots, |\mathcal{K}| \}$}
        \If{$[\bmat{C}]_{ij} = 0$} \Comment{Check that $j \notin \bigcup_{q = 1}^{r - 1} \mathcal{N}_{q} (i)$}
            \If{\mbox{$r$-STAGE-ADJACENT}($\bmat{S}_{r - 1}, \bmat{S}_1, i, j$) }
                \State $[\bmat{S}_r]_{ij} \gets 1$
                \State $[\bmat{S}_r]_{ji} \gets 1$
                \State $[\bmat{C}]_{ij} \gets 1$
                \State $[\bmat{C}]_{ji} \gets 1$
            \EndIf
        \EndIf
    \EndFor
\EndFor
\State \textbf{return:} $\bmat{S}_r$, $\bmat{C}$
\EndProcedure
\end{algorithmic}
\end{algorithm}
Finally, Algorithm \ref{alg: global routine} computes all $\bmat{S}_q$ for $q \in \{1, \cdots, r \}$ starting from \mbox{$1$-stage} neighbours.
\begin{algorithm}[H]
\caption{Compute the \mbox{$q$-stage} adjacency matrices for $q \in \{1, \dots, r \}$}
\label{alg: global routine}
\begin{algorithmic}[1]
\Procedure{\mbox{$(1:r)$-stage-matrices} }{$\bmat{S}_1, r$}
\State $\bmat{C} \gets \bmat{S}_1$
\If{$r = 1$}
    \State \textbf{return:} $\big \{ \bmat{S}_1 \big \} $
\Else
\For{$q \in \{2, \dots, r\}$}
    \State $\bmat{S}_q$, $\bmat{C} \gets$ \mbox{$r$-STAGE-MATRIX} ($\bmat{S}_{q - 1}, \bmat{S}_1, \bmat{C}$)
\EndFor
\EndIf
\State \textbf{return:} $\big \{ \bmat{S}_1, \dots, \bmat{S}_r \big \}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

The worst case scenario performs $O(|\mathcal{K}|)$ operations for Algorithm \ref{alg: base routine}, which are required for each of the steps in Algorithm's \ref{alg: second routine} loop which has complexity $O(|\mathcal{K}|^2)$, and Algorithm \ref{alg: global routine} performs $r$ instances of Algorithm \ref{alg: second routine}, thus, Algorithm \ref{alg: global routine} has a complexity $O(r |\mathcal{K}|^3)$.