Learn more about Russian war crimes in Ukraine.

Is there a route between these two nodes in this directed graph?

Question 4.2 of Cracking the Coding Interview:

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Given any node in the graph, we can generate a full list of nodes reachable from that node, by exploring the graph from that node outwards. We can then determine whether a route exists from node n1 to node n2 by generating the full list of nodes reachable from n1, and asking whether n2 is in that list.

To generate the “reachable set” from a node, we partition the graph into three sets: explored nodes, boundary nodes, and the rest. We repeatedly look for new nodes by looking at outgoing edges from nodes in the boundary set. When we’ve looked at all the outgoing edges of a node, we move that node to explored so we don’t look at its edges again. Eventually, our boundary set becomes empty, there are no new nodes to explore, and the explored set is all the reachable nodes.

Here’s an implementation in Haskell:

module DirectedGraphRoute where

import qualified Data.Set as Set
import Data.Set (Set)

type Node = Int
type Edge = (Node,Node)
type Graph = Set Edge

isRoute :: Graph -> Node -> Node -> Bool
isRoute g n1 n2 = Set.member n2 $ reachableSet g n1

reachableSet :: Graph -> Node -> Set Node
reachableSet g n = go Set.empty (Set.singleton n) where
  go explored boundary
    | Set.null boundary = explored
    | otherwise = go newExplored $ Set.fromList [ t | 
                    (f,t) <- Set.toList g, 
                    Set.member f boundary, 
                    not (Set.member t newExplored)
                  where newExplored = Set.union explored boundary

One optimization could be to stop as soon as we find n2 while exploring. Another optimization could be to expand from n1 and n2 concurrently (exploring edges in the reverse direction from n2), and stopping as soon as the explored sets overlap.

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only $19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s $29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

More by Jim

Tagged #ctci, #programming, #haskell. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.