A directed graph connects nodes with oriented edges: a path may follow an edge from one node to another, but not automatically in reverse. A ladder graph uses words as nodes and one-letter transformations as edges for shortest-path searches. section 5.1.1
For a polymorphic Haskell representation, store each node with the list of nodes reachable directly from it. An adjacency list can represent this structure, while an associative map improves lookup over scanning every edge. section 5.1.1 section 5.3.1
type DiGraph a = [(a, [a])]
The compact adjacency-list type maps each node to its outgoing neighbors. section 5.1.1
A practical directed-graph API provides operations to:
- Create an empty graph. section 5.3.1
- Add one edge or fold multiple edges into the graph. section 5.3.1
- Retrieve a node's connected successors, returning an empty list when the node is absent. section 5.3.1
- Remove duplicate successors when adding an existing edge. section 5.3.1
Building and querying a graph in GHCi
g = addEdges [(1,1), (1,2), (3,2), (3,1)] Graph.empty; children 3 g returns [2,1], while children 2 g returns []. Adding (2,1) makes children 2 return [1]. section 5.3.1
