Counting Paths and Graph Algorithms: A Dynamic Programming Approach Inspired by Ginny Weasley's Network

Introduction: From Hogwarts to Graph Theory

In the magical world of Harry Potter, Ginny Weasley often finds herself solving complex problems. In CSCI 3104 Problem Set 8, she tackles network path counting, shortest path trees, and graph conversions. These problems are not just wizardry—they reflect real challenges in computer science, from social network analysis to navigation apps. In this tutorial, we'll explore dynamic programming for path counting, compare graph representations, and learn how to simplify multigraphs efficiently. Whether you're a student studying for exams or a developer optimizing algorithms, these concepts are essential.

Dynamic Programming for Path Counting

Ginny's first task is to count the number of paths from node 1 to node 14 in a directed graph. A path must contain at least one edge. Using dynamic programming, we can compute the number of paths from each node to the target (node 14) by processing nodes in reverse topological order. The recurrence is: dp[v] = sum_{v -> u} dp[u], with dp[14] = 1 (base case: one path from 14 to itself, but since paths require at least one edge, we adjust). Actually, for paths from v to 14, we set dp[14] = 1 representing the empty path? Wait, let's clarify: The problem defines a path as having at least one edge. So from 14 to 14, there is no path (0). But we can handle this by initializing dp[14] = 1 as a sentinel, then subtract 1 at the end for the start node if needed. Alternatively, we can compute paths of length >=1 by using DP and then for node 1 we subtract 1 if there is a direct path? Actually, the standard DP counts all paths including zero-length. To exclude zero-length, we can simply not count the trivial path. In our implementation, we'll set dp[14] = 0 (no path from 14 to 14 with at least one edge) and then for each predecessor, add dp[neighbor] plus 1 if there is a direct edge? That gets messy. Simpler: Use DP that counts all paths (including zero-length) and then subtract 1 for the start node if we want only paths with at least one edge. But the problem says "path must have at least one edge", so from node 1 to 14, we count only paths with at least one edge. The DP from 14 down to 1: Let f(v) = number of paths from v to 14 with at least one edge. Then f(14) = 0. For any other v, f(v) = sum_{v->u} (1 + f(u))? No, because a path from v to 14 can be a single edge v->14 (if exists) or a path v->u->...->14. So f(v) = (1 if v->14 exists else 0) + sum_{v->u, u != 14} f(u). But this still counts paths that might go through 14? Actually, if there is an edge v->14, that's a path of length 1. For longer paths, we need to count paths that start with v->u and then continue to 14. So f(v) = sum_{v->u} (1 if u==14 else f(u)). That works. But the hint says "fill in a table that counts number of paths from each node j to 14, starting from 14 down to 1". So they likely use DP where dp[14] = 1 (counting the trivial path) and then for each node, dp[v] = sum_{v->u} dp[u], and then at the end, for node 1, they subtract 1 to exclude the trivial path? But the trivial path only exists from 14 to 14, not from 1 to 14. So actually, dp[v] as defined counts all paths (including zero-length) from v to 14. For v != 14, the zero-length path doesn't exist because you can't stay at v and be at 14. So dp[v] automatically counts only paths with at least one edge for v != 14. So the only issue is that dp[14] = 1 counts a zero-length path, but we don't care about paths starting at 14. So we can just compute dp[14] = 1 and then for each node v in reverse topological order, dp[v] = sum_{v->u} dp[u]. Then the answer for number of paths from 1 to 14 is dp[1]. That works because there is no path of length zero from 1 to 14. So we'll use that.

Let's illustrate with a small example. Suppose we have nodes 1,2,3,4 with edges: 1->2, 1->3, 2->4, 3->4. Target is 4. Compute dp[4]=1. Then dp[3] = dp[4] = 1, dp[2] = dp[4] = 1, dp[1] = dp[2] + dp[3] = 2. So there are 2 paths from 1 to 4: 1-2-4 and 1-3-4. Correct.

For Ginny's network (which we don't have the exact edges), she would list all nodes from 14 down to 1, compute dp using adjacency lists. This is O(V+E) time and O(V) space.

Shortest Path Trees vs. DFS Trees

