Graph Algorithms
Overview
Use this skill to choose and validate graph approaches that are correct for the domain and efficient for expected scale.
Scope Boundaries
- The problem involves reachability, shortest paths, dependencies, connectivity, matching, or flow.
- Algorithm choice materially affects correctness guarantees or runtime cost.
- Teams need explicit trade-off rationale between multiple graph approaches.
Shared References
- Algorithm selection rules:
references/graph-algorithm-selection-rules.md
Templates And Assets
- Problem framing template:
assets/graph-problem-framing-template.md
- Algorithm comparison template:
assets/graph-algorithm-comparison-template.md
Inputs To Gather
- Entity/relationship model and graph directionality assumptions.
- Constraints (weighted/unweighted, cyclic/acyclic, static/dynamic updates).
- Scale expectations (nodes, edges, update/query ratio, latency budget).
- Correctness requirements and acceptable approximation/error policy.
Deliverables
- Graph representation choice with invariants and assumptions.
- Candidate algorithm comparison with complexity and fit rationale.
- Validation plan for correctness, complexity, and edge-case handling.
- Residual risk list for scaling or approximation trade-offs.
Workflow
- Frame the problem using
assets/graph-problem-framing-template.md. - Determine representation (adjacency list/matrix/edge list) based on scale and operations.
- Compare candidate algorithms using
assets/graph-algorithm-comparison-template.md. - Select an approach using
references/graph-algorithm-selection-rules.md. - Validate with correctness tests (cycles, disconnected components, degenerate cases).
- Measure complexity behavior under representative and worst-case workloads.
- Publish decision rationale, constraints, and follow-up optimization actions.
Quality Standard
- Representation and algorithm assumptions are explicit and testable.
- Complexity claims are tied to real workload characteristics.
- Edge and failure cases are validated, not inferred.
- Trade-offs between accuracy, latency, and memory are documented.
Failure Conditions
- Stop when representation assumptions conflict with domain behavior.
- Stop when chosen algorithm fails required correctness guarantees.
- Escalate when performance requirements cannot be met with current constraints.