An immutable graph represents nodes and edges that cannot be changed after creation. Each new node or edge produces another graph value, making the representation suitable for graph-coloring search without mutating earlier states. section 8.1
For map coloring, nodes represent regions and undirected edges connect adjacent regions that must receive different colors. Direction matters only when edges identify a from-node and a to-node. section 8.1
A graph type wraps its representation to preserve meaning and enforce invariants:
- Use a generic node type so countries, cities, or other values can serve as nodes. section 8.3
- Store adjacency through an immutable multidictionary, while exposing graph terminology rather than dictionary terminology. section 8.3
- Provide operations for adding and removing nodes and edges, enumerating nodes, and testing node or edge membership. section 8.3
- Maintain undirected symmetry by recording an edge in both directions; the graph type prevents malformed adjacency from leaking through the API. section 8.3
Why the wrapper matters
A raw multidictionary can claim that Paraguay borders Brazil while omitting Paraguay from Brazil’s neighbors or mentioning Bolivia without making it a key. An immutable graph rejects this conceptual mess by owning the node-and-edge invariants. In the South American map, Argentina, Bolivia, Brazil, and Paraguay form a clique because every pair is adjacent. section 8.3
Figure 8.1 On the map of South America, four countries border one another. (Source: https://commons.wikimedia.org/wiki/File:Colored_map_south_America.png; licensed under the Creative Commons Attribution-Share Alike 4.0 International license: https://creativecommons.org/licenses/by-sa/4.0/)
Use the South America map to connect geographical borders with their abstract graph representation. section 8.1
