Haskell - generating all paths between nodes

Posted by user1460863 on Stack Overflow See other posts from Stack Overflow or by user1460863
Published on 2012-06-23T09:07:40Z Indexed on 2012/06/23 9:16 UTC
Read the original article Hit count: 106

Filed under:
|
|
|

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)]]

© Stack Overflow or respective owner

Related posts about haskell

Related posts about path