The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Graph Applications

Next ►
►

We now have the module's entire theory: traversals (07-03), shortest paths (07-04), and spanning trees (07-05). This lesson introduces not a single new algorithm: it puts them to work in complete, recognizable applications. First, the main course: the TaskFlow scheduler, which combines topological order, cycle detection, level-based parallelization, and computing the project's critical path. Then we'll step outside TaskFlow for two classics: a social network's collaborator suggestions (friends-of-friends with BFS) and a miniature PageRank, the algorithm that launched Google. We close with a panorama of graphs in production. All the code runs on the Graph class from 07-02.

Contents

  1. The complete TaskFlow scheduler
    • Validate: cycle detection
    • Order: topological order
    • Parallelize: tasks by levels
    • Estimate: the project's critical path
  2. Collaborator suggestions: friends-of-friends
  3. Simplified PageRank
  4. Graphs in production: a brief panorama

The complete TaskFlow scheduler

We start from the dependencies graph and the tasks index of 07-02 (remember: every task is a dict with id, title, priority, status, and hours; the edge A → B means "B depends on A"). The scheduler must answer, in this order, four questions: is the project executable? in what order? what can be done in parallel? and how many hours will it take at minimum?

Validate: cycle detection

Nothing makes sense if there's a cycle, so the scheduler starts by reusing has_cycle (white/gray/black, 07-03) as its gatekeeper:

def plan_project(graph, tasks):
    if has_cycle(graph):
        raise ValueError("Circular dependencies: review the project")
    return {
        "order": topological_order(graph),        # 07-03, Kahn
        "levels": parallel_levels(graph),         # new, below
        "duration": critical_path(graph, tasks),  # new, below
    }

In a real application this validation would also run before accepting each new dependency, which is cheaper than letting the error pile up.

Order: topological order

topological_order (Kahn, 07-03) already gives us a valid execution sequence for a single worker. Nothing new to add — except to note that a serial order squanders the team: if design_schema and design_ui don't depend on each other, why wait?

Parallelize: tasks by levels

The layered version of Kahn groups tasks into levels: level 0 is the tasks with no dependencies; level k, the ones that become ready when the previous levels finish. All tasks in the same level can run in parallel:

from collections import deque

def parallel_levels(graph):
    degrees = graph.in_degrees()
    current_level = [v for v, d in degrees.items() if d == 0]
    levels = []
    while current_level:
        levels.append(current_level)
        next_level = []
        for v in current_level:                # "finish" the whole level at once
            for neighbor in graph.neighbors(v):
                degrees[neighbor] -= 1
                if degrees[neighbor] == 0:
                    next_level.append(neighbor)
        current_level = next_level
    return levels

for i, level in enumerate(parallel_levels(dependencies)):
    print(f"Level {i}: {level}")
# Level 0: ['design_schema', 'configure_server', 'design_ui']
# Level 1: ['migrate_db', 'implement_ui']
# Level 2: ['deploy_api']
# Level 3: ['integration_tests']
# Level 4: ['launch']

It's the same Kahn from 07-03, but processing the queue in batches instead of one element at a time — compare it with module 6's level-order traversal, which pulled exactly this maneuver on trees. The management reading: with enough people, the project needs 5 batches; three people can kick off together on Monday.

Estimate: the project's critical path

Final question: with unlimited parallelism, how many hours at minimum does the project take? It's not the sum of all hours (there's parallelism), nor 07-04's shortest path. It's the longest path in the DAG counting each task's hours: the critical path. Any delay on it delays the entire project; every other task has slack.

Longest path? Sounds like inverting Dijkstra (negating weights... only valid without cycles), but on a DAG there's a cleaner, trap-free route: topological order + dynamic programming. Walking the tasks in topological order, by the time we reach a task we already know the finish time of all its dependencies, so:

finish(v) = hours(v) + max(finish(u) for each dependency u of v; 0 if none)
def critical_path(graph, tasks):
    finish = {}       # id -> earliest possible finish time
    critical_parent = {}
    for v in topological_order(graph):         # guarantees finish(u) is ready
        best, culprit = 0, None
        for u in graph.vertices():             # dependencies of v: edges u -> v
            if graph.edge_exists(u, v) and finish[u] > best:
                best, culprit = finish[u], u
        finish[v] = best + tasks[v]["hours"]
        critical_parent[v] = culprit           # the dependency setting the pace

    last = max(finish, key=finish.get)         # the task finishing latest
    path, current = [], last                   # rebuild backward (07-04)
    while current is not None:
        path.append(current)
        current = critical_parent[current]
    return {"hours": finish[last], "path": path[::-1]}

print(critical_path(dependencies, tasks))
# {'hours': 17,
#  'path': ['design_ui', 'implement_ui', 'integration_tests', 'launch']}

