Max Flow Explorer

Interactive TypeScript flow-network visualizer with augmenting paths, flow decomposition, minimum-cut certification, and an offline Android app.

Download Android APK

Overview

Max Flow Explorer is an interactive educational app for building directed flow networks and understanding how maximum flow is computed.

It does not stop at the final numeric answer. It shows the actual structure of the solution:

• the graph you build
• the capacities and current flow on each edge
• the augmenting paths used during the computation
• the final flow decomposition
• the induced minimum cut
• the certificate that max flow = min cut

The project is available in two forms:

• a browser-based web app
• an Android app packaged as an APK, running fully offline through a local WebView

Android App

An Android version is included in this repository.

Download

• Download the latest debug APK

What the Android app includes

• offline execution
• local assets bundled inside the APK
• touch-friendly graph interaction
• draggable nodes
• dedicated mobile graph focus mode for fixed-screen node editing

The Android app does not depend on an external backend or internet connection.

Why This Project Exists

Maximum flow is often presented as an algorithmic procedure, but many learners struggle to connect the theory with what is really happening in the graph.

This project makes the process visible.

You can see:

• how flow is pushed
• when backward residual moves appear
• how the final flow can be decomposed into paths
• how the minimum cut is induced from the final residual graph
• why the final value is mathematically certified

Main Features

Graph Construction

• add and remove nodes
• add and remove directed edges
• assign both capacity and initial flow to every edge
• choose source and sink explicitly
• reset flows only, or delete the full graph

Continuous Validation

• flow conservation is checked live while building the graph
• conservation is enforced only on internal nodes
• source and sink are excluded from the conservation constraint
• maximum flow computation is blocked if an internal node is unbalanced

Visual Interaction

• SVG-based graph rendering
• cleaner edge routing for better readability
• draggable nodes with real-time edge updates
• mobile focus mode for easier node movement on Android
• visual partition of the induced minimum cut directly on the graph

Algorithmic Output

• maximum flow computation
• augmenting paths
• explicit display of backward residual steps such as S -> A <- B -> T
• final source-to-sink flow decomposition
• induced minimum cut with source-side set, sink-side set, and cut edges

Certificate of Correctness

After computing the maximum flow, the app derives the minimum cut from the final residual graph:

• start from the source
• find every node still reachable in the residual graph
• form the source-side set and the complementary sink-side set
• collect the outgoing cut edges
• sum their capacities

This produces the certificate:

maximum flow value = minimum cut capacity

What You Can Learn with It

Augmenting Paths

The app shows the actual augmenting paths found during the algorithm, including residual backward moves.

Example:

S -> A <- B -> T

This is important because a correct maximum-flow explanation must show not only direct residual moves, but also the cases where existing flow is rearranged through backward residual edges.

If no augmenting path uses backward residual edges, the app states that explicitly.

Final Flow Decomposition

Once the final flow is reached, the app decomposes it into source-to-sink paths with corresponding flow values.

This separates:

• the paths used during the algorithm
• the paths that represent the final solution

Induced Minimum Cut

The minimum cut is not drawn arbitrarily.

It is built from the standard induced construction:

• reachable nodes from the source in the final residual graph
• complementary set containing the sink
• cut edges going from the source side to the sink side
• capacity equal to the maximum flow value

This is the core theoretical certificate behind the result.

Web Version

The web app is lightweight and runs entirely client-side.

Tech Stack

• TypeScript source code
• plain HTML and CSS
• SVG rendering
• no backend

Running Locally

You can open the web app directly:

• index.html

Or serve it locally:

cd /Users/simoneremoli/max-flow-app
python3 -m http.server 8000

Then open:

http://localhost:8000

Android Project

The Android wrapper lives in the android/ folder and loads the app from local bundled assets.

Key points:

• built with Gradle
• uses Android WebView
• works offline
• includes the project logo as app icon

Project Structure

max-flow-app/
├── assets/
│   └── logo.svg
├── android/
│   ├── app/
│   └── gradle/
├── index.html
├── styles.css
├── app.js
├── src/
│   └── app.ts
└── README.md

Core Files

• index.html: app structure
• styles.css: layout, styling, graph visuals
• app.js: browser-ready app logic
• src/app.ts: TypeScript source
• android/: Android WebView project
• assets/logo.svg: project and app icon source

Typical Workflow

1. Create the graph.
2. Add capacities and initial flow values.
3. Choose source and sink.
4. Check flow conservation on internal nodes.
5. Compute the maximum flow.
6. Inspect augmenting paths.
7. Inspect the final flow decomposition.
8. Inspect the induced minimum cut and its capacity.
9. Verify the certificate max flow = min cut.

Educational Use Cases

This project is especially useful for:

• algorithms courses
• graph theory classes
• operations research exercises
• oral exam preparation
• visual demonstrations of maximum flow and minimum cut

Notes

• The web version is fully client-side.
• The Android version works offline.
• The APK included here is a debug build intended for testing.
• The TypeScript source is included alongside the runnable JavaScript build.

License

This folder currently has no explicit license file. Add one before public distribution if needed.