Graph Modeling Patterns - Learning Module

Loading content...

0/276

Modeling Dependencies and Constraints

When Order Matters

Many real-world problems involve dependencies—relationships where one thing must come before another:

You must complete prerequisites before taking a course
You must install dependencies before building a package
You must complete certain tasks before others in a project
You must compile source files in the right order

These aren't just lists—they're directed graphs where edges encode 'must come before' relationships. And the question 'in what order should I do things?' is answered by topological sorting—one of the most practically useful graph algorithms.

What You Will Learn

By the end of this page, you will understand how to model dependency relationships as directed graphs, detect circular dependencies (cycles), find valid orderings using topological sort, and apply these techniques to real-world problems like course scheduling, build systems, and task planning.

Dependency Graphs: The Foundation

A dependency graph is a directed graph where:

Vertices represent tasks, items, or entities
Directed edges represent dependencies: edge A → B means 'A must be completed before B' (or equivalently, 'B depends on A')

The direction of edges can be conceptualized two ways:

Convention 1: Prerequisite pointing to dependent

Edge from Course A to Course B means 'A is a prerequisite for B'
Edge direction: prerequisite → dependent

Convention 2: Dependent pointing to prerequisite

Edge from Course B to Course A means 'B depends on A'
Edge direction: dependent → prerequisite

Both are valid; be consistent and match the problem's specification.

Dependency Modeling Examples
Domain	Vertices	Edge Meaning	Question Asked
Course Schedule	Courses	A→B: A before B	Can all courses be completed?
Build System	Modules	A→B: A compiled before B	What order to compile?
Package Manager	Packages	A→B: A installed before B	Installation order?
Task Scheduling	Tasks	A→B: A done before B	Valid task sequence?
Spreadsheet Cells	Cells	A→B: A evaluated before B	Order to evaluate?
Makefile Targets	Targets	A→B: A built before B	Build order?

The Cycle Problem

If the dependency graph has a cycle (A depends on B, B depends on C, C depends on A), there's no valid ordering—you can never start! Detecting cycles is often as important as finding orderings. A graph with no cycles is called a Directed Acyclic Graph (DAG).

Topological Sort: Finding Valid Orderings

Topological sort produces a linear ordering of vertices in a DAG such that for every directed edge A → B, vertex A appears before vertex B in the ordering.

Key properties:

Only defined for DAGs (directed acyclic graphs)
May not be unique (multiple valid orderings may exist)
Can be computed in O(V + E) time

Two main algorithms exist:

1. Kahn's Algorithm (BFS-based)

Uses in-degree counting
Iteratively removes vertices with zero in-degrees
Naturally detects cycles (if not all vertices processed)

2. DFS-based Algorithm

Perform DFS, add vertices to result when finished (post-order)
Reverse the result for topological order
Detect cycles via back edges (visiting a vertex still in the current path)

Kahn's Algorithm (BFS)

•Compute in-degree for each vertex
•Add all zero in-degree vertices to queue
•While queue not empty: remove vertex, add to result, decrement neighbors' in-degrees
•If neighbor's in-degree becomes 0, add to queue
•Cycle exists if result size < V

DFS-based Algorithm

•Mark all vertices as unvisited
•For each unvisited vertex, run DFS
•In DFS: mark visiting, recurse on neighbors, mark visited, add to stack
•Cycle if we visit a 'visiting' vertex
•Pop stack for topological order

Kahn's Algorithm: BFS-based Topological Sort

Kahn's algorithm is intuitive: start with items that have no prerequisites, complete them, then their dependents become unblocked. Repeat until done.

The Algorithm:

Compute in-degree for each vertex
Add all vertices with in-degree 0 to a queue
While queue is not empty:
- Remove a vertex, add to result
- For each neighbor, decrement its in-degree
- If neighbor's in-degree becomes 0, add to queue
If result contains all vertices, return it; else cycle exists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from collections import deque, defaultdict
from typing import List
 
