{- |
Module: maze/Maze.hs
Calculate a spanning tree (a maze) over a given graph.
-}
module Maze (Node, Edge, Graph, maze, showDot) where
import Data.List
type Node = Char
type Edge = (Node, Node)
type Graph = ([Node], [Edge])
type Class = [Node]
-- Take a graph and return a spanning tree graph (a maze) by calling
-- buildMaze with a set of equivalence classes (one for each node) and
-- a new graph that initially has only nodes but no edges.
maze :: Graph -> Graph
maze g = buildMaze g (map (:[]) ns) (ns, [])
where (ns,es) = g
-- Take a graph, a list of node equivalence classes, a new (spanning
-- tree) graph (which we are building up) and return a spanning tree
-- graph if only one equivalence is left. Otherwise, find an edge and
-- continue building the spanning tree by merging the classes
-- connected by the edge and adding the edge to the spanning tree.
buildMaze :: Graph -> [Class] -> Graph -> Graph
buildMaze g cs (ns,es)
| length cs == 1 = (ns,es)
| otherwise = buildMaze g (mergeClasses cs e) (ns,e:es)
where e = findEdge cs (snd g)
-- Given a list of classes and edges, find an edge that connects two
-- equivalence classes. We pick the first edge is there are multiple
-- but this could also be a random selection. The distinct helper
-- function tests where an edge connects two equivalence classes.
findEdge :: [Class] -> [Edge] -> Edge
findEdge cs es = head (filter (distinct cs) es)
where distinct cs (a,b) = filter (elem a) cs /= filter (elem b) cs
-- Given a list of equivalence classes and an edge, merge equivalence
-- classes given a specific edge by partitioning the classes into
-- those touched by the edge and those not touched by the edge. Concat
-- (join) the touched edges and then return the new list of
-- equivalence classes. The match helper function tests whether an
-- edge matches an equivalence class (i.e., whether any of the
-- endpoints is in the equivalence class.
mergeClasses :: [Class] -> Edge -> [Class]
mergeClasses cs e = concat m : n
where (m,n) = partition (match e) cs
where match (a,b) c = elem a c || elem b c
-- Show a graph in the dot notation.
showDot :: Graph -> String
showDot (ns,es) = "graph xyz {"
++ (concat (map showNode ns))
++ (concat (map showEdge es))
++ "}"
where showNode n = [n] ++ ";"
showEdge e = [a] ++ "--" ++ [b] ++ ";"
where (a,b) = e
-- Read a graph from the dot notation. TBD.
readDot :: String -> Graph
readDot = undefined