In today’s Programming Praxis exercise, our goal is to write a function that determines whether a given graph is a eulerian circuit, path, or neither and if so, to produce that path. Let’s get started, shall we?
import Data.List import qualified Data.Map as M
A graph that has 1 or more than 2 vertices with an odd amount of neighbours will never be a eulerian path. To determine whether a path is a circuit we simply check if it loops around. If possible, we start at a vertex with an odd amount of neighbours, since this is required for paths and optional for circuits.
check :: Ord a => M.Map a [a] -> Maybe (String, [a]) check graph | notElem (length . filter (odd . length) $ M.elems graph) [0,2] = Nothing | head path == last path = Just ("Circuit", path) | otherwise = Just ("Path", path) where path = walk [] graph start start = maybe (last $ M.keys graph) id $
To actually walk the graph we use the algorithm provided in the problem description.
walk :: Ord a => [(a, [a])] -> M.Map a [a] -> a -> [a] walk stack g v = case (g M.! v, stack) of (n:_,_) -> walk ((v, g' M.! v):stack) g' n where g' = M.adjust (delete n) v $ M.adjust (delete v) n g ([] ,(s,_):ss) -> v : walk ss g s ([] ,[]) -> [v]
Some tests to see if everything is working properly:
main :: IO () main = do let square = M.fromList [('A',"BC"), ('B',"AD"), ('C',"AD"), ('D',"BC")] let envelope = M.fromList [('A',"BCD"), ('B',"ACD"), ('C',"ABDE"), ('D',"ABCE"), ('E',"CD")] let seven = M.fromList [('A',"BBC"), ('B',"AACDD"), ('C',"ABD"), ('D',"BBC")] let five = M.fromList [('A',"BC"), ('B',"ACD"), ('C',"ABD"), ('D',"BC")] let star = M.fromList [('A',"B"), ('B',"ACD"), ('C',"B"), ('D',"B")] print $ check square print $ check envelope print $ check star == Nothing print $ check seven == Nothing print $ check five