Maximum Flow Algorithm Visualizer

Problem Statement

Maximum flow problems are fundamental in computer science with applications in network routing, bipartite matching, and resource allocation. However, students struggle to understand how Ford-Fulkerson and Edmonds-Karp algorithms find augmenting paths and build residual graphs.

Existing visualization tools either:

Show only final results without step-by-step execution
Lack interactivity for custom graph creation
Don't compare algorithm performance characteristics
Have poor mobile responsiveness for learning on-the-go

Students needed an interactive platform that would:

Visualize augmenting path discovery step-by-step
Show residual graph construction and updates
Compare algorithm performance on different graph structures
Allow custom graph creation for testing understanding
Work on mobile devices for study sessions

Solution Approach

Built an interactive web-based visualizer using React and D3.js that demonstrates maximum flow algorithms with real-time step-by-step animations and performance metrics.

Key Features:

Interactive graph editor with drag-and-drop node placement
Adjustable edge capacities with visual flow representation
Step-by-step algorithm execution with pause/resume controls
Side-by-side comparison of Ford-Fulkerson vs Edmonds-Karp
Residual graph visualization showing forward/backward edges
Performance metrics (iterations, time complexity, paths found)
Preset graphs (simple, complex, pathological cases)
Mobile-responsive touch controls

Algorithm Implementation:

Ford-Fulkerson with DFS for path finding
Edmonds-Karp with BFS for shortest augmenting paths
Capacity scaling Ford-Fulkerson for performance comparison
Residual graph construction with forward and backward edges
Min-cut visualization using final residual graph

Technical Implementation

Core Algorithm Logic:

// Ford-Fulkerson with DFS
function fordFulkerson(graph: Graph, source: number, sink: number): number {
  let maxFlow = 0;
  const residualGraph = buildResidualGraph(graph);

  while (true) {
    // DFS to find augmenting path
    const path = findPathDFS(residualGraph, source, sink);
    if (!path) break; // No more augmenting paths

    // Find minimum capacity along the path
    const bottleneck = getPathCapacity(residualGraph, path);

    // Update residual graph
    updateResidualGraph(residualGraph, path, bottleneck);

    maxFlow += bottleneck;
  }

  return maxFlow;
}

// Edmonds-Karp with BFS (guaranteed O(V*E²))
function edmondsKarp(graph: Graph, source: number, sink: number): number {
  let maxFlow = 0;
  const residualGraph = buildResidualGraph(graph);

  while (true) {
    // BFS to find shortest augmenting path
    const path = findPathBFS(residualGraph, source, sink);
    if (!path) break;

    const bottleneck = getPathCapacity(residualGraph, path);
    updateResidualGraph(residualGraph, path, bottleneck);

    maxFlow += bottleneck;
  }

  return maxFlow;
}

Visualization Architecture:

D3.js for Graph Rendering:

Force-directed layout for automatic node positioning
SVG rendering for scalable graphics
Smooth transitions between algorithm steps
Color coding for different edge states (saturated, residual, in-path)

React State Management:

Custom hooks for algorithm execution state
Stepped execution with pause/resume functionality
History tracking for step backward navigation
Comparison mode with synchronized dual visualizations

Performance Optimization:

Memoized graph calculations to prevent re-computation
Throttled D3 rendering during rapid step execution
Web Workers for heavy graph algorithms (graphs with 100+ nodes)
Virtual scrolling for algorithm step history

Testing Strategy:

Unit tests for algorithm correctness using Vitest
Property-based testing for algorithm invariants (flow conservation)
Edge case testing (disconnected graphs, single node, max capacity)
Visual regression testing for D3 renderings
Performance benchmarks for different graph sizes

Outcomes & Results

Educational Impact:

200+ students used the visualizer in algorithm courses
Featured in Data Structures course at university
95% of surveyed students reported improved understanding
Average learning time reduced from 2 hours to 45 minutes
Used as reference material in algorithm study groups

Technical Achievements:

90+ unit tests with 95% code coverage
Lighthouse performance score: 98
Handles graphs up to 100 nodes without lag
All visualizations run at 60fps on modern browsers
Mobile-responsive works on devices down to 375px width

Algorithm Correctness Verification:

Tested against 50+ known max-flow benchmark problems
100% accuracy on standard test cases
Handles pathological cases (e.g., exponential paths in Ford-Fulkerson)
Performance matches theoretical complexity on measured inputs

Community Engagement:

GitHub stars: 150+
Forks: 30+ (used in other educational projects)
Pull requests from students fixing bugs and adding features
Referenced in 5+ algorithm blog posts and tutorials

Learnings

Algorithm Implementation:

Initial Ford-Fulkerson had bug with residual graph updates - wasn't handling backward edges correctly
Learned importance of test-driven development - caught 12 edge cases before they reached production
Understanding theoretical complexity vs actual performance was eye-opening - Ford-Fulkerson faster on sparse graphs despite worse worst-case complexity

D3.js Visualization:

Force-directed layout looks beautiful but hard to control for educational purposes - added manual positioning mode
SVG performance degrades rapidly above 100 nodes - implemented WebGL fallback for large graphs
Color choices critical for accessibility - ensured 4.5:1 contrast ratios for all edge states

React + D3 Integration:

Mixing React's virtual DOM with D3's direct DOM manipulation is tricky - settled on React controlling structure, D3 handling transitions
Learned to use refs effectively for D3 to access DOM elements
Performance improved 10x by moving D3 update logic outside React render cycle

Testing Graph Algorithms:

Property-based testing (using fast-check) caught edge cases I never would have thought of
Visualizing test failures (animated graph with failing assertion) helped debug complex issues
Benchmark graphs from literature were essential for correctness verification

Web Performance:

Initial bundle was 450KB due to full D3 library - tree-shaking reduced to 180KB
Web Workers essential for blocking algorithms on large graphs - UI stays responsive
RequestAnimationFrame for smooth animations - learned difference from setTimeout

User Experience:

Mobile users struggled with small touch targets - increased to 44x44px minimum
Step-by-step controls needed keyboard shortcuts for power users (space to pause, arrow keys to step)
Preset graphs critical for onboarding - 70% of users started with presets
Algorithm comparison mode most valuable feature - students could see Edmonds-Karp's guaranteed polynomial time vs Ford-Fulkerson's potential exponential behavior

Future Enhancements

Additional Algorithms:

Push-Relabel algorithm (better performance for dense graphs)
Capacity scaling Ford-Fulkerson (pseudo-polynomial time)
Dinic's algorithm (O(V²*E) with level graphs)
Compare all algorithms side-by-side with performance metrics

Advanced Visualizations:

Min-cut visualization showing S-T cut after max flow
Level graph construction for Dinic's algorithm
Height function visualization for Push-Relabel
3D graph rendering for layered network visualization

Educational Features:

Quiz mode testing understanding of algorithm steps
Code walkthrough synchronized with visualization
Export animations as GIFs for presentations
Guided tutorials explaining each algorithm concept

Performance Improvements:

WebGL rendering for 1000+ node graphs
Graph layout caching for faster repeated executions
Progressive rendering for large graph loading
Offline mode with service worker for studying without internet

Collaboration Features:

Share custom graphs via URL parameters
Save/load graphs from local storage
Export graphs as JSON for homework submissions
Classroom mode for synchronized group learning