CODEWITHSUNDEEP
haskell
user1460863
user1460863

Reputation: 31

Haskell - generating all paths between nodes

I need to build a function, which return all paths between certain nodes.

connect :: Int -> Int-> [[(Int,Int)]]

Data.Graph library gives me usefull function 'buildG' which builds graph for me. If I call

let g = buildG (1,5) [(1,2),(2,3),(3,4),(4,5),(2,5)],

I will get an array where every node is mapped to his neighbours. An example:

g!1 = [2]
g!2 = [3,5] 
..
g!5 = []

I was trying to do it using list comprehensions, but I am not very good in haskell and I am getting typing error which I can't repair.

connect x y g 
    | x == y = []
    | otherwise = [(x,z) | z <- (g!x), connect z y g]

I don't need to worry at this moment about cycles. Here is what I want to get:

connect 1 5 g = [[(1,2),(2,3),(3,4),(4,5)],[(1,2),(2,5)]]

Upvotes: 3

Views: 1778

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183888

Think recursively. A path from s to e is composed of a first edge (s,t) and a path from t to e, unless s == e, in which case a path shall be empty. So a first attempt is

connect x y g
    | x == y    = [[]]
    | otherwise = [(x,t):path | t <- g!x, path <- connect t y g]

The list of all eligible paths from a node to itself is the list with the single element [], in the other cases, we obtain the list of all eligible paths by the logic above, pick a first edge and find the paths from its end.

The problem is that cycles will cause it to hang. To avoid that, you have to remember which nodes you already have visited, and not explore paths from that on:

connect x y g = helper x y g [x]
  where
    helper a b g visited
        | a == b    = [[]]
        | otherwise = [(a,c):path | c <- g!a, c `notElem` visited, path <- helper c b g (c:visited)]

Upvotes: 5

Related Questions