7.3 DAG, Strongly Connected Components and Network Flow: From Dependency Sorting to Resource Allocation

Building systems requires sorting dependencies, module analysis must resolve cyclic references, and schedulers need to assign tasks to machines. All of these problems are modeled using graphs, but they require different structures: DAGs, strongly connected components, flow networks, and bipartite graphs.

DAG and Topological Order

A directed acyclic graph (DAG) contains no directed cycles. A topological order is a linear arrangement of vertices such that for every edge u→v, vertex u appears before vertex v.

A topological order exists if and only if the finite directed graph is a DAG.

Kahn's Algorithm

Compute the in-degree of each vertex
Enqueue all vertices with in-degree 0

while queue is not empty:
  Dequeue vertex v and append to result
  For each edge v→u:
    decrement indegree[u]
    if indegree[u] becomes 0, enqueue u

If the final output contains fewer than |V| vertices, the remaining vertices form a cycle.

Multiple vertices with in-degree zero indicate that a topological order may not be unique. The choice of queue, heap, or stable sorting strategy affects the resulting order; if a deterministic sequence is required, a tie-breaker rule must be explicitly specified.

DFS Method

Push the vertex onto the sequence when the DFS traversal exits that vertex, then reverse the sequence to obtain a topological order of the DAG. A cycle must be detected during traversal; the reverse order of exit vertices in a cyclic graph is not a valid topological order.

Dependency Edge Direction Must Be Agreed Upon

"A depends on B" can be represented as:

A→B   // from dependent to dependency

Alternatively, it can be written as:

B→A   // from prerequisite to subsequent item

To ensure that topological order directly yields a build sequence, B→A is typically used. The algorithm does not understand business semantics; reversing the direction results in an inverse order that still appears valid.

Strongly Connected Components Compression Cycle

In a directed graph, if node u can reach node v and node v can reach node u, then the two nodes belong to the same strongly connected component (SCC). Mutual reachability defines an equivalence relation, so SCCs partition the vertices into disjoint blocks.

By collapsing each SCC into a single supervertex, the resulting condensed graph is guaranteed to be a DAG. If the condensed graph contained a cycle, it would imply that the corresponding components should have been merged into a larger SCC, contradicting the definition of SCCs.

Applications include:

• Reporting cyclic modules as a single unit;
• Analyzing mutually reachable regions in state machines;
• Sorting components on a DAG for dependency resolution;
• Identifying the strongly connected core of a web graph.

Kosaraju's algorithm uses two DFS passes; Tarjan's uses a single DFS with low-link values and a stack. Both achieve O(V+E) time complexity on adjacency lists, though with different constant factors and implementation details.

Flow Networks

A flow network includes:

• a source node s;
• a sink node t;
• a capacity c(u,v)≥0 for each directed edge;
• a flow value f(u,v).

Constraints:

0 ≤ f(u,v) ≤ c(u,v)

Flow conservation holds for all nodes except the source and sink:

Σ incoming flows = Σ outgoing flows

The goal of maximum flow is to maximize the total amount of flow from the source to the sink.

Residual Networks and Augmenting Paths

After sending some flow, the residual network shows how the flow can still be adjusted:

• Forward residual: unused capacity;
• Backward residual: allows reversal of previously sent flow.

Find an augmenting path s→t in the residual network, and increase the flow along the path by the minimum residual capacity; backward edges enable the algorithm to correct earlier decisions.

Ford–Fulkland is the overarching method framework; termination and complexity depend on the path selection strategy and the type of capacities. Edmonds–Karp selects the shortest augmenting path each time using BFS, yielding a polynomial-time bound of O(VE²). For larger instances, algorithms like Dinic’s or push-relabel are commonly used.

Maximum Flow Minimum Cut

A s-t cut partitions the vertices into:

s∈S, t∈T, S∪T=V

The cut capacity is the sum of the edge capacities from S to T. No flow can exceed the capacity of any cut.

Maximum Flow Minimum Cut Theorem:

Maximum flow value = Minimum cut capacity

This theorem provides a certificate of algorithmic optimality and reveals the bottleneck edges. In network throughput analysis, the minimum cut represents the model's capacity bottleneck; real systems must also account for latency, shared resources, and time-varying capacity.

Bipartite Matching

Bipartite graph vertices are divided into L and R; edges only connect vertices across the two sets. A matching is a set of edges with no shared endpoints.

Task, machine assignment:

L: tasks
R: machines
Edge: a machine can execute a given task

This can be transformed into a flow network:

s → each task, capacity 1
Each task → compatible machines, capacity 1
Each machine → t, capacity 1

Under integer capacities, the maximum flow problem has an integer solution, and flows of value 1 on task–machine edges form a maximum matching.

If a machine can handle multiple tasks, increase the capacity from the machine to the sink. If tasks and machines have preference weights, the problem becomes a weighted matching or a minimum-cost flow problem, and the standard maximum flow formulation no longer captures the objective.

The Hopcroft–Karp algorithm can compute a maximum matching in a bipartite graph in O(E√V). Whether it's worth using depends on the scale and the implementation environment.

Hall's Theorem gives the condition for a perfect matching

A bipartite graph G=(L,R,E) has a matching that covers all vertices in L if and only if for any subset S⊆L:

|N(S)| ≥ |S|

N(S) is the set of all neighbors of S on the right side. Intuitively, any group of tasks must collectively have at least as many candidate machines as tasks, otherwise, there's not enough capacity to assign them all.

Checking every subset individually is infeasible, but maximum matching algorithms efficiently determine whether a matching exists or reveal a bottleneck.

Sources of Distortion in Graph Models

• Treating dynamic capacity as a static constant;
• Using unilateral representations for protocols that require mutual acknowledgment;
• Ignoring multiple shared resource dimensions on a single machine;
• Misrepresenting parallelizable tasks as a total order;
• Optimizing throughput with maximum flow algorithms while neglecting latency and fairness;
• Focusing solely on compatibility in matching, without encoding cost, quotas, or affinity.

Algorithms address specific graph problems. Model validation is just as critical as algorithmic correctness.

Completion Check

1. Compute the strongly connected components (SCCs) and condense the DAG for a module graph with cyclic dependencies;
2. Use the Kahn algorithm to produce two valid topological orders;
3. Construct a small flow network and manually determine the maximum flow and minimum cut;
4. Translate the compatibility relationships among three tasks and three machines into a flow network;
5. Apply Hall's condition to explain why a perfect matching does not exist in a given example;
6. Explain what a standard maximum flow solution misses when applied to weighted task assignment.

References

• MIT OpenCourseWare: Introduction to Algorithms