Practical Graph Theory

The Algorithms Behind Modern Software

Introduction

1. The Shape of Software Problems
2. What This Book Is
3. What This Book Is Not
4. Prerequisites
5. How to Use This Book
6. A Note on Rigor
7. What Lies Ahead

Chapter 1: What Is a Graph?

1. A First Intuition: From Networks to Abstractions
2. Vertices, Edges and the Mathematical Definition
3. Directed and Undirected Graphs
4. Weighted Graphs and Edge Labels
5. Paths, Cycles, Walks and Trails
6. Connectivity and Connected Graphs
7. Trees, Forests and Cycles
8. Graph Properties: Degree, Density and Diameter
9. Summary

Chapter 2: Representing Graphs in Memory

1. Adjacency Lists: Structure and Trade-offs
2. Adjacency Matrices: When Density Pays Off
3. Edge Lists and Adjacency Arrays
4. Implicit and Dynamic Graphs
5. Multigraphs, Self-Loops and Parallel Edges
6. Space and Time Complexity of Representations
7. Implementation: The Base Graph Class
8. Summary

Chapter 3: Breadth-First Search

1. The Layer-by-Layer Idea
2. Queue-Based Implementation
3. Reachability and Shortest Paths in Unweighted Graphs
4. Level Graphs and Distance Labels
5. Reconstructing Shortest Paths
6. BFS on Directed Graphs
7. Complexity and Invariants
8. Summary

Chapter 4: Depth-First Search

1. The Recursive Dive
2. Iterative DFS and the Call Stack
3. Discovery and Finish Times
4. The DFS Forest and Edge Classification
5. Detecting Cycles with DFS
6. Topological Sorting via DFS
7. Complexity and Stack Overflow Considerations
8. Summary

Chapter 5: Connectivity and Components

1. Connected Components in Undirected Graphs
2. The Connected Components Algorithm
3. Counting Components and Component Sizes
4. Bipartite Graphs and Two-Coloring
5. Testing Bipartiteness
6. Applications: Dependency Partitioning
7. Summary

Chapter 6: Trees as Graphs

1. Tree Definitions and Characterizations
2. Rooted Trees and Parent-Child Relations
3. Tree Traversals: Preorder, Inorder, Postorder
4. Parent Pointers and Tree Distance
5. From Graphs to Spanning Trees
6. Forests and Multi-Rooted Structures
7. Summary

Chapter 7: Directed Acyclic Graphs and Topological Order

1. Directed Cycles and Their Meaning
2. Detecting Cycles in Directed Graphs
3. Kahn’s Algorithm for Topological Sort
4. DFS-Based Topological Sort
5. Multiple Valid Orders and Ties
6. DAG Dynamic Programming Foundations
7. Cycle Reporting: Extracting the Cycle
8. Summary

Chapter 8: Strong Connectivity

1. What Is Strong Connectivity?
2. The Condensation Graph
3. Kosaraju’s Algorithm: Two-Pass DFS
4. Tarjan’s Algorithm: One-Pass Low Links
5. Correctness Arguments for Both
6. Choosing Between Kosaraju and Tarjan
7. Summary

Chapter 9: Critical Structure: Bridges and Articulation Points

1. Articulation Points: Vertices That Break Graphs
2. Bridges: Edges That Disconnect Components
3. The Low-Link Value Technique
4. Finding Bridges and Articulation Points in O(V+E)
5. Cut Vertices and Biconnected Components
6. Applications in Network Resilience
7. Summary

Chapter 10: Shortest Paths in Unweighted Graphs

1. BFS as Shortest Path Algorithm
2. Single-Source Shortest Paths
3. Multi-Source Shortest Paths
4. All-Pairs in Unweighted Graphs
5. Counting Shortest Paths
6. Shortest Path Trees
7. Summary

Chapter 11: Dijkstra’s Algorithm

1. The Greedy Insight
2. Priority Queue Implementation
3. Proof of Correctness
4. Time Complexity and Heap Choices
5. Handling Ties and Determinism
6. Early Termination and Bidirectional Search
7. Summary

Chapter 12: Negative Weights and Bellman-Ford

1. Why Dijkstra Breaks with Negative Edges
2. Relaxation and Bellman-Ford
3. Negative Cycle Detection
4. Complexity Analysis
5. Applications: Arbitrage and Potential Functions
6. SPFA as a Practical Variant
7. Summary

Chapter 13: All-Pairs Shortest Paths and Heuristics

1. Floyd-Warshall Algorithm
2. Dynamic Programming View of Floyd-Warshall
3. Johnson’s Algorithm for Sparse Graphs
4. A* Search and Admissible Heuristics
5. Consistent vs Admissible Heuristics
6. Choosing Between All-Pairs Methods
7. Summary

