Directed graph finding the Node whose input edges are not all reachable from Given node

Question

In a recent interview I was asked below question.

Given a set of nodes and edges with a start Node point to final end node. In the below diagram it starts at 1 ends at 15. Their question was given the Node 2 (or any node) as the starting point how can we find the next node in its path whose input edges are not all reachable from the Node 2 (ie how can we reach 14).

How can I do this, pseudo code should be fine.

Answer 1

i do not see any way to avoid traversing the entire graph at least once (assuming nodes do not have links to parents). if that is ok, then a simple solution based on maps from nodes to the set of immediate parents ('parent map' below) is:

• write a routine that extends a parent map for all nodes below a starting node (using dfs). the routine does not need to explore nodes that are already keys in the map.

• call the routine above for every node in the graph. this gives a complete map from nodes to parents (the transpose of the graph, effectively).

• call the routine above from the given node in the question (eg 2), with a new map. this gives a map from nodes to parents reachable from 2.

• using a bfs from the given node, find the first node where the parents in the two maps differ.

you don't need to store the actual parent nodes in the map (it's just easiest to explain that way); you could do something similar by marking visited nodes and storing a count of the number of parents.

and yet another way of saying this: find the transpose of the graph and the set of nodes reachable from the given node. then bfs from the given node to find the first node where the transpose leads to a parent outside the reachable set. (which really is just the question...)

Answer 2

1. Mark all the edges that are reachable from the start node.
2. Find the first node that is reachable from the start node that has unmarked input edges.

Answer 3

I would say:

1. Find nodes which are unreachable from node 2. Run BFS or any complete algorithm to find set all reachable R. Find unreachable using U = V - R

2. Find All nodes which can be reached from those unreachable nodes, whenever you find a node, you very whether it is in the reachable list of node 2. If it is, you save the edge you just used.

In the second step, you successively pick nodes in U and do a BFS. You treat nodes differently :

• Whenever you find a node X belonging to U which was already picked, you stop
• Whenever you find a node Y belonging to U and not picked, you remove this node from U
• When You find a node in R, you remember the edge and mark this node as "do not visit ever".

Answer 4

• If this algorithm has to do one time lookup then just consider the StartNode:
  • Find all the nodes that are reachable from the Start Node. (By running BFS graph traversal algorithm)
  • Keep this list of nodes which are reachable from StartNode, in a hash table for efficient lookup.
  • For each node which are reachable from the current node (in order):
    • check the incoming nodes (starting vertext of incoming edge)
    • If all the incoming nodes are available in the hash table then move to the next reachable node - else return this node.