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 of 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
?