Graph representation in Haskell

Question

Hello, I have chosen to represent a graph in Haskell by a list of nodes (ex. n=[1,2,3,4]) and a list of pairs representing the edges (example m=[(1,2), (2,3)]). Now I have to see if the graph is strongly connected.

My main issue is how to find if there is a way between 2 nodes in the graph. I wrote something like that:

-- sees if 2 nodes are adjacent

adjacent x y [] = False

adjacent x y (mu:m) =  
        if(x== (fst mu) && y==(snd mu)) then True  
        else adjacent x y m

-- the successor of a node, ex for the edge (1,2) the succ of 1 is 2  
suc x [] = 0  
suc x (l:list) =   
        if(x==(fst l)) then snd l  
        else suc x list

-- my main function
way 0 y list = False 

way x y (mu:m)  
    | x==y = True  
    | (adjacent x y (mu:m)) == True = True  
    | otherwise =   
        if ((way (suc x (mu:m)) y (mu:m))==False) then way (suc x m) y m  
        else True  

It works when I have nodes of degree 1, but for the nodes with a greater degree it doesn't always work. Can you give me a clue about it?

Answer 1

You have two errors of understanding:

1. m, your list of edges is static throughout the entire search. Don't eat it up as you recur in way.
2. Each vertex can have more than one edge leaving it. You want to know whether any of the neighbours of x has a way to y. To find the neighbours you first have to filter the list of edges to find only the edges leaving x.

You also need to build up a list of nodes you've already visited on your quest to find a connection. If you end up on a node you've already seen, then that particular path has failed.

Some hints to make your code a lot shorter: for adjacent, try elem. For succ, try Data.Maybe.fromMaybe and lookup.

Answer 2

Here are some questions to ask yourself:

1. Should adjacent 3 2 [(1,2),(2,3)] be True?
2. How many successors to 1 are there in the graph [(1,2),(2,3),(1,4),(3,4)]
3. Why does, or doesn't, way need to have both a x==y case and an adjacent x y ... case?
4. In the recursion step of way does the == False test really tell you something that lets you recurse on the smaller graph of m?

In general, you haven't written type signatures for your top level functions. It is usually very instructive to do so, and will communicate your design more clearly:

type Vertex = Int
type Edge = (Vertex, Vertex)
type Graph = [Edge]

adjacent :: Vertex -> Vertex -> Graph -> Bool
suc :: Vertex -> Graph -> Vertex
way :: Vertex -> Vertex -> Graph -> Bool

Think about if those types make sense, and if they decompose your problem as you would expect, just thinking about graphs in general.

Is your aim really the way function, or is it to determine if the graph is connected? You might be presupposing too much about the way in which you can determine if the graph is connected.

Lastly, a small part about Haskell syntax: Like most other languages, function application binds very tightly, tighter than == and && operators. Unlike most other languages, function application doesn't use parenthesis. Hence, adjacent can be recoded as:

adjacent x y [] = False
adjacent x y (mu:m) =  
    if x == fst mu && y == snd mu then True  
    else adjacent x y m 

Which in turn could be simplified to:

adjacent x y [] = False
adjacent x y (mu:m) = (x == fst mu && y == snd mu) || adjacent x y m