def find_course_order(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
    """
    Find a valid order to take all courses, or return empty if impossible.
    
    Input: prerequisites[i] = [a, b] means course b must be taken before course a
           (i.e., b → a in our graph, or 'b is a prerequisite for a')
    
    This is topological sort on a dependency graph.
    
    Time Complexity: O(V + E) where V = courses, E = prerequisites
    Space Complexity: O(V + E) for graph and in-degree array
    """
    # Build adjacency list and compute in-degrees
    graph = defaultdict(list)
    in_degree = [0] * num_courses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)  # prereq → course
        in_degree[course] += 1
    
    # Initialize queue with all courses having no prerequisites
    queue = deque()
    for course in range(num_courses):
        if in_degree[course] == 0:
            queue.append(course)
    
    result = []
    
    # Process courses in topological order
    while queue:
        course = queue.popleft()
        result.append(course)
        
        # "Taking" this course unblocks dependents
        for dependent in graph[course]:
            in_degree[dependent] -= 1
            if in_degree[dependent] == 0:
                queue.append(dependent)
    
    # Check if we processed all courses
    if len(result) == num_courses:
        return result
    else:
        return []  # Cycle exists - impossible to complete all
 
# Example: 4 courses with prerequisites
num_courses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
# Meaning: 0→1, 0→2, 1→3, 2→3
# i.e., 0 before 1, 0 before 2, 1 before 3, 2 before 3
 
order = find_course_order(num_courses, prerequisites)
print(f"Valid order: {order}")  # Output: [0, 1, 2, 3] or [0, 2, 1, 3]

Why Kahn's Detects Cycles

If a cycle exists, every vertex in the cycle has in-degree ≥ 1 (each depends on something in the cycle). These vertices will never reach in-degree 0, so they'll never be added to the queue. Thus, result.length < V indicates a cycle.

DFS-based Topological Sort with Cycle Detection

The DFS approach uses a key insight: in a DFS, a vertex is 'finished' (all descendants explored) only after all vertices it depends on are finished. By collecting vertices in reverse finish order, we get a topological sort.

Three-Color Marking:

White (0): Unvisited
Gray (1): Currently visiting (in the current DFS path)
Black (2): Finished processing

If during DFS we encounter a gray vertex, we've found a back edge—a cycle exists!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from collections import defaultdict
from typing import List
 
def can_finish_courses(num_courses: int, prerequisites: List[List[int]]) -> bool:
    """
    Determine if all courses can be finished (no circular dependencies).
    Uses DFS with three-color marking for cycle detection.
    
    Time Complexity: O(V + E)
    Space Complexity: O(V + E)
    """
    # Build adjacency list: course → [dependents]
    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)
    
    # Vertex states: 0 = unvisited, 1 = visiting, 2 = visited
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_courses
    
    def has_cycle(course: int) -> bool:
        """DFS from course, return True if cycle detected."""
        if color[course] == GRAY:
            return True  # Back edge - cycle!
        if color[course] == BLACK:
            return False  # Already fully explored
        
        color[course] = GRAY  # Mark as currently visiting
        
        for dependent in graph[course]:
            if has_cycle(dependent):
                return True
        
        color[course] = BLACK  # Mark as finished
        return False
    
    # Check for cycle starting from each course
    for course in range(num_courses):
        if color[course] == WHITE:
            if has_cycle(course):
                return False  # Cycle found
    
    return True  # No cycle, all courses can be finished
 
# Example with cycle
num_courses = 2
prerequisites = [[1, 0], [0, 1]]  # 0→1 and 1→0: cycle!
print(f"Can finish: {can_finish_courses(num_courses, prerequisites)}")  # False
 
# Example without cycle
prerequisites = [[1, 0]]  # 0→1 only
print(f"Can finish: {can_finish_courses(2, prerequisites)}")  # True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from collections import defaultdict
from typing import List
 
