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

Graph Exercises

Next ►
►

The module's entire theory is on the table: modeling (07-01), the Graph class (07-02), BFS/DFS/Kahn (07-03), Dijkstra and company (07-04), MST and Union-Find (07-05), and their applications (07-06). This lesson is practice from top to bottom: six progressive exercises, no new theory, built around a real TaskFlow project — the launch of its mobile app. Try to solve each one on your own before looking at the solution; the order matters, because each exercise reuses pieces from the previous one. You'll need the Graph class and the bfs, topological_order, and reverse functions from the earlier lessons.

Contents

  1. The starting project
  2. Exercise 1: build and query the project graph
  3. Exercise 2: the path with the fewest steps between two tasks
  4. Exercise 3: detect and list the dependency cycle
  5. Exercise 4: execution order with priority tie-breaking
  6. Exercise 5: task islands (independent projects)
  7. Exercise 6: the grid as an implicit graph
  8. Solutions

The starting project

The team is planning the mobile app launch in TaskFlow. These are the tasks (with their priority, 1 = highest) and their dependencies, in plain language:

Task Priority Depends on
define_scope 1 —
design_screens 2 define_scope
choose_stack 1 define_scope
implement_login 2 design_screens, choose_stack
implement_board 1 design_screens, choose_stack
connect_api 1 implement_login, implement_board
usability_tests 2 connect_api
prepare_marketing 3 —
publish_store 1 usability_tests, prepare_marketing 
graph LR
    A[define_scope] --> B[design_screens]
    A --> C[choose_stack]
    B --> D[implement_login]
    C --> D
    B --> E[implement_board]
    C --> E
    D --> F[connect_api]
    E --> F
    F --> G[usability_tests]
    M[prepare_marketing] --> H
    G --> H[publish_store]

Exercise 1: build and query the project graph

