liveBook · Manning

Active node

As explained in Algorithms Every Programmer Should Know

An active vertex is a vertex with positive excess flow that can undergo a push or relabel operation.

An active node is an intermediate vertex with positive excess flow. It needs to send that excess onward: it can push flow along a residual edge with a valid downhill height, or relabel when no such push is available. The source and sink are not treated as active nodes. section 10.4 section 10.1

Table 10.2 Node states after initialization
Node(u)
Height h(u)
Excess e(u)
Active State
Node 0(s)
4
0
Inactive (Source)
Node 1
0
10
Active
Node 2
0
5
Active
Node 3(t)
0
0
Inactive (Sink)

After source preflow, the table shows two intermediate nodes active with excesses of 10 and 5; the source and sink are inactive. section 10.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Traces active-node states through initialization and a four-node example, alongside the algorithm’s main loop.
Examples
Uses a water-system analogy and a four-node network whose intermediate nodes begin with excesses of 10 and 5.
What it assumes
Assumes a flow network with designated source and sink, edges with capacities, and vertex excess.
What you can do after
Apply push-relabel by selecting non-source, non-sink vertices with positive excess for push or relabel operations.
How it connects
Connects active nodes to preflow, excess flow, residual capacity, and the push-relabel algorithm.

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.