def topological_sort_dfs(num_vertices: int, edges: List[List[int]]) -> List[int]:
    """
    DFS-based topological sort returning the ordering.
    
    Returns empty list if cycle exists.
    """
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)  # u → v means u before v
    
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_vertices
    result = []
    has_cycle = False
    
    def dfs(vertex: int):
        nonlocal has_cycle
        if has_cycle:
            return
        
        color[vertex] = GRAY
        
        for neighbor in graph[vertex]:
            if color[neighbor] == GRAY:
                has_cycle = True
                return
            if color[neighbor] == WHITE:
                dfs(neighbor)
        
        color[vertex] = BLACK
        result.append(vertex)  # Add to result when finished
    
    for vertex in range(num_vertices):
        if color[vertex] == WHITE:
            dfs(vertex)
            if has_cycle:
                return []
    
    # Result is in reverse topological order
    return result[::-1]
 
# Example
edges = [[0, 1], [0, 2], [1, 3], [2, 3]]  # 0→1, 0→2, 1→3, 2→3
order = topological_sort_dfs(4, edges)
print(f"Topological order: {order}")  # [0, 2, 1, 3] or [0, 1, 2, 3]

Real-World Dependency Modeling

Dependency graphs and topological sort power critical systems across software engineering:

Industry Applications

•Build Systems (Make, Bazel, Gradle): Source files depend on headers/libraries. Determine compilation order. Detect circular dependencies that would cause infinite builds.
•Package Managers (npm, pip, apt): Packages depend on other packages. Install in order that satisfies all dependencies. Detect version conflicts and circular deps.
•Task Schedulers (Airflow, Luigi): Data pipeline tasks depend on upstream tasks. Schedule tasks so dependencies complete first. Detect cycles that would stall pipelines.
•Spreadsheet Engines (Excel, Sheets): Cells reference other cells. Evaluate in order that respects references. Detect circular references that can't be evaluated.
•Compiler Passes: Optimization passes have ordering requirements. Some passes produce information needed by others. Determine valid pass ordering.
•Database Migrations: Later migrations may depend on earlier ones. Apply in correct sequence. Detect schema conflicts.

Parallel Execution

Topological sort also reveals parallelization opportunities. Tasks at the same 'level' (no dependencies between them) can execute in parallel. Kahn's algorithm naturally groups tasks by level—all tasks added to the queue in the same round can run concurrently.

Advanced Dependency Patterns

Beyond basic topological sort, several advanced patterns appear in dependency modeling:

Pattern 1: Counting Valid Orderings

How many valid topological orders exist? This is useful for understanding flexibility in scheduling. The count can be computed with dynamic programming on the DAG.

Pattern 2: All Possible Orderings

Generate all valid topological orders. Use backtracking: at each step, choose any vertex with in-degree 0, recurse, then restore state.

Pattern 3: Lexicographically Smallest Order

Among all valid orderings, find the one that comes first alphabetically/numerically. Use a min-heap instead of a queue in Kahn's algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import heapq
from collections import defaultdict
from typing import List
 
def smallest_topological_order(n: int, edges: List[List[int]]) -> List[int]:
    """
    Find lexicographically smallest valid topological order.
    Uses min-heap instead of queue in Kahn's algorithm.
    
    Time Complexity: O((V + E) log V) due to heap operations
    Space Complexity: O(V + E)
    """
    graph = defaultdict(list)
    in_degree = [0] * n
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    # Use min-heap for lexicographic order
    min_heap = []
    for vertex in range(n):
        if in_degree[vertex] == 0:
            heapq.heappush(min_heap, vertex)
    
    result = []
    
    while min_heap:
        # Always pick smallest available vertex
        vertex = heapq.heappop(min_heap)
        result.append(vertex)
        
        for neighbor in graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                heapq.heappush(min_heap, neighbor)
    
    return result if len(result) == n else []
 
# Example
edges = [[0, 2], [1, 2], [2, 3]]
# Valid orders: [0,1,2,3] or [1,0,2,3]
# Lex smallest: [0,1,2,3]
order = smallest_topological_order(4, edges)
print(f"Lex smallest order: {order}")  # [0, 1, 2, 3]

Pattern 4: Minimum Semesters / Parallel Levels

What's the minimum time to complete all tasks if we can run independent tasks in parallel? This is the length of the longest path in the DAG—the critical path.

Pattern 5: Adding Minimum Edges for Connectivity

