---
description: This section describes how to implement a flow network.
---

# 9.1. Flow Network

A flow network is a directed graph that has the following properties:

{% embed url="https://www.slideshare.net/jchoi7s/flow-network" %}

## Max Flow

Let us define the [`MaxFlow`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/graph/flow/MaxFlow.java) class that keeps track of the amount of flows in every edge used to find the maximum flow:

```java
public class MaxFlow {
    private Map<Edge, Double> flow_map;
    private double maxflow;

    public MaxFlow(Graph graph) {
        init(graph);
    }

    public void init(Graph graph) {
        flow_map = new HashMap<>();
        maxflow = 0;

        for (Edge edge : graph.getAllEdges())
            flow_map.put(edge, 0d);
    }
}
```

* `L2`: consists of (edge, flow) as the key-value pair.
* `L3`: stores the total amount of flows to the target vertices.
* `L13-14`: initializes all flows to `0`.

Let us define getter methods:

```java
public double getMaxFlow() {
    return maxflow;
}

public double getResidual(Edge edge) {
    return edge.getWeight() - flow_map.get(edge);
}
```

* `L5`: returns the remaining residual that can be used to push more flows.
  * `L6`: the edge weight represents the total capacity.

Finally, let us define setter methods:

```java
public void updateFlow(List<Edge> path, double flow) {
    path.forEach(e -> updateFlow(e, flow));
    maxflow += flow;
}

public void updateFlow(Edge edge, double flow) {
    Double prev = flow_map.getOrDefault(edge, 0d);
    flow_map.put(edge, prev + flow);
}
```

* `L1`: takes the path from a source and a target.
  * `L2`: updates the flow of every edge in the path with the specific flow.
  * `L3`: updates the overall flow.
* `L6`: adds the specific flow to the specific edge.
