--------------------------------------------------------------------------------
-- datatypes for a weighted, undirected graph with each node having a name
--  represented by a string (similar to what you will be representing in your
--  assignments).
data Graph = G [Node] [Edge]	-- A graph consists of sets of nodes and edges
data Edge  = E Node Node Int	-- An edge consists of 2 nodes and a weight
data Node  = N String		-- A node consists of a string, and can be
    deriving Eq 		--  compared to other nodes in a direct way

-- edges can be compared; since the graph is undirected and we only have one
--  edge between any two cities, we don't care about which is the start and
--  which is the end. Nor, for comparison purposes, do we care about the weight
instance Eq Edge where
    (E s1 e1 w1) == (E s2 e2 w2)
        | s1 == s2 && e1 == e2 = True
        | s1 == e2 && e1 == s2 = True
	| otherwise            = False

-- example of a graph (hint: this may be one of the graphs I use to test
--  your assignments!)
g1 :: Graph
g1 = G [N "a", N "b", N "c", N "d", N "e", N "f", N "g", N "h"]
       [E (N "a") (N "b") 16, E (N "b") (N "c") 21, E (N "c") (N "d") 14,
        E (N "d") (N "e") 22, E (N "a") (N "e") 70, E (N "f") (N "g") 17,
	E (N "g") (N "h") 65, E (N "f") (N "h") 94]

--------------------------------------------------------------------------------
-- Can we travel from the given start city to the end city in the graph,
--  without using the edge directly between them (if such an edge exists)?
canTravel :: Graph -> Node -> Node -> Bool
canTravel g start end = search [(g2, start)] end where
    g2 = removeEdge g (E start end 0)

-- perform a depth-first search on a (graph, start city) pair, to see if
--  the given end city is reachable
search :: [(Graph, Node)] -> Node -> Bool
search [] end      = False
search ((g, start):rest) end
    | start == end = True
    | otherwise    = search (newgs ++ rest) end where
        newgs = map (reduce (g, start) outs) outs
	outs  = outEdges g start

-- return a graph identical to that supplied, except with the given edge removed
removeEdge :: Graph -> Edge -> Graph
removeEdge (G ns es) e = (G ns (filter (/= e) es))

-- returns a list of all the edges in the graph that touch the given node
outEdges :: Graph -> Node -> [Edge]
outEdges (G ns es) start = [e | e <- es, touches start e] where
    touches :: Node -> Edge -> Bool
    touches start (E a b w)
        | start == a = True
	| start == b = True
	| otherwise  = False

-- "reduces" the given graph and start node as follows:
--  1. removes the start node, and all edges that touch it, from the graph
--  2. returns a list of all such resulting graphs, one for each outgoing edge
--     such that the new start city in the result corresponds to the city
--     at the other end of that edge
reduce :: (Graph, Node) -> [Edge] -> Edge -> (Graph, Node)
reduce ((G ns es), start) outs (E a b w) = ((G ns' es'), start') where
    ns'                 = filter (/= start) ns
    es'                 = foldr (\e rest -> filter (/= e) rest) es outs
    start' | a == start = b
	   | b == start = a

--------------------------------------------------------------------------------