Given a disconnected dependency graph, what's the minimum edges to add to make it connected? This relates to finding connected components and spanning trees.

Case Study: Alien Dictionary

The 'Alien Dictionary' problem beautifully demonstrates extracting dependencies from implicit constraints:

Problem:

Given a sorted list of words from an alien language, derive the alphabetical order of characters in that language.

Example:

Words: ["wrt", "wrf", "er", "ett", "rftt"]
Since "wrt" comes before "wrf", we know 't' < 'f'
Since "wrt" comes before "er", we know 'w' < 'e'
Continue extracting constraints...
Answer: "wertf"

This is topological sort where we first extract the dependency edges from word comparisons!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from collections import defaultdict, deque
from typing import List
 
def alien_order(words: List[str]) -> str:
    """
    Derive character ordering from sorted alien dictionary.
    
    Step 1: Extract ordering constraints between characters
    Step 2: Build dependency graph
    Step 3: Topological sort for valid ordering
    
    Time Complexity: O(C) where C = total characters in all words
    Space Complexity: O(1) since alphabet is bounded (26 letters)
    """
    # Build graph and track all characters that appear
    graph = defaultdict(set)
    in_degree = {char: 0 for word in words for char in word}
    
    # Extract ordering constraints from adjacent words
    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        min_len = min(len(word1), len(word2))
        
        # Edge case: "abc" before "ab" is invalid (prefix should come first)
        if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
            return ""  # Invalid input
        
        # Find first differing character
        for j in range(min_len):
            if word1[j] != word2[j]:
                # word1[j] comes before word2[j]
                if word2[j] not in graph[word1[j]]:
                    graph[word1[j]].add(word2[j])
                    in_degree[word2[j]] += 1
                break  # Only first difference matters
    
    # Kahn's algorithm for topological sort
    queue = deque([char for char in in_degree if in_degree[char] == 0])
    result = []
    
    while queue:
        char = queue.popleft()
        result.append(char)
        
        for neighbor in graph[char]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check for cycle
    if len(result) != len(in_degree):
        return ""  # Cycle exists
    
    return ''.join(result)
 
# Example
words = ["wrt", "wrf", "er", "ett", "rftt"]
order = alien_order(words)
print(f"Alien alphabet order: {order}")  # "wertf"

Key Insight

The Alien Dictionary problem shows that dependencies aren't always given explicitly. Sometimes you must infer them from other constraints. The pattern: implicit constraints → explicit graph → topological sort, appears in many problems.

Summary: Dependencies as Graphs

Modeling dependencies as directed graphs enables powerful analysis of ordering relationships, cycle detection, and scheduling. Let's consolidate the key concepts:

Key Takeaways

•Dependencies form directed graphs — Tasks are vertices, 'must come before' relationships are edges.
•Cycles mean impossibility — A circular dependency cannot be satisfied. DAGs (acyclic graphs) are required for valid orderings.
•Topological sort finds valid orderings — Both Kahn's (BFS) and DFS approaches work in O(V + E).
•Kahn's algorithm is intuitive — Start with no-prerequisite items, remove them, repeat. Detects cycles naturally.
•DFS uses three-color marking — White/Gray/Black states detect cycles via back edges to gray vertices.
•Real-world applications abound — Build systems, package managers, task schedulers, spreadsheets all use these techniques.
•Dependencies can be implicit — Sometimes constraints must be extracted before building the graph (Alien Dictionary pattern).

Module Complete:

You have now mastered the core graph modeling patterns:

Converting problems to graphs — The general framework
Implicit graphs (state space) — Handling massive state spaces
Grid as graph — The ubiquitous 2D pattern
Dependencies as graphs — Ordering constraints and topological sort

These patterns transform seemingly diverse problems into applications of well-known graph algorithms—the hallmark of algorithmic thinking.

Page Complete

You now understand how to model dependencies and constraints as directed graphs, detect cycles that make problems unsolvable, and find valid orderings using topological sort. This completes the module on Common Graph Modeling Patterns—essential knowledge for recognizing graph structures in diverse problem domains.