Checking the finish times by hand: design_ui 5 → implement_ui 5+8=13; on the other branch, migrate_db finishes at 5 and deploy_api at 7. integration_tests waits for the slower one: max(13, 7) + 3 = 16, and launch wraps up at 17 hours. The critical path runs through the interface: speeding up migrate_db wouldn't move the project up by a minute (it has 6 hours of slack), but every hour gained on implement_ui is an hour off the project.

graph LR
    A[design_schema 3h] --> B[migrate_db 2h]
    S[configure_server 1h] --> C
    B --> C[deploy_api 2h]
    C --> D
    U[design_ui 5h] ==> I[implement_ui 8h]
    I ==> D[integration_tests 3h]
    D ==> L[launch 1h]
    style U stroke:#c00,stroke-width:3px
    style I stroke:#c00,stroke-width:3px
    style D stroke:#c00,stroke-width:3px
    style L stroke:#c00,stroke-width:3px

Efficiency note: the double loop with edge_exists is O(n · a) for teaching clarity; with the reversed graph from 07-03 (exercise 2) it would drop to O(n + a). With this, the scheduler is complete: validation, ordering, parallelism, and estimation in about 60 lines on top of structures we already had.

Collaborator suggestions: friends-of-friends

Change of domain. TaskFlow adds a social touch: suggesting collaborators to each user. The classic social-network heuristic: suggest those at distance exactly 2 — collaborators of my collaborators who aren't yet mine — ranked by how many mutual contacts we share. It's a BFS capped at two layers on an undirected graph:

def suggest_collaborators(graph, user, limit=3):
    direct = set(graph.neighbors(user))               # distance 1
    candidates = {}                                   # candidate -> mutual contacts
    for friend in direct:
        for second in graph.neighbors(friend):        # distance 2
            if second != user and second not in direct:
                candidates[second] = candidates.get(second, 0) + 1
    return sorted(candidates, key=candidates.get, reverse=True)[:limit]

social = Graph(directed=False)
for a, b in [("anna", "bruno"), ("anna", "carla"), ("bruno", "david"),
             ("carla", "david"), ("carla", "elena"), ("david", "frank")]:
    social.add_edge(a, b)

print(suggest_collaborators(social, "anna"))   # ['david', 'elena']

anna gets david suggested ahead of elena because she shares two contacts with him (bruno and carla) and only one with elena. We didn't even need the queue here: with exactly two layers, two nested loops are the truncated BFS — but conceptually it's bfs_distances (exercise 1 of 07-03) filtered to distance 2. This is how — with many refinements layered on top — LinkedIn's or Facebook's "people you may know" works.

Simplified PageRank

The web is a directed graph (pages → links, lesson 07-01). Google's question in 1998: which pages are important? PageRank's idea: a page is important if important pages link to it — a circular definition resolved by iteration. The "random surfer" model: with probability d (≈ 0.85) they follow a random link on the current page; with 1 − d they jump to any page whatsoever. A page's rank is the fraction of time the surfer spends on it:

def pagerank(graph, d=0.85, iterations=30):
    vertices = graph.vertices()
    n = len(vertices)
    rank = {v: 1 / n for v in vertices}           # start: all equal
    for _ in range(iterations):
        new_rank = {v: (1 - d) / n for v in vertices}   # the random jump
        for v in vertices:
            outgoing = graph.out_degree(v)
            if outgoing == 0:                     # page with no links:
                for target in vertices:           # spread across all
                    new_rank[target] += d * rank[v] / n
            else:
                for target in graph.neighbors(v): # spread its rank
                    new_rank[target] += d * rank[v] / outgoing
        rank = new_rank
    return rank

web = Graph(directed=True)
for source, target in [("blog", "docs"), ("blog", "home"), ("docs", "home"),
                       ("forum", "home"), ("home", "docs")]:
    web.add_edge(source, target)

for page, r in sorted(pagerank(web).items(), key=lambda x: -x[1]):
    print(f"{page}: {r:.3f}")
# home: 0.470
# docs: 0.455
# blog: 0.038
# forum: 0.038

Reading the code: on each iteration, every page distributes its rank among its outgoing links (d * rank / outgoing), and everyone additionally receives the random jump's crumb ((1 - d) / n). After a few dozen iterations the values stabilize (it converges to a fixed point). home wins because the other three link to it; docs follows extremely closely with a single incoming link, because the one linking to it is the all-important home — there's the circularity resolved: what counts is not just how many links you receive, but from whom. blog and forum, with no incoming links, are left with the random jump's crumb. In TaskFlow, the same idea applied to the reversed dependency graph would flag the project's "structurally central" tasks.

Graphs in production: a brief panorama

To wrap up, where graphs live in real systems (no code, just a map):

