Graph search algorithm fails-CodePudding

I tried to modify my code that uses Graph a to find any vertices that are connected to vertex n. The definition of connection here is that vertex m is either directly connected to vertex n (via an edge) or connected to vertex k which in turn is connected to vertex n.

The code that I want to modify

-- ** Code 1 **

findPath :: Eq a => Graph a -> a -> [a]
findPath (Graph v w) a
    | [x | x<-v, x==a] == [] = []
    | otherwise = findPath' (Graph v w) [a]

findPath' :: Eq a => Graph a -> [a] -> [a]
findPath' (Graph [] _) _ = []
findPath' (Graph _ _) [] = []
findPath' (Graph v w) (tp:st)
    | [x | x<-v, x==tp] == [] = findPath' (Graph vv w) st
    | otherwise = tp : findPath' (Graph vv w) (adjacent    st)
    where
        adjacent = [x | (x,y)<-w, y==tp]    [x | (y,x)<-w, y==tp]
        vv = [x | x<-v, x/=tp]

connected :: Eq a => Graph a -> a -> a -> Bool
connected g a b =  if (a `elem` (findPath g b)) == True then True else False

My attempt at modifying it

-- **Code 2**

convert :: [a] -> [(a, a)]
convert [] = []
convert (k:v:t) = (k, v) : convert t


-- a is vertex
-- [a] is a list from neighbors
getEdges :: Eq a => a -> [a] -> [a]
getEdges _ [] = []
getEdges a (y:ys) = a : y : getEdges a ys


-- vertices :: Eq a => Graph a -> [a]
-- neighbors :: Eq a => Graph a -> a -> [a]
-- [a] is a list of vertex
mergeEdges :: Eq a => Graph a -> [a] -> [a]
mergeEdges _ [] = []
mergeEdges g (x:xs) = getEdges x (neighbors g x)    mergeEdges g xs

removeElements :: Eq a => [(a,a)] -> [(a,a)]
removeElements [] = []
removeElements ((a,b) : (v,w) : xs) =  [(a,b)]    removeElements xs

--v = vertex, w = edges
findPath :: Eq a => [a] -> [(a,a)] -> a -> [a]
findPath v w a
    | [x | x<-v, x==a] == [] = []
    | otherwise = findPath' v w [a]

--v = vertex, w = edges
findPath' :: Eq a => [a] -> [(a,a)] -> [a] -> [a]
findPath' [] _ _ = []
findPath' _ _ [] = []
findPath' v w (tp:st)
    | [x | x<-v, x==tp] == [] = findPath' vv w st
    | otherwise = tp : findPath' vv w (adjacent    st)
    where
        adjacent = [x | (x, y)<-w, y==tp]    [x | (y,x)<-w, y==tp]
        vv = [x | x<-v, x/=tp]

getParam :: Eq a => Graph a -> [(a,a)]
getParam g = removeElements ((convert(mergeEdges g (vertices g))))


connected :: Eq a => Graph a -> a -> a -> Bool
connected g a b = if (a `elem` (findPath (vertices g) (getParam g) b ) ) == True then True else False

Testing the code

This is my graph: Graph {vers = [-6,-3,5,3], edgs = [(-6,5),(3,-3),(-3,5)]}

Code 1:

ghci> connected g 3 5
True

Code 2:

ghci> connected g 3 5
False

My best guess is that when I changed the argument from Graph a to a list of tuples [(a,a)] my code stoped working here but I don't understand why:

| otherwise = tp : findPath' vv w (adjacent    st)
where
    adjacent = [x | (x, y)<-w, y==tp]    [x | (y,x)<-w, y==tp]

I cannot use constructors from Graph a, (..), as it is not allowed :-( and therefore I need to modify my code.

Adding additional code

data Graph a = Graph {
  vers :: [Vertex a],
  edgs    :: [Edge a]
} deriving (Show, Eq, Read)

neighbors :: Eq a => Graph a -> a -> [a]
neighbors (Graph x []) _ = []
neighbors (Graph x ((v, w) : xs)) a
     | a == v = w : neighbors (Graph x xs) a
     | a == w = v : neighbors (Graph x xs) a
     | (v, w) : xs == [] = []
     | otherwise = neighbors (Graph x xs) a

CodePudding user response：

When I run you getParam function on your example input Graph {vers = [-6,-3,5,3], edgs = [(-6,5),(3,-3),(-3,5)]} I get:

ghci> getParam g
[(-6,5),(-3,5),(5,-3)]

Here you can see that the edge (-3,5) and (5,-3) is duplicated and the edge (3,-3) has disappeared. So, I think your removeElements function is too simple. You could perhaps try a function that first sorts the tuple and then removes duplicates:

import Data.List (nub)

...

sortTuple :: Ord a => (a, a) -> (a, a)
sortTuple (x, y)
  | x <= y = (x, y)
  | otherwise = (y, x)

removeElements :: Ord a => [(a, a)] -> [(a, a)]
removeElements xs = nub (map sortTuple xs)

-- also change the types of some other functions:
getParam :: Ord a => Graph a -> [(a,a)]
connected :: Ord a => Graph a -> a -> a -> Bool

Using that function I do get getParam g == [(-6,5),(-3,3),(-3,5)] and connected g 3 5 == True.

But I'm also left wondering why you don't just use getParams g = edgs g?