A graph represents items as nodes and their relationships as edges. Edges may be directed, allowing travel from one node to another without implying a return edge, or undirected. They can also carry costs, though an unweighted graph is enough when every move counts as one step. section 5.1.1
Word ladders as paths
Treat each dictionary word as a node. Connect two words when one valid game move transforms one into the other. A solution is then a path through the ladder graph; comparing paths reveals whether a chain such as cat to dog is shortest. section 5.1.1
A directed graph can use an adjacency map: map each node to the list of its connected children. This representation keeps the graph polymorphic, so nodes can have any equality-comparable type. Looking up a missing node yields no children. section 5.3.1
Useful operations for an adjacency-map graph include:
- Add one edge. Create the starting node when absent; otherwise extend its child list and remove duplicates. section 5.3.1
- Add a list of edges or build a graph from node-and-child-list pairs. section 5.3.1
- Retrieve a node’s connected children with a map lookup and an empty-list default. section 5.3.1
Build the ladder graph by generating candidate words that add, remove, or modify one letter, finding matching dictionary permutations, and using those words as neighbors. A word with no valid one-step transformations remains a node with an empty neighbor list. section 5.4.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
Inspect the complete Haskell API for adding edges, constructing a directed graph, and retrieving children. section 5.3.1
