## Posts Tagged ‘graph’

### 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
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```

### Programming Praxis – Topological Sort

November 19, 2010

In today’s Programming Praxis exercise, our goal is to write two functions related to directed acyclical graphs (DAGs). The first one is to check whether a given directed graph is acyclical. The second is to perform a topological sort of a DAG, which means to sort it so that no node precedes a node that leads to it. Let’s get started, shall we?

A quick import:

```import Data.List
```

The following function is just a bit of syntactic sugar for an operation I use a few times.

```with :: (a -> b) -> [a] -> (b -> b -> Bool) -> b -> [a]
with t xs eq x = filter ((eq x) . t) xs
```

Both functions need to find vertices with no incoming edges.

```noIncoming :: Eq a => [(a, a)] -> [a] -> Maybe a
noIncoming es = find (null . with snd es (==))
```

Checking if a graph is cyclical is a simple matter of recursively removing nodes with no incoming edges to see if any remain, which would mean that the graph is cyclical.

```isCyclic :: Eq a => [(a, a)] -> Bool
isCyclic = not . null . until (\x -> remove x == x) remove where
remove es = maybe es (with fst es (/=)) . noIncoming es \$ map fst es
```

The process for topologically sorting a list is roughly similar: Find a vertex with no incoming edges, remove the edges leading from it and repeat, returning the vertices in the correct order.

```tsort :: Eq a => [(a, a)] -> [a]
tsort xs = if isCyclic xs then error "cannot sort cyclic list"
else f xs . nub . uncurry (++) \$ unzip xs where
f es vs = maybe [] (\v -> v : f (with fst es (/=) v) (delete v vs)) \$
noIncoming es vs
```

Some tests to see if everything is working correctly:

```main :: IO ()
main = do print \$ isCyclic [(3,8),(3,10),(5,11),(7,8)
,(7,11),(11,2),(11,9),(11,10)]
print \$ isCyclic [(3,8),(3,10),(5,11),(7,8),(7,11)
,(10,5),(11,2),(11,9),(11,10)]
print \$ tsort [(3,8),(3,10),(5,11),(7,8)
,(7,11),(11,2),(11,9),(11,10)]
```

We get a different order than the Scheme solution, but as the exercise mentions there are many different possible sorts. Since we’re using a different algorithm, we get different results.