The Seven Bridges of Königsberg
May 31, 2013
Our exercise today studies a famous problem solved by the great Swiss mathematician Leonhard Euler in 1735, which marked the beginning of what is now the “graph theory” branch of mathematics. Euler proved that it was impossible to cross all seven bridges once without retracing your path. He proved that a complete circuit, returning to the starting point, is possible only if all vertices connect to an even number of neighbors, and a complete path that doesn’t return to the starting point is possible if exactly two of the vertices have an odd number of neighbors, the rest being even, in which case the two odd-count vertices are the starting and ending points of the path.
The following algorithm to determine a eulerian path in a graph, if it exists, is ancient; I would be happy if anybody can provide a pointer to the source of the algorithm:
1) If a complete circuit is possible, choose any vertex at random as the current vertex. If a complete path but not a circuit is possible, choose either of the two odd-degree vertices at random. Otherwise, quit.
2a) If the current vertex has neighbors, add it to the stack, choose any of its neighbors as the new current vertex, and remove the edge between the two vertices.
2b) If the current vertex has no neighbors, add it to the path, remove the last vertex from the stack and make it the current vertex.
3) Repeat step 2 until the current vertex has no neighbors and the stack is empty.
4) Add the current vertex to the path and quit.
Your task is to write programs that determine if a graph is an eulerian circuit or eulerian path and, if it is, determine the path. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to write a function that determines whether a given graph […]
My Haskell solution (see http://bonsaicode.wordpress.com/2013/05/31/programming-praxis-the-seven-bridges-of-konigsberg/ for a version with comments):
import Data.List import qualified Data.Map as M 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 $ find (odd . length . (graph M.!)) $ M.keys graph 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]