Problem 81 Solution
This solution defines a new type, GraphPath which defines a path through a graph and the unused edges. Using GraphPath we can recurses to find all possible paths.
import Html
import List
import Set
-- Nodes of a graph must be of type comparable because we define
type alias Edge comparable = (comparable, comparable)
type alias AdjList comparable = (List((comparable, List comparable)))
type alias Graph comparable = (List comparable, List (Edge comparable))
-- add a path to Graph. Edges should be in either the path or the graph but never both
type alias GraphPath comparable = (Graph comparable, List comparable)
-- Given two nodes a graph, return all acyclic paths in the graph between the two nodes
findPaths : comparable -> comparable -> Graph comparable -> List (List comparable)
findPaths start goal graph =
List.map Tuple.second <| findPaths_ goal [(graph, [start])]
-- Given a goal node and a list of path, recursively search each path
-- so we can find all complete paths to the goal
findPaths_ : comparable -> List (GraphPath comparable) -> List (GraphPath comparable)
findPaths_ goal paths =
case paths of
[] -> []
p :: ps ->
if endsAt goal p then
p :: findPaths_ goal ps
else
findPaths_ goal ((extendPath p) ++ ps)
-- given a path, return a list of all edges connecting to the end of the path
extendPath : GraphPath comparable -> List (GraphPath comparable)
extendPath ((gNodes, edges), pathNodes) =
case last pathNodes of
Nothing ->
[]
Just x ->
let
es = List.filter (\(a,b) -> (a == x) || (b == x)) edges
gs = List.repeat (List.length es) ((gNodes, edges), pathNodes)
in
List.filter isAcyclic
<|List.map2 (\gp e -> addToPath gp e x) gs es
isAcyclic : GraphPath comparable -> Bool
isAcyclic (g, ns) =
List.length ns == Set.size (Set.fromList ns)
--given a path, and an edge, construct a GraphPath that adds the edge to the path, and updates the graph to remove the edge
addToPath : GraphPath comparable -> Edge comparable -> comparable -> GraphPath comparable
addToPath ((ns, es), ps) (x,y) end =
let
es_ = Set.toList <| Set.remove (x,y) <| Set.fromList es
end_ = if x == end then y else x
in
((ns, es_), ps ++ [end_])
-- given a value and a path, return if the value matches the last node of the path
endsAt : comparable -> GraphPath comparable -> Bool
endsAt end (g, ns) =
case last ns of
Nothing ->
False
Just x ->
x == end
last : List a -> Maybe a
last list =
List.head (List.reverse list)