## Posts Tagged ‘konigsberg’

### Programming Praxis – The Seven Bridges of Königsberg

May 31, 2013

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