Directed separation

gistfile1.hs

import qualified Data.Array as A
import Data.Tuple (swap)
import Data.List (nub, (\\))
import Data.Graph

type Path = [Vertex]
type Givens = [Vertex]

adjacent :: Graph -> Vertex -> [Vertex]
adjacent = (A.!)
        
findAllPaths' :: Graph -> Vertex -> Vertex -> Path -> [Path]
findAllPaths' g a b visited
  | a == b    = [visited]
  | otherwise = concat $ map (\v->findAllPaths' g v b (v:visited)) vs
  where vsV = adjacent g a \\ visited -- Don't permit multiple visits of vertices
        vsE = map snd $ filter (\(x,y)->x==a) $ edges g \\ pathEdges (reverse visited) -- Don't permit multiple visits of edges
        vs = vsE

     
findAllPaths :: Graph -> Vertex -> Vertex -> [Path]
findAllPaths g a b = findAllPaths' g a b [a]

pathEdges :: Path -> [Edge]
pathEdges (a:[]) = []
pathEdges (a:b:c) = (a,b) : pathEdges (b:c)
                    
isPathDSep :: Graph -> Givens -> Path -> Bool
isPathDSep g obs p =
  undefined

dSep :: Graph -> Givens -> Vertex -> Vertex -> Bool
dSep g obs a b = 
  not $ null $ filter (isPathDSep g obs) $ findAllPaths g a b
    
graph = buildUndirG (1,8)
        [ (1,2), (2,3), (3,4), (4,1)
        , (8,1), (3,5), (3,6), (6,7) ]

buildUndirG :: Bounds -> [Edge] -> Graph
buildUndirG bounds edges = buildG bounds $ nub $ edges ++ map swap edges
        
main = do
  print $ findAllPaths graph 4 7