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: 139
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