An edge connects two nodes in a graph. It may be directed, allowing travel from one node to another but not necessarily back, or undirected. Edges can carry costs, though a word-ladder graph treats every edge as one equal transformation step. section 5.1.1
Figure 5.2 A ladder graph for a selection of English words
A word ladder makes edges concrete: each line joins two words reachable through one valid single-step transformation. A chain is a path made from those edges. section 5.1.1
For a directed Haskell graph, an edge can be represented as a pair `(node, child)`. An adjacency-map representation stores each starting node with its list of connected child nodes, making outgoing edges easy to retrieve. section 5.1.1 section 5.3.1
Useful operations on directed edges include:
- Add one edge by altering the entry for its starting node; create that entry when it is absent. section 5.2 section 5.3.1
- Add many edges by applying `addEdge` to every edge in a list. section 5.3.1
- Remove duplicate children when adding an edge, so a node's adjacency list does not repeat a connection. section 5.3.1
- Retrieve a node's connected children with an empty list when the node has no map entry. section 5.3.1
Adding and querying edges
Starting with an empty graph, add `(1,1)`, `(1,2)`, `(3,2)`, and `(3,1)`. The children of `3` are `[2,1]`; the children of `2` are `[]` until `(2,1)` is added, after which they are `[1]`. 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
The listing collects the core edge API: `addEdge`, `addEdges`, graph construction, and `children` lookup. section 5.3.1
