A graph is a data structure consisting of nodes, or vertices, connected by directed or undirected edges. An undirected graph must preserve adjacency in both directions: if Paraguay connects to Brazil, Brazil must connect to Paraguay. A dedicated graph type can enforce that invariant while hiding whether it uses a multidictionary, adjacency matrix, or another representation. section 8.3
An immutable undirected graph benefits from an abstract, generic interface:
- Represent nodes with a generic type, so callers can use countries, integers, or other values. section 8.3
- Expose operations for adding, removing, and enumerating nodes and edges, and for checking membership. section 8.3
- Store each undirected edge in both directions while presenting nodes and edges rather than dictionary keys and values. section 8.3
- Use cliques to represent groups in which every node is adjacent to every other node. section 8.3
Modeling Sudoku as a graph
A Sudoku grid becomes a graph with 81 nodes, one per cell. Connect two nodes when their cells cannot contain the same number. Each row, column, and three-by-three box forms a clique, turning the puzzle into a graph-coloring problem: digits are colors, and adjacent cells must receive different colors. Because each node has degree 20 while only nine colors are available, solving requires backtracking rather than a simple coloring pass. section 8.5
Listing 8.2 An immutable undirected graph wrapping a multidictionary
readonly struct ImGraph<N> where N : notnull
{
public static ImGraph<N> Empty = new(ImMulti<N, N>.Empty);
private readonly ImMulti<N, N> nodes;
private ImGraph(ImMulti<N, N> ns) => this.nodes = ns;
public bool IsEmpty => nodes.IsEmpty;
public bool HasNode(N n) => nodes.ContainsKey(n);
public bool HasEdge(N n1, N n2) => nodes.HasValue(n1, n2);
public IEnumerable<N> Nodes => nodes.Keys;
public ImmutableHashSet<N> Edges(N n) => nodes[n];
public ImGraph<N> AddNode(N n) =>
HasNode(n) ?
this :
new(nodes.SetItem(n, ImmutableHashSet<N>.Empty));
public ImGraph<N> AddEdge(N n1, N n2) =>
new(nodes.Add(n1, n2).Add(n2, n1));
public ImGraph<N> RemoveEdge(N n1, N n2) =>
new(nodes.Remove(n1, n2).Remove(n2, n1));
public ImGraph<N> RemoveNode(N n)
{
var result = this;
foreach (var n2 in Edges(n))
result = result.RemoveEdge(n, n2);
return new(result.nodes.Remove(n));
}
public ImGraph<N> AddEdges(N n1, IEnumerable<N> ns)
{
var result = this;
foreach (var n2 in ns)
result = result.AddEdge(n1, n2);
return result;
}
public ImGraph<N> AddClique(IList<N> ns)
{
var result = this;
for(int i = 0; i < ns.Count; i += 1)
for(int j = i + 1 ; j < ns.Count; j += 1)
result = result.AddEdge(ns[i], ns[j]);
return result;
}
}
Inspect the immutable C# graph wrapper and its node, edge, membership, and mutation operations. section 8.3
Listing 8.5 A graph for Sudoku puzzles and its colors
var sudoku = ImGraph<int>.Empty;
for (int i = 0; i < 9; i += 1)
sudoku = sudoku.AddClique([.. Enumerable.Range(i * 9, 9)]); #1
for (int i = 0; i < 9; i += 1)
sudoku = sudoku.AddClique(
[.. Enumerable.Range(0, 9).Select(x => x * 9 + i)]); #2
sudoku = sudoku
.AddClique([00, 01, 02, 09, 10, 11, 18, 19, 20]) #3
.AddClique([03, 04, 05, 12, 13, 14, 21, 22, 23])
.AddClique([06, 07, 08, 15, 16, 17, 24, 25, 26])
.AddClique([27, 28, 29, 36, 37, 38, 45, 46, 47])
.AddClique([30, 31, 32, 39, 40, 41, 48, 49, 50])
.AddClique([33, 34, 35, 42, 43, 44, 51, 52, 53])
.AddClique([54, 55, 56, 63, 64, 65, 72, 73, 74])
.AddClique([57, 58, 59, 66, 67, 68, 75, 76, 77])
.AddClique([60, 61, 62, 69, 70, 71, 78, 79, 80]);
var digits = ImmutableHashSet<char>.Empty
.Add('1').Add('2').Add('3').Add('4').Add('5')
.Add('6').Add('7').Add('8').Add('9');
Inspect the C# construction of Sudoku rows, columns, and boxes as graph cliques. section 8.5