Domain What the graph models What runs on top
Graph databases (Neo4j, Neptune) Entities and relationships as first-class citizens Pattern and path queries (Cypher, Gremlin)
Recommendation (Amazon, Netflix, Spotify) Users ↔ products, bipartite Neighborhoods, random walks, collaborative filtering
CI/CD and builds (Make, Gradle, Airflow) Steps and their dependencies: a DAG Topological order and parallelization — our scheduler, at scale
Maps and logistics Junctions and weighted segments Dijkstra and variants with heuristics (A*)
Fraud detection Accounts, cards, shared devices Connected components and suspicious patterns

The moral: what we've built this module isn't an academic exercise; it's the small, understandable version of the machinery that orchestrates pipelines, routes, and recommendations every day. When the scale grows, the engines change (graph databases, distributed processing), but the concepts — adjacency, BFS, topological order, paths — are exactly these.

Common Mistakes and Tips

  • Confusing the critical path with the shortest path. The critical path is the LONGEST path in the DAG: it sets the project's unavoidable duration. Minimizing (07-04) and maximizing (here) answer opposite questions; dynamic programming over topological order is only valid for maximizing because the DAG has no cycles.
  • Computing the critical path without validating the DAG first. With a cycle, topological_order raises an exception (good); if you used a different, silent implementation, the dynamic programming would read values that were never computed. Always validate first.
  • Forgetting the "no outgoing links" case in PageRank. Without that redistribution, dead ends' rank evaporates on every iteration and the total stops summing to 1 — a classic bug that's hard to notice because the relative ranking can still look reasonable.
  • Accidentally suggesting friends on a directed graph. If you build the social network with directed=True (our class's default), "friends of my friends" will only look in one direction. For friendships, an explicit Graph(directed=False).
  • Tip: notice the pattern of this lesson: no application needed new structures, only composing the existing ones. That composition is the skill that separates someone who "knows algorithms" from someone who solves problems.

Exercises

Exercise 1: a task's slack

Extend critical_path to compute each task's slack: how many hours it can be delayed without affecting the total duration. Hint: also compute the latest allowed finish time, walking the topological order backward from the total duration; slack = latest − earliest.

Exercise 2: collaborators at distance 3

Generalize suggest_collaborators into collaborators_at_distance(graph, user, k) using bfs_distances (exercise 1 of 07-03) to return the users at distance exactly k.

Exercise 3: the most central task

Apply pagerank to the reversed dependencies graph (with reverse from 07-03) and reason about why the highest-ranked task is the one it is.

Solutions

Solution 1:

def slacks(graph, tasks):
    data = critical_path(graph, tasks)
    total = data["hours"]
    finish = {}
    for v in topological_order(graph):
        prior = max((finish[u] for u in graph.vertices()
                     if graph.edge_exists(u, v)), default=0)
        finish[v] = prior + tasks[v]["hours"]

    latest = {}
    for v in reversed(topological_order(graph)):  # from the end back to the start
        successors = [latest[s] - tasks[s]["hours"] for s in graph.neighbors(v)]
        latest[v] = min(successors, default=total)  # no successors: project end
    return {v: latest[v] - finish[v] for v in finish}

print(slacks(dependencies, tasks))
# {'design_schema': 6, 'configure_server': 10, 'migrate_db': 6,
#  'deploy_api': 6, 'design_ui': 0, 'implement_ui': 0,
#  'integration_tests': 0, 'launch': 0}

The tasks with slack 0 are exactly the critical path; configure_server can slip up to 10 hours without moving the launch. This is the PERT/CPM analysis from the project-management handbooks, built out of our own pieces.

Solution 2:

def collaborators_at_distance(graph, user, k):
    distances = bfs_distances(graph, user)   # 07-03, exercise 1
    return [v for v, d in distances.items() if d == k]

print(collaborators_at_distance(social, "anna", 2))  # ['david', 'elena']
print(collaborators_at_distance(social, "anna", 3))  # ['frank']

All the logic was already in bfs_distances: the application is a one-line filter. (We lose the mutual-contact tie-break; combining it with the original version's counting is left as an optional improvement.)

Solution 3: After reversing, the arrows point from each task toward its dependencies, so rank flows from the project's end back toward its foundations. Does design_schema or configure_server win... no: following the flow, rank accumulates in the tasks most transitively depended upon — with this graph, design_schema and design_ui receive the rank trickling down their chains, and the biggest beneficiary is design_ui, from which the heaviest branch hangs (the whole UI and, through the tests, the launch). Running it confirms the intuition: the "root" tasks of the long chains are the structurally critical ones, consistent with section 1's critical path.

Conclusion

We've watched graphs earn their keep: the TaskFlow scheduler (validate with cycles, order with Kahn, parallelize by levels, estimate with the critical path — the DAG's longest path via dynamic programming), social suggestions at distance 2, and a toy PageRank that distills the idea that sorted the web. None of it required new algorithms: just composing BFS, DFS, Kahn, and Dijkstra with the structures from the previous modules. One last step of the module remains, and it's all yours: an entire lesson of exercises to consolidate graphs from start to finish, from modeling to algorithms, once again with TaskFlow as the proving ground.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved