Graph Traversal

Question

There are three types of nodes in my graph, red, blue, and black. For each red node I want to find a path to one black node (in whatever time). On the way, I cannot pass through another red node. How can I find all red nodes where there is a path to a black node that satisfies the above condition?

Answer 1

Now this depends on how your data structures are represented in some ways, but I would use the following algorithm. (To find all the paths at once)

Each node should be augmented with a variable which will store an edge to follow backwards to get to a black node.

Start with the set of black nodes. Make a queue containing all edges connected to them (store the edges as directed edges with the end being the black node).

Then for each edge in the queue check the start node of the edge. If the start node has been processed already, discard the edge. Otherwise check the color of the start node of the edge. If it is red, store the edge in the red node and add it to the set of processed vertices. If the node is blue store the edge in the node, add the blue node to the set of processed vertices and then add all other edges adjacent to the blue node (except for those connecting to processed vertices) to the queue (with their end node being set to our blue node). The start node of edges in the queue can never be black since we already processed all the black nodes, so if it were we would have discarded the edge at the start of the loop.

If you want to know if every red node has a path to a black node then also maintain a set of unprocessed nodes. If there remain nodes in this set after the queue of edges to check is empty, these nodes cannot reach a black node without traveling through a red node. Iterate through this set to see if there are any red nodes in the set.

At the end, we'll end up with a set of processed vertices, and the nodes in this set each store an edge that points you along a path (that doesn't go through red nodes) that ends at a black node.

If we use hash sets, this should be $O(E)$ I think since each edge is processed at most once. Well $O(V)+O(E)$ for sparse graphs, but for connected graphs $V$ is $O(E)$.

Edit:

Proof of correctness. By which I mean a proof of the following fact. A red vertex is in the set of processed vertices at the end of the algorithm if and only if there exists a path from the red vertex to a black vertex passing through only blue vertices.

Proof: We prove instead the equivalent statement: The set of processed vertices at the end of the algorithm is precisely the set of vertices with a path to a black vertex that doesn't pass through a red vertex.

First we show inductively that the set of processed vertices is a subset of the set of vertices with such a path. The initial set of processed vertices is the set of black vertices. Trivially these all have a path to a black vertex not passing through a red vertex, so the condition is true to start with. Then at each stage of the loop we consider an edge $(s,e)$ with $e$ already in the set of processed vertices (assume $s$ is unprocessed, since otherwise we discard the edge without changing the set of processed vertices). Hence there is a path from $e$ to a black vertex not passing through a red vertex. Moreover, we never add directed edges with a red target vertex to the queue since we only add edges whose targets are black or blue. Thus $e$ is not red. Hence adding the edge $s\to e$ to the path from $e$ to a black vertex that doesn't pass through a red vertex gives a path from $s$ to a black vertex not passing through a red vertex. Thus adding $s$ to the set of processed vertices preserves the property that all vertices in the set of processed vertices have a path to a black vertex not passing through a red vertex.

Conversely if a vertex $v$ has a path to a black vertex not passing through red vertices, define $d(v)$ to be the length of the shortest such path. We'll prove by induction on $d(v)$ that $v$ is processed at some point in the algorithm. If $d(v)=0$ $v$ is black, and it is processed at the beginning of the algorithm. Otherwise $d(v) > 0$, so let $w$ be the next vertex along the minimal length path from $v$ to a black vertex. Clearly $d(w)=d(v)-1$, so by our induction hypothesis $w$ is processed at some point in the algorithm. Since $w$ is not red when it was processed all of its (previously unprocessed) adjacent edges are added to the queue of edges to be processed. Thus the edge $v\to w$ is added to the queue when $w$ is processed, and therefore $v$ will be processed at some point (either when we come to the edge $v\to w$ or perhaps before that, but either way $v$ must be processed). Thus the induction holds. This completes the other half of the proof of our assertion. $\blacksquare$

It is also true that by following the edges stored at a vertex you will get a path to a black vertex not passing through a red vertex, but the proof of correctness is similar to the proof above, so I won't repeat myself.