Push relabel is an algorithm that computes maximum flow in a flow network. It's considered one of the most efficient maximum flow algorithms that is able to achieve O(V^E) time complexity which is asymptopically more efficient than O(VE^2) Edmonds-Karp algorithm that adopts breadth-first search (BFS). (Source)
Debug Visualizer is used in this demonstration to better visualize the underlying implementation and data structure of Push-Relabel algorithm. Vertices are displayed with labels (Height : Excess Flow)
Graph Color Legend
- Red - Adjacent vertex that's selected to receive excess flow
- Light Gray - Vertex that's performing relabel
- Light Blue - Normal vertex in the graph
- Light Green - Currently selected vertex
- Light Yellow - Adjacent vertices of the currently selected vertex
- Light Pink - Source vertex
- Orange - Sink vertex
Demo
Since this application relies heavily on Debug Visualizer, breakpoints are required to be set in order to enter debug mode and notice what happens in each step of the algorithm.
Breakpoints
- Line 235 - Selects the destination vertex
- Line 237 - Shows which vertex has been selected with its adjacent vertices
- Line 288 - Shows which vertex has performed relabel to increase its height
- Line 303 - Reflects the changes of the graphs till none of the vertices have excess flow
- Line 307 - Shows which node is selected for relabeling
- Line 310 - Shows the current state of the graph prior to relabeling
- Line 358 - Shows the final max flow network graph with its corresponding residual graph
- Install Debug Visualizer
git clone https://github.com/jeraldlyh/smu-cs202-push-relabel- Select max_flow.py
- Set the respective breakpoints as shown in the setup
- Ctrl + Shift + P -> Debug: Start Debugging
- Ctrl + Shift + P -> Debug Visualizer: New View
- Enter GRAPH into input box
- Ctrl + Shift + P -> Debug Visualizer: New View
- Enter RESIDUAL_GRAPH into input box
- Shift + F10 to reflect changes in the graph