16 Directed Acyclic Graphs
16.1 Sharing and Equality
16.1.1 Re-Examining Equality
16.1.2 The Cost of Evaluating References
16.1.3 Notations for Equality
16.1.4 On the Internet, Nobody Knows You’re a DAG
16.1.5 It’s Always Been a DAG
16.1.6 From Acyclicity to Cycles
16.2 The Size of a DAG
16.2.1 Stage 1
16.2.2 Stage 2
16.2.3 Stage 3
16.2.4 Stage 4
16.2.5 Stage 5
16.2.6 What We’ve Learned
16.2.7 More on Value Printing: An Aside from Racket
17 Graphs
17.1 Introducing Graphs
17.1.1 Understanding Graphs
17.1.2 Representations
17.1.2.1 Links by Name
17.1.2.2 Links by Indices
17.1.2.3 A List of Edges
17.1.2.4 Abstracting Representations
17.1.3 Measuring Complexity for Graphs
17.2 Basic Graph Traversals
17.2.1 Reachability
17.2.1.1 Simple Recursion
17.2.1.2 Cleaning up the Loop
17.2.1.3 Traversal with Memory
17.2.1.4 A Better Interface
17.2.2 Depth- and Breadth-First Traversals
17.3 Graphs With Weighted Edges
17.4 Shortest (or Lightest) Paths
17.5 Moravian Spanning Trees
17.5.1 The Problem
17.5.2 A Greedy Solution
17.5.3 Another Greedy Solution
17.5.4 A Third Solution
17.5.5 Checking Component Connectedness
18 Several Variations on Sets
18.1 Representing Sets as Lists
18.1.1 Representation Choices
18.1.2 Time Complexity
18.1.3 Choosing Between Representations
18.1.4 Other Operations
18.2 Making Sets Grow on Trees
18.2.1 Using Binary Trees
18.2.2 Checking the Complexity
18.2.3 A Fine Balance: Tree Surgery
18.2.3.1 Left-Left Case
18.2.3.2 Left-Right Case
18.2.3.3 Any Other Cases?
18.3 Union-Find
18.3.1 Implementing with State
18.3.2 Optimizations
18.3.3 Analysis
18.4 Hashes, Sets, and Key-Values
18.4.1 A Hash Function for Strings
18.4.2 Sets from Hashing
18.4.3 Arrays
18.4.4 Sets from Hashing and Arrays
18.4.5 Collisions
18.4.6 Resolving Collisions
18.4.7 Complexity
18.4.8 Bloom Filters
18.4.9 Generalizing from Sets to Key-Values
18.5 Equality, Ordering, and Hashing
18.5.1 Converting Values to Ordered Values
18.5.2 Hashing in Practice
18.5.3 Equality and Ordering
18.6 Sets as a Case Study
18.6.1 Nature of the Data
18.6.2 Nature of the Operations
18.6.3 Nature of the Guarantee