A node is one item in a graph. Edges connect nodes, so a path is a sequence of nodes joined by valid connections. In a word-ladder graph, each English word is a node, and an edge represents one allowed transformation between words. Finding a ladder from cat to dog becomes finding a path through those nodes. section 5.1.1
Figure 5.2 A ladder graph for a selection of English words
The ladder graph makes nodes visible as words and shows how edges provide alternative routes between a start word and an end word. section 5.1.1
Nodes do not prescribe a single Haskell value type. A graph can be polymorphic, allowing its nodes to be words, numbers, or another type chosen by the program. For the word game, the useful design question is not just what a node is, but which nodes it connects to and how those connections support shortest-path search. section 5.1.1
For a directed graph, a practical representation maps each node to a list of its connected child nodes. The node is the map key; its children are the values associated with that key. A node without an entry is treated as having no connected nodes, so looking it up returns an empty list. section 5.3.1
Adding and querying nodes
Adding the edge (3,2) records node 2 among node 3’s children. Adding (3,1) gives node 3 the children [2,1]. Querying children 2 returns [] until an edge beginning at node 2 is added. When adding an edge to an existing node, duplicate children are removed with nub. section 5.3.1
Listing 5.7 Functions for adding edges to a directed graph and retrieving connected nodes
import qualified Data.List as L #1
...
addEdge :: (Eq a) => (a, a) -> DiGraph a -> DiGraph a
addEdge (node, child) = M.alter insertEdge node #2
where
insertEdge Nothing = Just [child] #3
insertEdge (Just nodes) =
Just (L.nub (child : nodes)) #4
addEdges :: (Eq a) => [(a, a)] -> DiGraph a -> DiGraph a
addEdges [] graph = graph #5
addEdges (edge : edges) graph = addEdge edge (addEdges edges graph) #6
buildDiGraph :: (Eq a) => [(a, [a])] -> DiGraph a
buildDiGraph nodes = go nodes M.empty
where
go [] graph = graph
go ((key, value) : xs) graph = M.insert key value
(go xs graph) #7
children :: (Eq a) => a -> DiGraph a -> [a]
children = M.findWithDefault [] #8
This implementation shows nodes as keys in a directed adjacency map, with addEdge, addEdges, buildDiGraph, and children defining the main operations. section 5.3.1
Adding an edge requires handling two cases: the starting node may be absent, or it may already have a child list. The underlying alter operation passes Nothing for a missing key and Just value for an existing mapping. Its result can keep, add, replace, or remove a node’s mapping without mutating the associative list. section 5.2
