An adjacency list represents a graph by recording which nodes are connected. For a polymorphic Haskell graph, an associative list of node pairs can represent an undirected, unweighted graph. section 5.1.1
A simple pair list is easy to understand but requires scanning the whole list to test edges, find neighbors, or insert without duplicates. An adjacency map indexes each node to its neighbors, making it better suited to efficient traversal. section 5.1.1
Choose the representation according to the graph:
- Use node pairs when an undirected edge is naturally represented by the presence of one connecting tuple. section 5.1.1
- Use a node-to-neighbors map for directed traversal; each mapping entry implies edges in one direction. section 5.1.1
- Represent one undirected edge twice in a directed adjacency map, once from each endpoint. section 5.1.1
Two connected nodes
For nodes 1 and 2, an undirected adjacency map can be written as [(1, [2]), (2, [1])]. The two entries express both traversal directions. section 5.1.1
type DiGraph a = [(a, [a])]
Inspect the Haskell type for a directed adjacency map: a polymorphic node maps to a list of neighboring nodes. section 5.1.1
