I have got the code bellow and need to define the function hCycles
using the list monad (and the do notation). hCycles
is supposed to compute the Hamiltonian Cycles for any generic node of the graph in the image.
The thing is I’m not quite sure how to do that with the list monad and since I can’t add the starting node to the function’s arguments, how should I proceed?
-- 1. Graph structure: nodes and adjacency matrix (i.e. the edges)
data Node = A | B | C | D | E | F deriving (Show,Eq,Ord)
adj :: (Node,Node) -> Bool
adj p = case p of
(A,B) -> True
(A,C) -> True
(A,F) -> True
(B,A) -> True
(B,C) -> True
(B,E) -> True
(B,F) -> True
(C,A) -> True
(C,B) -> True
(C,D) -> True
(D,C) -> True
(D,E) -> True
(E,B) -> True
(E,D) -> True
(E,F) -> True
(F,A) -> True
(F,B) -> True
(F,E) -> True
(_,_) -> False
type Path = [Node]
-- 2. Auxiliary functions
adjacentNodes :: Node -> [Node] -> [Node]
adjacentNodes n ns = filter (\x -> adj(n,x)) ns
allNodes :: [Node]
allNodes = [A,B,C,D,E,F]
choice :: ([a],[a]) -> [a]
choice = uncurry (++)
-- 3. To do
hCycles :: Node -> [Path]
hCycles n = undefined
P.S.: I think I have a first version of the function:
hCycles :: Node -> [Path]
hCycles n = do
p <- [[n]]
nextNode <- adjacentNodes n allNodes
if n == nextNode
then [p]
else addtoEnd p allNodes
But I’m not quite sure if the if/else case is correct (since hCycles
isn’t called again, I don’t even think it’s recursive, but I don’t know how to do that)…