What algorithm will visit each node in a graph a number of times equal to the number of paths to that node from the root?

Question

First Few Iterations of the Algorithm

We have an algorithm in which a squirrel visits the nodes of a directed graph.

Our graph has two colors of edges: black and white.

Initially, the graph has black edges only, and no white edges.

The squirrel never changes the color of an edge from black to white. The squirrel simply inserts an additional white edge from time-to-time, or the squirrel deletes a white edge.

Between node $x$ and node $y$ we can have:

• no edges (no black and no white)
• one black edge from $x$ to $y$, but no white edges.
• one black edge from $y$ to $x$, but no white edges.
• two black edges going in both directions, but no white edges.
• one black edge from $x$ to $y$ and a white edge running in parallel
• one black edge from $x$ to $y$ and one white edge in the opposite direction
• one black edge from $y$ to $x$ and a white edge running in parallel
• one black edge from $y$ to $x$ and one white edge in the opposite direction
• two black edges going in both directions, and one white edge going one of the two directions.

There is always zero or one white-edge between two nodes, but never two white edges going in opposite directions.

No matter what iteration of the algorithm we are on, white edges always describe a path beginning at the root node where no nodes are repeated on that path.

Our squirrel begins at the root node. The squirrel will always be stationed at one of the graph's nodes.

We move the squirrel node-by-node to trace an arbitrary path beginning at the root node.

With each step, the squirrel draws a white arc from the node it came from to the most recently visited node.

Initially, our algorithm looks like depth-first search, but it will change later.

The squirrel continues along the path until the squirrel can go no further.

The squirrel can go no further because all successors of the node which the squirrel stops at are already on the squirrel's path. That is, all successors of the current node are the root node or have a white edge going into them.

At this point, the graph contains exactly one white path.

The graph will always have just one white path.

As this point, we order the squirrel to back-trace a short ways, deleting white edges as it goes.

At all times, the graph must contain exactly one white path.

We re-visit the same vertex many times. In particular, we should leaf-ward visit node $x$ the same number of times as the number of paths from the root to node $x$.

Leaf-ward visits occur when lengthening the white-path, not shortening the white-path. Shortening the white path is known as back-tracking or a backtrace.

This is not canonical depth-first search of a graph because we do visit the same node many times.

We cannot visit a node if that node is already in the "active" (white) path.

I am stuck (not sure what to do) after the first deep path is constructed.

Maze Analogy

Suppose you had a maze with a single starting point. I asked you for an algorithm which would provide me with the $(x, y)$ coordinates of every dead-end in the maze.

One is tempted to use something like depth-first search.

There are some complications:

• the maze represents an arbitrary graph, not a tree. Our maze contains cycles.
• I require that each dead-end in the maze be visited a number of times equal to the number of distinct paths to that dead-end from the beginning of the maze.

Question about an Algorithm

Can you describe an algorithm which:

• accepts a rooted directed graph $G$ as input.
• returns a container (such as a set, array, or linked list) which contains every “pseudo-sink” of the input graph.
• Initially, all nodes are painted zero times. If $k$ is the number of paths from the root node to node $x$, then $x$ gets painted by the algorithm (visited) exactly $k$ times before the algorithm returns.

We will eventually provide a mathematically formal definition of a “pseudo-sink”.

Informally, a node is a “pseudo-sink” if there exists a path going to that node which cannot go any further without repeating a node previously seen on the path.

Example

Here is a picture of a rooted graph.

The black node is the root-node.
The white nodes are pseudo-sinks.
Grey nodes are not pseudo-sinks and are not the root node either.

Definitions

Definition of “rooted”

A rooted digraph is a digraph which has exactly one of its vertices designated as a special “root node”.

Definition of “Pseudo-Sink”

For any rooted directed graph $G$, and any node $z$ in digraph $G$, we say that $z$ is a “pseudo-sink” in digraph $G$ if and only if node $z$ is the end of a maximally long path originating at the root of digraph $G$.

Definition of maximally long

For any directed graph $G$, for any node $x$ in $G$, and for any path $P$ in graph $G$ ending at node $x$, we say that $P$ is a “maximally long” in graph $G$ if and only if for any node $y$ in digraph $G$, if $(x, y)$ is an edge in digraph $G$, then $y$ is a node in path $P$.

Definition of path: In the definition given above, a path is not allowed repeat any vertices. Also, a path's first node may not be the same as the last node in the same path.

Definition of digraph

Note that we allow $G$ to have self-loops $\begin{pmatrix}(x,x)\in AS \end{pmatrix}$.
An example of a digraph might have:

• $VS(G) =\begin{Bmatrix} 1, 2, 3, 4 \end{Bmatrix}$
• $AS(G) =\begin{Bmatrix} (1, 2), (2, 3), (2, 4), (4, 4), (3, 2), (3, 3)\end{Bmatrix}$

Alternative definition of Pseudo-Sink

Let $G$ be a directed graph. Let $r_{G}$ be the designated root node in digraph $G$.

A Pseudo-Sink of digraph $G$ is any leaf-node of the “Path Tree” rooted at node $r_{G}$ in directed graph $G$.

Definition of Path: Suppose for a moment that for any “path” $P$ in graph $G$ there exists $m \in \mathbb{N}$ such that $P$ is a mapping from the set $\begin{Bmatrix} n \in \mathbb{N} \cup \{0\} : n \leq m \end{Bmatrix}$ to the vertices of graph $G$ such that $\forall a, b \in \begin{Bmatrix} n \in \mathbb{N} \cup \{0\} : n \leq m \end{Bmatrix}, b = a + 1 \implies \begin{pmatrix} P[a], P[b] \end{pmatrix} \in AS(G), \text{ and } a \neq b \implies P[a] \neq P[b]$

