|
15 Directed Acyclic Graphs
|
|
15.1 Sharing and Equality
|
|
15.1.1 Re-Examining Equality
|
|
15.1.2 The Cost of Evaluating References
|
|
15.1.3 Notations for Equality
|
|
15.1.4 On the Internet, Nobody Knows You’re a DAG
|
|
15.1.5 It’s Always Been a DAG
|
|
15.1.6 From Acyclicity to Cycles
|
|
15.2 The Size of a DAG
|
|
15.2.1 Stage 1
|
|
15.2.2 Stage 2
|
|
15.2.3 Stage 3
|
|
15.2.4 Stage 4
|
|
15.2.5 Stage 5
|
|
15.2.6 What We’ve Learned
|
|
15.2.7 More on Value Printing: An Aside from Racket
|
|
16 Graphs
|
|
16.1 Introducing Graphs
|
|
16.1.1 Understanding Graphs
|
|
16.1.2 Representations
|
|
16.1.2.1 Links by Name
|
|
16.1.2.2 Links by Indices
|
|
16.1.2.3 A List of Edges
|
|
16.1.2.4 Abstracting Representations
|
|
16.1.3 Measuring Complexity for Graphs
|
|
16.2 Basic Graph Traversals
|
|
16.2.1 Reachability
|
|
16.2.1.1 Simple Recursion
|
|
16.2.1.2 Cleaning up the Loop
|
|
16.2.1.3 Traversal with Memory
|
|
16.2.1.4 A Better Interface
|
|
16.2.2 Depth- and Breadth-First Traversals
|
|
16.3 Graphs With Weighted Edges
|
|
16.4 Shortest (or Lightest) Paths
|
|
16.5 Moravian Spanning Trees
|
|
16.5.1 The Problem
|
|
16.5.2 A Greedy Solution
|
|
16.5.3 Another Greedy Solution
|
|
16.5.4 A Third Solution
|
|
16.5.5 Checking Component Connectedness
|
|
17 Several Variations on Sets
|
|
17.1 Representing Sets as Lists
|
|
17.1.1 Representation Choices
|
|
17.1.2 Time Complexity
|
|
17.1.3 Choosing Between Representations
|
|
17.1.4 Other Operations
|
|
17.2 Making Sets Grow on Trees
|
|
17.2.1 Using Binary Trees
|
|
17.2.2 Checking the Complexity
|
|
17.2.3 A Fine Balance: Tree Surgery
|
|
17.2.3.1 Left-Left Case
|
|
17.2.3.2 Left-Right Case
|
|
17.2.3.3 Any Other Cases?
|
|
17.3 Union-Find
|
|
17.3.1 Implementing with State
|
|
17.3.2 Optimizations
|
|
17.3.3 Analysis
|
|
17.4 Hashes, Sets, and Key-Values
|
|
17.4.1 A Hash Function for Strings
|
|
17.4.2 Sets from Hashing
|
|
17.4.3 Arrays
|
|
17.4.4 Sets from Hashing and Arrays
|
|
17.4.5 Collisions
|
|
17.4.6 Resolving Collisions
|
|
17.4.7 Complexity
|
|
17.4.8 Bloom Filters
|
|
17.4.9 Generalizing from Sets to Key-Values
|
|
17.5 Equality, Ordering, and Hashing
|
|
17.5.1 Converting Values to Ordered Values
|
|
17.5.2 Hashing in Practice
|
|
17.5.3 Equality and Ordering
|
|
17.6 Sets as a Case Study
|
|
17.6.1 Nature of the Data
|
|
17.6.2 Nature of the Operations
|
|
17.6.3 Nature of the Guarantee
|