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 = 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
                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 ->
                es = List.filter (\(a,b) -> (a == x) || (b == x)) edges
                gs = List.repeat (List.length es) ((gNodes, edges), pathNodes)
                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 =
        es_ = Set.toList <| Set.remove (x,y) <| Set.fromList es
        end_ = if x == end then y else x
        ((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 ->

        Just x ->
            x == end

last : List a -> Maybe a
last list = 
    List.head (List.reverse list)

Back to problem

results matching ""

    No results matching ""