A “Path Tree” of digraph $G$ rooted at node $r _{G} \in G$ is defined to be a tree $T$ such that there exists a mapping $\mathcal{toG}$ from the vertex set of the tree $\begin{pmatrix} VS(T) \end{pmatrix}$ to the vertex set of the graph $VS(G)$ such that all of the following are true:

• There exists a unique tree-node $r_{T}$ such that $\mathcal{toG}(r_{T}) = r_{G}$
• For any tree-path $P_{T}$, there exist a path $P_{G}$ in graph $G$ such that $\forall k \in \mathtt{domain}(P_{T}), \mathcal{toG} \begin{pmatrix} P_{T}(k)\end{pmatrix} = P_{G}(k)$
• For any path $P_{G}$ in graph $G$, there exists a path $P_{T}$ in tree $T$ such that $\forall k \in \mathtt{domain}(P_{T}), \mathcal{toG} \begin{pmatrix} P_{T}(k)\end{pmatrix} = P_{G}(k)$
• If there are two tree-paths $P_{T}$ and ${P^{\prime}}_{T}$ and there exists a path $P_{G}$ in graph $G$ such that $\forall k \in \mathtt{domain}(P_{T}), \mathcal{toG} \begin{pmatrix} P_{T}(k)\end{pmatrix} = P_{G}(k)$ and $\forall k \in \mathtt{domain}({P^{\prime}}_{T}), \mathcal{toG} \begin{pmatrix} {P^{\prime}}_{T}(k)\end{pmatrix} = P_{G}(k)$ then $P_{T} = {P^{\prime}}_{T}$
• if there are two graph paths corresponding to the same tree path then the two graph paths are equal to each-other.

Notation for Pseudo-Code

In pseudo-code, for any object x and function f feel free to assume that both of the following are equivalent:

result = x.f(y, z)
result = f(x, y, z)

• The vertex set of a graph is denoted as $\mathtt{VS}(\mathtt{G})$ and also written as $\mathtt{G}. \mathtt{VS}()$

• We can assume that the following array-like function named $\mathtt{KIDS}$ is included as part of the input graph $G$:

$\mathtt{KIDS}(\mathtt{Knode} \text{ } \mathtt{vert})$: returns an ordered container to the children of node $\mathtt{vert}$.
As some example pseudo-code, we might write the following:

for KID in KIDS  {
    print(KID)
}

for V in G.VS() {
    print(V)
}

for V in VS(G) {
    print(V)
}

The input to our algorithm is not necessarily a tree object. However, we may wish to build a tree as an intermediate step.

• For an ordered tree, $\mathtt{PARENT}(\mathtt{TreeKnode} \text{ } \mathtt{vert})$: returns the parent of node vert or NULL.

• For an ordered tree, $\mathtt{SIB}(\mathtt{TreeKnode} \text{ } \mathtt{vert})$ returns the eldest sibling of node vert. If there is no sibling, then it returns $\mathtt{NULL}$ .

• $\mathtt{SIB}(\mathtt{Knode} \text{ } \mathtt{vert}, \mathtt{int} \text{ } \mathtt{dist})$
  • returns $\mathtt{SIB}(\mathtt{vert})$ if $\mathtt{dist} == 0$.
  • For $\mathtt{d} \in \begin{Bmatrix} n \in \mathbb{N}: n \geq 1 \end{Bmatrix}$, it returns $\mathtt{SIB}(\mathtt{vert}, \mathtt{d} - 1)$

Answer 1

Here is a recursive algorithm, written in Python. For simplicity, assume vertices are $0,\cdots, n-1$.

The idea is basically the same as that of the usual depth first search. At each recursive call, the algorithm will explore all paths that starts from the current source node without revisiting any visited nodes. However, when it back-traces from a visited node, it will consider that node as unvisited. This extension of unvisited nodes enables the algorithm to traverse all paths without using exponential working memory.

A squirrel can search a graph/maze by following procedure complete_dfs recursively.

• Upon entering the procedure given a pair of visited_nodes and source, the squirrel will find and remember kids to be explored.
• At visited_nodes.add(kid), the squirrel will move leaf-ward from source to kid, entering the next level of the procedure with updated visited_nodes and kid as the new source.
• At visited_nodes.remove(kid), the squirrel will back-trace from kid to source, since kid is considered as having been explored for the updated set of visited nodes.

By the way, pseudo-sink and maximally long path can also be defined in an undirected graph. Replacing kids by neighbors, the same algorithm can find pseudo-sinks and numbers of paths of an undirected graph with respect to a source node as well.

def compute_pseudo_sinks(n: int, root: int, kids: list[list]) -> set:
    """ kids is a rooted directed graph with nodes 0, ..., n-1
        kids[u] is the list of kids of node u
        Return the set of all pseudo-sinks.
    """

    pseudo_sinks = set()
    painted_times = [0] * n  # painted_times[i] will be the number of paths from root to node i

    def complete_dfs(visited_nodes: set, source: int):
        """ visited_nodes is the set of nodes in a path from the root
            Explore all paths that start from source avoiding visited_nodes
        """
        is_pseudo_sink = True
        for kid in kids[source]:
            if kid not in visited_nodes:
                is_pseudo_sink = False
                visited_nodes.add(kid)
                painted_times[kid] += 1
                complete_dfs(visited_nodes, kid)
                visited_nodes.remove(kid)
        if is_pseudo_sink:
            pseudo_sinks.add(source)

    painted_times[root] = 1
    complete_dfs({root}, root)
    return pseudo_sinks  # , painted_times


# an example
n, r, kids = 5, 0, [[1], [2, 3], [1, 2, 3], [2], [3]]
ps = compute_pseudo_sinks(n, r, kids)
print("pseudo-sinks:", ps)  # pseudo-sinks: {2, 3}