# Graph Traversal

An example implementation of Depth First Search and Breadth First Search in Roc.

## Code

## The Graph interface represents a [graph](https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)) ## using an [adjacency list](https://en.wikipedia.org/wiki/Adjacency_list) ## and exposes functions for working with graphs, such as creating one from a list and ## performing a depth-first or breadth-first search. module [ Graph, fromList, fromDict, dfs, bfs, ] ## Graph type representing a graph as a dictionary of adjacency lists, ## where each key is a vertex and each value is a list of its adjacent vertices. Graph a := Dict a (List a) where a implements Eq ## Create a Graph from an adjacency list. fromList : List (a, List a) -> Graph a fromList = \adjacencyList -> emptyDict = Dict.withCapacity (List.len adjacencyList) update = \dict, (vertex, edges) -> Dict.insert dict vertex edges List.walk adjacencyList emptyDict update |> @Graph ## Create a Graph from an adjacency list. fromDict : Dict a (List a) -> Graph a fromDict = @Graph ## Perform a depth-first search on a graph to find a target vertex. ## [Algorithm animation](https://en.wikipedia.org/wiki/Depth-first_search#/media/File:Depth-First-Search.gif) ## ## - `isTarget` : A function that returns true if a vertex is the target. ## - `root` : The starting vertex for the search. ## - `graph` : The graph to perform the search on. dfs : (a -> Bool), a, Graph a -> Result a [NotFound] dfs = \isTarget, root, @Graph graph -> dfsHelper isTarget [root] (Set.empty {}) graph # A helper function for performing the depth-first search. # # `isTarget` : A function that returns true if a vertex is the target. # `stack` : A List of vertices to visit. # `visited` : A Set of visited vertices. # `graph` : The graph to perform the search on. dfsHelper : (a -> Bool), List a, Set a, Dict a (List a) -> Result a [NotFound] dfsHelper = \isTarget, stack, visited, graph -> when stack is [] -> Err NotFound [.., current] -> rest = List.dropLast stack 1 if isTarget current then Ok current else if Set.contains visited current then dfsHelper isTarget rest visited graph else newVisited = Set.insert visited current when Dict.get graph current is Ok neighbors -> # filter out all visited neighbors filtered = neighbors |> List.keepIf (\n -> !(Set.contains newVisited n)) |> List.reverse # newly explored nodes are added to LIFO stack newStack = List.concat rest filtered dfsHelper isTarget newStack newVisited graph Err KeyNotFound -> dfsHelper isTarget rest newVisited graph ## Perform a breadth-first search on a graph to find a target vertex. ## [Algorithm animation](https://en.wikipedia.org/wiki/Breadth-first_search#/media/File:Animated_BFS.gif) ## ## - `isTarget` : A function that returns true if a vertex is the target. ## - `root` : The starting vertex for the search. ## - `graph` : The graph to perform the search on. bfs : (a -> Bool), a, Graph a -> Result a [NotFound] bfs = \isTarget, root, @Graph graph -> bfsHelper isTarget [root] (Set.single root) graph # A helper function for performing the breadth-first search. # # `isTarget` : A function that returns true if a vertex is the target. # `queue` : A List of vertices to visit. # `seen` : A Set of all seen vertices. # `graph` : The graph to perform the search on. bfsHelper : (a -> Bool), List a, Set a, Dict a (List a) -> Result a [NotFound] bfsHelper = \isTarget, queue, seen, graph -> when queue is [] -> Err NotFound [current, ..] -> rest = List.dropFirst queue 1 if isTarget current then Ok current else when Dict.get graph current is Ok neighbors -> # filter out all seen neighbors filtered = List.keepIf neighbors (\n -> !(Set.contains seen n)) # newly explored nodes are added to the FIFO queue newQueue = List.concat rest filtered # the new nodes are also added to the seen set newSeen = List.walk filtered seen Set.insert bfsHelper isTarget newQueue newSeen graph Err KeyNotFound -> bfsHelper isTarget rest seen graph # Test DFS with multiple paths expect actual = dfs (\v -> Str.startsWith v "C") "A" testGraphMultipath expected = Ok "Ccorrect" actual == expected # Test BFS with multiple paths expect actual = bfs (\v -> Str.startsWith v "C") "A" testGraphMultipath expected = Ok "Ccorrect" actual == expected # Test DFS expect actual = dfs (\v -> Str.startsWith v "F") "A" testGraphSmall expected = Ok "F-DFS" actual == expected ## Test BFS expect actual = bfs (\v -> Str.startsWith v "F") "A" testGraphSmall expected = Ok "F-BFS" actual == expected # Test NotFound DFS expect actual = dfs (\v -> v == "not a node") "A" testGraphSmall expected = Err NotFound actual == expected # Test NotFound BFS expect actual = dfs (\v -> v == "not a node") "A" testGraphSmall expected = Err NotFound actual == expected # Test DFS large expect actual = dfs (\v -> v == "AE") "A" testGraphLarge expected = Ok "AE" actual == expected ## Test BFS large expect actual = bfs (\v -> v == "AE") "A" testGraphLarge expected = Ok "AE" actual == expected # Some helpers for testing testGraphSmall = [ ("A", ["B", "C", "F-BFS"]), ("B", ["D", "E"]), ("C", []), ("D", []), ("E", ["F-DFS"]), ("F-BFS", []), ("F-DFS", []), ] |> fromList testGraphLarge = [ ("A", ["B", "C", "D"]), ("B", ["E", "F", "G"]), ("C", ["H", "I", "J"]), ("D", ["K", "L", "M"]), ("E", ["N", "O"]), ("F", ["P", "Q"]), ("G", ["R", "S"]), ("H", ["T", "U"]), ("I", ["V", "W"]), ("J", ["X", "Y"]), ("K", ["Z", "AA"]), ("L", ["AB", "AC"]), ("M", ["AD", "AE"]), ("N", []), ("O", []), ("P", []), ("Q", []), ("R", []), ("S", []), ("T", []), ("U", []), ("V", []), ("W", []), ("X", []), ("Y", []), ("Z", []), ("AA", []), ("AB", []), ("AC", []), ("AD", []), ("AE", []), ] |> fromList testGraphMultipath = [ ("A", ["B", "Ccorrect"]), ("B", ["Ccorrect", "Cwrong"]), ("Ccorrect", []), ("Cwrong", []), ] |> fromList

## Output

Run this from the directory that has `Graph.roc`

in it:

$ roc test Graph.roc 0 failed and 4 passed in 653 ms.