In problem 2, Ginny needs a directed graph where a set of tree edges forms a shortest path tree but cannot be produced by any DFS. This highlights that DFS trees depend on edge order, while shortest path trees are based on distances. For example, consider a graph with vertices s, a, b, and edges: s->a (weight 1), s->b (weight 1), a->b (weight 1). The shortest path tree with edges (s->a, s->b) is valid because distances: d(s)=0, d(a)=1, d(b)=1. But DFS from s could produce tree edges (s->a, a->b) if adjacency list order puts a before b. The tree (s->a, s->b) cannot be produced by any DFS because DFS always follows a path until dead end; it would never have two children from s unless it backtracks? Actually, DFS from s can have multiple children if it visits s, then explores a completely, then backtracks to s and then visits b. That would give tree edges (s->a, s->b). So that example doesn't work. A correct example: vertices s, a, b, c. Edges: s->a (1), s->b (1), a->c (1), b->c (1). Shortest path tree: (s->a, s->b) gives distances: d(s)=0, d(a)=1, d(b)=1, d(c)=2 (via either a or b). But DFS from s: if adjacency list order is a then b, DFS goes s->a->c, then back to s, then s->b. Tree edges: s->a, a->c, s->b. That's a different set. To get tree edges (s->a, s->b), DFS would need to visit s, then go to a, but then immediately backtrack to s without exploring a's children? That's not possible because DFS explores all reachable vertices from a before backtracking. So (s->a, s->b) cannot be a DFS tree because from a, DFS must explore at least one outgoing edge (if any). Since a has an edge to c, DFS would include a->c. Therefore, the tree (s->a, s->b) is a shortest path tree but not a DFS tree. This satisfies the requirements.

Graph Representations: Degrees Computation

Professor Dumbledore needs in- and out-degrees for all vertices in a directed multigraph. The efficiency depends on representation:

• Adjacency matrix: O(V^2) time to scan all entries, O(V^2) space. For each vertex, sum row for out-degree, column for in-degree.
• Edge list: O(E) time to count degrees by iterating edges, O(V+E) space for storing degrees. But if vertices have arbitrary labels, we need a hash map to map labels to indices, adding O(V) overhead.
• Adjacency list: O(V+E) time to traverse lists: for each vertex, out-degree is length of its list; in-degree requires scanning all lists or maintaining reverse list. If we have both in and out adjacency lists, O(V+E). Otherwise, we can compute in-degrees by initializing array to zero and for each edge (u,v), increment in-degree of v. That's O(V+E) time and O(V) space.

Thus, adjacency list is most efficient for this task.

Converting Directed Multigraph to Simple Graph

The magical parrot problem: Convert a directed multigraph G to a simple graph G' by removing duplicate edges and self-loops. Given adjacency lists, we need O(V+E) time and space. Algorithm: For each vertex u, create a boolean array or hash set to track neighbors already added. Since vertices are numbered 1..V, we can use a boolean array visited of size V+1, initialized to false. For each u, iterate its adjacency list. For each neighbor v, if v == u, skip (self-loop). Else, if not visited[v], add v to new list and set visited[v]=true. After processing u, reset visited for the neighbors we added (or reuse a timestamp technique). Resetting visited for each u would be O(V+E) if we reset only the neighbors we touched. Alternatively, use an integer array lastVisited with a counter. Initialize lastVisited[v]=0 for all v. Use a global counter. For each u, increment counter. For each neighbor v, if v != u and lastVisited[v] != counter, then add v to new list and set lastVisited[v]=counter. This avoids resetting. Then build new adjacency lists. This runs in O(V+E) time and O(V) extra space for the array.

Pseudocode:

function simplify(G):
    V = number of vertices
    newAdj = array of empty lists of size V+1
    lastVisited = array of zeros of size V+1
    counter = 0
    for u from 1 to V:
        counter += 1
        for v in G.adj[u]:
            if v != u and lastVisited[v] != counter:
                lastVisited[v] = counter
                newAdj[u].append(v)
    return newAdj

Proof of correctness: The algorithm ensures each directed edge (u,v) with u!=v appears exactly once in newAdj[u] because we only add v if it hasn't been added for this u in the current pass. Self-loops are skipped. So G' is a simple directed graph.

Time: O(V+E) because we iterate each edge once. Space: O(V) for lastVisited, plus output adjacency lists which contain at most E edges (but actually at most V^2, but in practice O(E) if many duplicates? The problem asks for O(V+E) space, and the output graph has at most E edges, so it's O(V+E).

Conclusion: Graph Algorithms in the Wizarding World and Beyond

From Ginny's path counting to Dumbledore's degree calculations, these graph problems teach fundamental algorithmic techniques. Dynamic programming, representation choices, and efficient transformations are crucial in fields like social network analysis, route planning, and data processing. By understanding these concepts, you can solve complex problems in both magical and real-world contexts.