Build the mobile graph with the Graph class (remember the module's convention: add_edge(A, B) = "B depends on A") and a priorities dictionary with each task's priority. Then answer with code: (a) which tasks can start right away (in-degree 0)?; (b) how many tasks does choose_stack directly unblock, and which ones?; (c) is publish_store the only "final" task (out-degree 0)?

Exercise 2: the path with the fewest steps between two tasks

The project lead asks: "what is the shortest dependency chain leading from define_scope to publish_store?". Write shortest_path_steps(graph, source, target) returning the list of tasks along the path with the fewest edges (or None if no path exists). Hint: BFS storing predecessors, and backward reconstruction as in Dijkstra (07-04) — but with no heap: there are no weights here.

Exercise 3: detect and list the dependency cycle

A distracted user adds two new dependencies: user feedback comes after publishing (publish_store → user_feedback) and, in the rush, declares that the screen design depends on that feedback (user_feedback → design_screens). The project deadlocks. has_cycle (07-03) only returns True; for a useful error message, TaskFlow needs to show the cycle. Write find_cycle(graph) returning the list of the cycle's vertices (ending with the starting vertex repeated), or None if there is none. Hint: in the white/gray/black DFS, additionally keep the path list of gray vertices; when you bump into a gray one, the cycle is the stretch of path starting at that vertex.

Exercise 4: execution order with priority tie-breaking

topological_order (Kahn) chooses arbitrarily among the available tasks. The team wants something better: among the tasks runnable at each moment, the highest-priority one first (lowest number; on equal priority, alphabetical order). Write topological_order_priority(graph, priorities) replacing Kahn's deque with module 4's heapq using (priority, id) tuples. Apply it to the mobile graph (without exercise 3's edges) and compare prepare_marketing's position with what a plain queue would give it.

Exercise 5: task islands (independent projects)

The mobile graph gains the tasks of another workstream: redesign_logo → update_website and update_website → press_release, plus one loose task with no relationships, renew_domain. Write task_islands(graph) returning the connected components (ignoring the arrows' direction, as in 07-03) sorted from largest to smallest, and use it to answer: how many independent projects coexist on the board, and how big is each one?

Exercise 6: the grid as an implicit graph

TaskFlow's office is trying out a package-delivery robot that moves through a gridded warehouse: . is open floor, # a shelf, S the robot's starting point and M the destination desk:

warehouse = [
    "S.#.",
    ".#..",
    "....",
    "#.#M",
]

Compute the minimum number of moves (up/down/left/right) from S to M with BFS... without building any Graph object. The grid already is a graph: every open cell is a vertex and its neighbors are computed on the fly by looking at the four adjacent squares. This implicit graph pattern matters enormously: it shows that BFS only needs to know "give me v's neighbors", not any particular structure.

Solutions

Solution 1

mobile = Graph(directed=True)
mobile_dependencies = [
    ("define_scope", "design_screens"),
    ("define_scope", "choose_stack"),
    ("design_screens", "implement_login"),
    ("choose_stack", "implement_login"),
    ("design_screens", "implement_board"),
    ("choose_stack", "implement_board"),
    ("implement_login", "connect_api"),
    ("implement_board", "connect_api"),
    ("connect_api", "usability_tests"),
    ("usability_tests", "publish_store"),
    ("prepare_marketing", "publish_store"),
]
for source, target in mobile_dependencies:
    mobile.add_edge(source, target)

priorities = {
    "define_scope": 1, "design_screens": 2, "choose_stack": 1,
    "implement_login": 2, "implement_board": 1, "connect_api": 1,
    "usability_tests": 2, "prepare_marketing": 3, "publish_store": 1,
}

# (a) in-degree 0: can start today
degrees = mobile.in_degrees()
print([t for t, d in degrees.items() if d == 0])
# ['define_scope', 'prepare_marketing']

# (b) direct unblocks of choose_stack
print(mobile.out_degree("choose_stack"), list(mobile.neighbors("choose_stack")))
# 2 ['implement_login', 'implement_board']

# (c) final tasks: out-degree 0
print([t for t in mobile.vertices() if mobile.out_degree(t) == 0])
# ['publish_store']  -> yes, it's the only one

Comments: every task appears in some edge, so no explicit add_vertex was needed — but always double-check that assumption (here, exercise 5's renew_domain will break it). The answers come straight from the class's methods, no algorithm involved: modeling well already answers questions.

Solution 2

from collections import deque

def shortest_path_steps(graph, source, target):
    if source == target:
        return [source]
    predecessor = {source: None}         # doubles as the visited set (07-03)
    queue = deque([source])
    while queue:
        current = queue.popleft()
        for neighbor in graph.neighbors(current):
            if neighbor not in predecessor:
                predecessor[neighbor] = current
                if neighbor == target:   # arrived: we can stop right here
                    path = [target]
                    while predecessor[path[-1]] is not None:
                        path.append(predecessor[path[-1]])
                    return path[::-1]    # rebuilt backwards, as in 07-04
                queue.append(neighbor)
    return None                          # queue empty, never arrived: unreachable

print(shortest_path_steps(mobile, "define_scope", "publish_store"))
# ['define_scope', 'design_screens', 'implement_login',
#  'connect_api', 'usability_tests', 'publish_store']

Comments: the predecessor dict plays two roles (marking visited and remembering the path), just like in Dijkstra but without weights or a heap. Being able to cut out as soon as the target is reached is a luxury exclusive to BFS: the first visit guarantees the minimum number of edges. There are two 5-edge paths (via login or via the board); BFS returns whichever it discovers first, and both are correct.

Solution 3

def find_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in graph.vertices()}
    path = []                                    # the gray vertices, in order

    def visit(v):
        color[v] = GRAY
        path.append(v)
        for neighbor in graph.neighbors(v):
            if color[neighbor] == GRAY:          # edge back into the current path
                start = path.index(neighbor)     # where the cycle begins
                return path[start:] + [neighbor]
            if color[neighbor] == WHITE:
                cycle = visit(neighbor)
                if cycle:
                    return cycle                 # propagate the find upward
        path.pop()                               # backtracking: v leaves the path
        color[v] = BLACK
        return None

    for v in graph.vertices():
        if color[v] == WHITE:
            cycle = visit(v)
            if cycle:
                return cycle
    return None

mobile.add_edge("publish_store", "user_feedback")
mobile.add_edge("user_feedback", "design_screens")
print(find_cycle(mobile))
# ['design_screens', 'implement_login', 'connect_api',
#  'usability_tests', 'publish_store', 'user_feedback', 'design_screens']

# clean up for the next exercises (remove_edge: exercise 2 of 07-02)
mobile.remove_edge("publish_store", "user_feedback")
mobile.remove_edge("user_feedback", "design_screens")

Comments: the only novelty over has_cycle (07-03) is the path list, which grows on painting gray and shrinks on backtracking — an explicit stack, module 3, portraying the DFS's current branch at all times. On bumping into a gray vertex, the stretch from its position is exactly the cycle; the repeated vertex is appended at the end so the user-facing message reads as a closed circle. With this list, TaskFlow can display: "cannot add the dependency: design_screens → ... → user_feedback → design_screens".

Solution 4

import heapq

def topological_order_priority(graph, priorities):
    degrees = graph.in_degrees()
    heap = [(priorities[v], v) for v, d in degrees.items() if d == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        _, current = heapq.heappop(heap)         # the highest-priority runnable
        order.append(current)
        for neighbor in graph.neighbors(current):
            degrees[neighbor] -= 1
            if degrees[neighbor] == 0:
                heapq.heappush(heap, (priorities[neighbor], neighbor))
    if len(order) < len(degrees):
        raise ValueError("There is a dependency cycle")
    return order

priorities["user_feedback"] = 3          # left behind as a vertex after exercise 3
print(topological_order_priority(mobile, priorities))
# ['define_scope', 'choose_stack', 'design_screens', 'implement_board',
#  'implement_login', 'connect_api', 'usability_tests',
#  'prepare_marketing', 'publish_store', 'user_feedback']

Comments: it's Kahn to the letter with the deque swapped for a heap — the same queue→priority-queue substitution that turned the Queue into the UrgentInbox in module 4. The (priority, id) tuples break ties on their own: first by number, then alphabetically, with no need for module 4's counter because the ids are comparable strings. Look at prepare_marketing: it's runnable from minute one, but its priority 3 pushes it back to the end (it only comes out when it's the sole option); a FIFO queue would have run it second or third. The order remains topologically valid: the heap only ever contains tasks with all their dependencies satisfied.

Solution 5

mobile.add_edge("redesign_logo", "update_website")
mobile.add_edge("update_website", "press_release")
mobile.add_vertex("renew_domain")                # no edges: explicit registration!

def task_islands(graph):
    und = Graph(directed=False)                  # version without arrow directions
    for v in graph.vertices():
        und.add_vertex(v)
        for target in graph.neighbors(v):
            und.add_edge(v, target)
    visited, islands = set(), []
    for v in und.vertices():
        if v not in visited:
            island = bfs(und, v)                 # v's entire component
            visited.update(island)
            islands.append(island)
    return sorted(islands, key=len, reverse=True)

for island in task_islands(mobile):
    print(len(island), island)
# 9 ['define_scope', ..., 'usability_tests', 'publish_store']
# 3 ['redesign_logo', 'update_website', 'press_release']
# 1 ['user_feedback']
# 1 ['renew_domain']

Comments: four islands — the mobile app (9 tasks), the brand campaign (3), and two loose tasks. Surprised by user_feedback? In exercise 3 we removed its two edges, but the vertex stayed registered: it now shows up as its own island, a reminder that V and E are independent sets (07-01). Two more details to watch: the conversion to undirected before searching for components (with the arrows, publish_store wouldn't "see" prepare_marketing), and the explicit registration of renew_domain, which with no edges wouldn't exist in the graph — the classic mistake from 07-02. A perfectly valid alternative: UnionFind (07-05), unioning the endpoints of every edge; the final roots are the islands.

Solution 6

from collections import deque

def min_steps(grid):
    rows, cols = len(grid), len(grid[0])
    for r in range(rows):                        # locate S and M
        for c in range(cols):
            if grid[r][c] == "S":
                start = (r, c)
            elif grid[r][c] == "M":
                goal = (r, c)

    visited = {start}                            # module 5's set of tuples
    queue = deque([(start, 0)])                  # (cell, steps to reach it)
    while queue:
        (r, c), steps = queue.popleft()
        if (r, c) == goal:
            return steps
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:   # the 4 directions
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols           # inside the board
                    and grid[nr][nc] != "#"                 # not a shelf
                    and (nr, nc) not in visited):
                visited.add((nr, nc))                       # mark when enqueueing
                queue.append(((nr, nc), steps + 1))
    return None                                  # M unreachable

print(min_steps(warehouse))   # 6

Comments: it's the bfs from 07-03 with two cosmetic changes: the vertices are (row, column) tuples — hashable, which is why they work as set elements — and the "neighbors" are read from no adjacency list: they're generated on the fly by adding the four offsets and filtering out bounds and walls. One optimal 6-step path: (0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (2,3) → (3,3); check it by drawing on the grid. The underlying lesson: BFS doesn't need the Graph class, only a neighbors function. Game maps, puzzle states, document versions: anything with "states and transitions" is an implicit graph, and the entire module applies to it.

Common Mistakes and Tips

  • Building edges with the convention inverted. If you write add_edge("design_screens", "define_scope") thinking "depends on", every subsequent algorithm will work on an upside-down project. Re-read each edge as "finishing A unblocks B" before moving on.
  • Forgetting vertices with no edges (renew_domain): they don't show up in islands, orderings, or counts. Explicit registration, always.
  • path.index(neighbor) on huge graphs is O(path length); in production you'd also store each gray vertex's position in a dict. For understanding the algorithm, the clear version wins.
  • Testing only the happy path. Run shortest_path_steps with an unreachable target, find_cycle on the clean graph, and the warehouse with the goal walled off: half of all real-world bugs live in the Nones.
  • The module's final tip: when a new problem baffles you, ask yourself "what are the vertices here, and what are the edges?". That's the question that turns robots into grids, tasks into DAGs, and users into networks — and once it's answered, the algorithms are always this module's same six.

Conclusion

Six exercises and one whole project later, graphs have gone from concept to tool: you've built and queried the graph of a real launch, found the shortest dependency chain with BFS and predecessors, turned "there is a cycle" into an error message that shows the cycle, made Kahn respect priorities with module 4's heap, split the board into independent projects, and discovered that even a gridded warehouse is a graph if you ask it the right question.

And with that, something bigger: TaskFlow is structurally complete. Look back over what the course has built — the board on arrays and linked lists, undo with stacks, notifications and urgencies with queues and heaps, instant indexes with hash tables, hierarchies with trees and, since this module, dependencies, orderings, and routes with graphs. No fundamental piece remains unknown. What remains is judgment: facing a new problem, which structure do you choose and why? That is exactly the subject of module 8: looking back with perspective, learning to choose a structure with cost and design arguments, and rounding off the course with resources to keep going and final projects that bring together everything you've learned.

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