Route Between Nodes



In [1]:

    
import qualified Data.Graph as G
import qualified Data.Array as A
import qualified Data.Sequence as S
import qualified Data.IntSet as I



In [2]:

    
path :: G.Graph -> G.Vertex -> G.Vertex -> Bool
path g src dst
    | src == dst = True
    | otherwise = dfs (I.singleton src) (S.singleton src)
    where
        dfs :: I.IntSet -> S.Seq G.Vertex -> Bool
        dfs seen queue
            | S.null queue = False
            | dst `elem` unseen = True
            | otherwise = dfs seen' queue'
            where
                (current, remaining) = (S.index queue 0, S.drop 1 queue)
                unseen = filter (`I.notMember` seen) $ g A.! current
                seen' = seen `I.union` I.fromList unseen
                queue' = remaining S.>< S.fromList unseen

Tests



In [3]:

    
import Test.QuickCheck



In [4]:

    
testPath :: [(G.Vertex, G.Vertex)] -> Bool
testPath [] = path g single single == G.path g single single
    where
        single = 1
        g = G.buildG (single, single) []
testPath edges = and [ path g x y == G.path g x y | x <- G.vertices g, y <- G.vertices g]
    where
        bounds = (minimum (map (uncurry min) edges), maximum (map (uncurry max) edges))
        g = G.buildG bounds edges



In [5]:

    
quickCheck testPath









    





+++ OK, passed 100 tests.