In Haskell, we may represent a graph in adjacency-list representation using an association list that maps each vertex to a list of its neighbors:
type Graph a = [(a, [a])]
For example, consider this undirected graph:
We may represent it as
graph = [ ('a', "ce"), ('b', "de"), ('c', "adf"), ('d', "bcef"),
('e', "bdf"), ('f', "cdeg"), ('g', "f") ]a) Write a function
adjacent :: Eq a => Graph a -> a -> [a]
that returns a list of a vertex's neighbors in a graph.
b) Write a function
paths :: Eq a => Graph a -> a -> a -> [[a]]
that takes a graph and the ids of start and end vertices v and w, and returns a list of all possible paths from v to w, where a path is represented as a list of vertices. A path may not contain the same vertex twice.
Write a function
dfs :: Eq a => Graph a -> a -> [a]
that takes a graph and the id of a start vertex v, and returns a list of all vertices that are reachable from v. Use a depth-first search. Write the function two ways: (a) using recursion to explore the graph; (b) using a stack data structure.
a) Write a function that takes a directed graph and returns True if the graph is cyclic, otherwise False.
b) Modify your function to work on an undirected graph.
Write a function that takes a graph and the ids of start and end vertices v and w, and returns a list of vertices on the shortest path from v to w, or Nothing if there is no such path. Use a breadth-first search.
In an undirected graph, a Hamiltonian path is a path that visits every vertex exactly once.
Write a function that takes a graph in adjacency-list representation and returns a list of all Hamiltonian paths in the graph.
Write a function that takes two graphs in adjacency list representation and returns true if the graphs are isomorphic.