Graphs are the natural modeling medium for complex, interconnected real-world networks. Let's analyze three production architectures.
1. Google Maps Navigation Engine
Graph Representation:
- Vertices: Intersections, highway on-ramps, dead-ends.
- Edges: Road segments connecting intersections.
- Weights: Travel time in seconds (computed dynamically using speed limits, distance, and live traffic congestion data).
- Direction: One-way streets are directed edges; two-way streets are paired bidirectional edges.
Intersection A --(60s, traffic)---> Intersection B
| |
(30s) (45s)
v v
Intersection C <--(120s, jam)------- Intersection D
Routing algorithms like Contraction Hierarchies and A Search* traverse this graph to calculate the fastest driving route in milliseconds.
2. Social Networks (Facebook vs Twitter / Instagram)
Undirected Model (Facebook / LinkedIn)
Friendship is mutual: if User A is friends with User B, then User B is friends with User A.
- Modeled as an Undirected Graph.
- Friend suggestions: find 2-hop neighbors with the highest number of mutual connections.
Directed Model (Twitter / Instagram / TikTok)
Following is asymmetric: User A can follow Celebrity B without Celebrity B following User A back.
- Modeled as a Directed Graph.
- High In-Degree = High influence / popular account.
3. Dependency Injection in Android (Dagger & Hilt)
When you annotate dependencies with @Inject in Android:
class UserRepository @Inject constructor(
private val api: ApiService,
private val db: Database
)
Dagger analyzes all classes at compile-time and constructs a Directed Dependency Graph:
[ Activity ]
|
v
[ UserRepository ]
/ \
v v
[ ApiService ] [ Database ]
|
v
[ OkHttpClient ]
Compile-Time Cyclic Dependency Check:
If Class A needs Class B, and Class B needs Class A, Dagger detects a cycle in the graph during compilation and fails the build with a descriptive error, preventing fatal runtime infinite recursion!
Summary
- Navigation systems model roads as weighted directed graphs.
- Social networks use undirected graphs for mutual connections and directed graphs for follower relationships.
- Dependency injectors like Dagger validate architecture at compile time by detecting cycles in DAGs.