Haskell - generating all paths between nodes

Question

I need to build a function that returns all paths between specific nodes.

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

The Data.Graph library gives me a useful buildG function that builds a 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 each node maps to neighbors. Example:

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

I tried to do this using lists, but I'm not very good at haskell, and I am getting an input error that I cannot fix.

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

I do not need to worry about cycles at this point. Here is what I want to get:

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

Answer 1

Think recursively. The path from s to e consists of the first edge (s,t) and the path from t to e , if only s == e , in which case the path should be empty. So the first attempt is

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

The list of all valid paths from node for ourselves is a list with a single element [] , in other cases, we get a list of all valid paths according to the logic above, select the first edge and find the paths from its end.

The problem is that the cycles will make it hang. To avoid this, you must remember which nodes you have already visited, and not study the paths from this:

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