Haskell Graphic View

Question

I decided to present the graph in Haskell using a list of nodes (e.g. n=[1,2,3,4]) and a list of pairs representing edges (example m=[(1,2), (2,3)]). Now I have to see if the graph is tightly connected.

My main problem is how to find a way between two nodes in the graph. I wrote something like this:

-- 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 nodes with a greater degree it does not always work. Can you let me know about this?

Answer 1

You have two errors of understanding:

• m, your list of edges is static throughout the search. Do not eat it when you return to way.
• , . , any x a way to y. , filter , , x.

, , . node, , .

, : adjacent elem. succ Data.Maybe.fromMaybe lookup.

Answer 2

, :

• adjacent 3 2 [(1,2),(2,3)] True?
• 1 [(1,2),(2,3),(1,4),(3,4)]
• , way x==y, adjacent x y ...?
• way == False -, m?

, . , :

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

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

, , , , .

way , ? , , , .

, Haskell: , - , , == &&. , - . , adjacent :

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

, , :

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