Chapter 14: Minimum Spanning Trees

1. The MST Problem
2. Cut Property and Cycle Property
3. Kruskal’s Algorithm
4. Prim’s Algorithm
5. Correctness Proofs
6. Dense vs Sparse Graph Choices
7. Summary

Chapter 15: Disjoint-Set Union

1. The Union-Find Problem
2. Naive Implementation and Its Failure
3. Union by Rank
4. Path Compression
5. Nearly-Linear Time via Amortized Analysis
6. Advanced Variants: Persistent and Rollback DSU
7. Summary

Chapter 16: Network Flow

1. Flow Networks and the Max Flow Problem
2. Cuts and the Max-Flow Min-Cut Theorem
3. Ford-Fulkerson Method
4. Edmonds-Karp: BFS for Strong Polynomial Time
5. Dinic’s Algorithm and Level Graphs
6. Complexity Comparisons
7. Summary

Chapter 17: Bipartite Matching

1. Bipartite Matching Formulation
2. Maximum Matching via Max Flow
3. Hopcroft-Karp Algorithm
4. Alternating Paths and Augmenting Paths
5. Applications: Task Assignment and Scheduling
6. Summary

Chapter 18: Graph Coloring and Hard Problems

1. Vertex Coloring and Chromatic Number
2. Greedy Coloring and Its Limits
3. Brooks’ Theorem and Special Cases
4. NP-Completeness of Coloring
5. Approximation Algorithms
6. Applications: Register Allocation and Scheduling
7. Summary

Chapter 19: Eulerian and Hamiltonian Paths

1. Eulerian Paths and Circuits
2. Hierholzer’s Algorithm
3. Hamiltonian Paths and NP-Hardness
4. Approximation and Heuristics
5. Applications: Route Planning and DNA Sequencing
6. Summary

Chapter 20: Tree Algorithms and LCA

1. Lowest Common Ancestor
2. Binary Lifting for LCA
3. Rooted Tree Queries
4. Path Aggregation on Trees
5. Tree Isomorphism Basics
6. Summary

Chapter 21: Heavy-Light and Centroid Decomposition

1. Heavy-Light Decomposition
2. Path Decomposition and Chains
3. Combining HLD with Segment Trees
4. Centroid Decomposition
5. Applications: Dynamic Tree Problems
6. Summary

Chapter 22: Treewidth, Sparsification and Randomized Algorithms

1. Treewidth and Tree Decompositions
2. Fixed-Parameter Tractability
3. Graph Sparsification
4. Randomized Algorithms for Connectivity
5. Sketches for Massive Graphs
6. Summary

Chapter 23: Dependencies and Build Systems

1. Package Dependencies as DAGs
2. Dependency Resolution and Conflicts
3. Build-System Scheduling
4. Circular Dependency Detection
5. Incremental Recomputation
6. Summary

Chapter 24: Networking and Routing

1. Shortest Path Routing
2. Link-State Routing and Dijkstra
3. OSPF and IS-IS in Practice
4. Network Flow for Capacity Planning
5. Redundancy and Fault Tolerance
6. Summary

Chapter 25: Social Networks and Recommendations

1. Social Graphs as Data Structures
2. Connectivity and Communities
3. PageRank and Random Walks
4. Collaborative Filtering as Graph Matching
5. Scalability Challenges
6. Summary

Chapter 26: Workflow Orchestration and Distributed Systems

1. Workflow DAGs
2. Scheduling with Dependencies
3. Distributed Coordination Graphs
4. Failure Recovery and Retries
5. Cycle Detection in Distributed State
6. Summary

Chapter 27: Algorithm Selection Framework

1. Graph Modeling as First Step
2. Problem Classification by Graph Type
3. Choosing Between Algorithm Families
4. Scalability Trade-offs
5. Library vs Custom Implementation
6. Summary

Chapter 28: Production-Grade Graph Code

1. Designing the Graph Library API
2. Testing Graph Algorithms
3. Benchmarking and Profiling
4. Memory Optimization for Large Graphs
5. Integrating with NetworkX and Other Libraries
6. Summary

Chapter 29: Final Synthesis

1. The Unifying View of Graph Algorithms
2. Common Patterns and Invariants
3. When Graphs Are Not the Right Abstraction
4. Emerging Areas: Graph Neural Networks and Beyond
5. A Practitioner’s Checklist
6. Summary

Conclusion

1. Delivering on the Promise
2. The Lasting Value
3. A Final Note

References