How to find a path in a graph that does not contain nodes from a set?

Question

I have a directed and unweighted graph G = { V, E }.

Additionally, I have a set X which is a subset of the vertices V. This set denotes special forbidden nodes.

I want to find a path from a given source node v to a destination node u but the path must not contain any of the forbidden nodes in X.

How can I find such a path but avoid the nodes at the same time?

edit : this is my final solution

    def notPassTroughX(G: Graph, X: list, u: Node, v: Node):
    
        for x in X:
            x.set_color(color.black)

        return not G.bfs(u, v) and G.bfs(u, v)

Answer 1

Ignore nodes in X

Grab your favorite path-finding algorithm and simply ignore any node in X.

Since you tagged with "depth-first-search" let us take a look at that algorithm (pseudocode taken from Wikipedia):

let S be a stack
S.push(v)
while S is not empty do
    v = S.pop()
    if v is not labeled as discovered then
        label v as discovered
        for all edges from v to w in G.adjacentEdges(v) do
            S.push(w)

All you have to do is to modify the edge relaxation step, which is

for all edges from v to w in G.adjacentEdges(v) do

Simply ignore any edge that leads to a node in X, so:

for all edges from v to w in G.adjacentEdges(v) where w is not in X do

That is all you have to do.

---

Reference implementation

Here is an implementation in Java:

Node source = ...
Set<Node> nodesToIgnore = ...

Queue<Node> nodesToProcess = Collections.asLifoQueue(new ArrayDeque<>());
nodesToProcess.add(source); // add all starting nodes

Set<Queue> visitedNodes = new HashSet<>();
while (!nodesToProcess.isEmpty()) {
    // Settle node
    Node currentNode = nodesToProcess.poll();
    if (!visitedNodes.add(currentNode)) {
        continue; // Already visited before
    }
    
    // Do something with the node
    System.out.println(currentNode); // Replace by whatever you need
    
    // Relax all outgoing edges
    for (Node neighbor : currentNode.getNeighbors()) {
        if (nodesToIgnore.contains(neighbor)) {
            continue;
        }
        nodesToProcess.add(neighbor);
    }
}

---

Stop when destination reached

The regular DFS algorithm explores the full graph. A simple modification can be done to stop it as soon as the destionation has been reached.

For that, just break the loop once you settled the destination:

// change this
v = S.pop()
// to
v = S.pop()
if (v == destination) {
    break;
}

In the Java code, that is:

Node destination = ...
...
while (!nodesToProcess.isEmpty()) {
    // Settle node
    Node currentNode = nodesToProcess.poll();
    if (currentNode == destination) {
        break;
    }
    ...
}

---

Path building

Constructing the final path is usually done via backtracking. Therefore, you simply have to remember for each node from where you came. For example by giving them a parent field or similar. Then you construct the path by reversly following them from destination back to source.

...
while (!nodesToProcess.isEmpty()) {
    ...
    // Relax all outgoing edges
    for (Node neighbor : currentNode.getNeighbors()) {
        if (nodesToIgnore.contains(neighbor)) {
            continue;
        }

        neighbor.parent = currentNode; // remember parent
        nodesToProcess.add(neighbor);
    }
}

// Construct path by backtracking
List<Node> path = new ArrayList<>();
Node currentNode = destination;
while (currentNode != null) {
    path.add(currentNode);
    currentNode = currentNode.parent;
}

Collections.reverse(path);

---

Full code

Node source = ...
Node destination = ...
Set<Node> nodesToIgnore = ...

Queue<Node> nodesToProcess = Collections.asLifoQueue(new ArrayDeque<>());
nodesToProcess.add(source); // add all starting nodes

Set<Queue> visitedNodes = new HashSet<>();
while (!nodesToProcess.isEmpty()) {
    // Settle node
    Node currentNode = nodesToProcess.poll();
    if (currentNode == destination) {
        break;
    }
    if (!visitedNodes.add(currentNode)) {
        continue; // Already visited before
    }
    
    // Relax all outgoing edges
    for (Node neighbor : currentNode.getNeighbors()) {
        if (nodesToIgnore.contains(neighbor)) {
            continue;
        }

        neighbor.parent = currentNode; // remember parent
        nodesToProcess.add(neighbor);
    }
}

// Construct path by backtracking
List<Node> path = new ArrayList<>();
Node currentNode = destination;
while (currentNode != null) {
    path.add(currentNode);
    currentNode = currentNode.parent;
}

Collections.reverse(path);