Maximize p = 0x1 + x2 + 0x3 + x4 subject to
x1 <= 4
x2 <= 2
x3 <= 3
x4 <= 2
x2 - x1 <= 0
x4 - x3 <= 0

Maximize p = 0x1 + 0x2 + 0x3 + 0x4 + 0x5 + 0x6 + x7 + x8  subject to
x1 <= 4
x2 <= 2
x3 <= 3
x4 <= 2
x5 <= 3
x6 <= 1
x7 <= 2
x8 <= 4
x3 - x1 <= 0
x4 + x5 - x2 - x6 <= 0
x6 + x7 - x3 - x4 <= 0
x8 - x5 <= 0

Minimize p = 4x1 + 2x2 + 3x3 + 2x4 + 0y1 + 0y3  subject to
x1 + y1 >= 1
x3 + y3 >= 1
x2 - y1 >= 0
x4 - y3 >= 0

Minimize p = 4x1 + 2x2 + 3x3 + 2x4 +
3x5 + x6 + 2x7 + 4x8 + 0y1 + 0y2 + 0y3 + 0y4  subject to
x1 + y1 >= 1
x2 + y2 >= 1
x3 - y1 + y3 >= 0
x4 - y2 + y3 >= 0
x5 - y2 + y4 >= 0
x6 - y3 + y2 >= 0
x7 - y3 >= 0
x8 - y4 >= 0

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);
    }
}

public double getMaxFlow() {
    return maxflow;
}

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

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);
}

public class Subgraph {
    private final List<Edge> edges;
    private final Set<Integer> vertices;

    public Subgraph() {
        edges = new ArrayList<>();
        vertices = new HashSet<>();
    }

    public Subgraph(Subgraph graph) {
        edges = new ArrayList<>(graph.getEdges());
        vertices = new HashSet<>(graph.getVertices());
    }
}

public List<Edge> getEdges() { return edges; }

public Set<Integer> getVertices() { return vertices; }

public void addEdge(Edge edge) {
    edges.add(edge);
    vertices.add(edge.getSource());
    vertices.add(edge.getTarget());
}

public boolean contains(int vertex) {
    return vertices.contains(vertex);
}

private double getMin(MaxFlow mf, List<Edge> path) {
    double min = mf.getResidual(path.get(0));

    for (int i = 1; i < path.size(); i++)
        min = Math.min(min, mf.getResidual(path.get(i)));

    return min;
}

private Subgraph getAugmentingPath(Graph graph, MaxFlow mf, Subgraph sub, int source, int target) {
    if (source == target) return sub;
    Subgraph tmp;

    for (Edge edge : graph.getIncomingEdges(target)) {
        if (sub.contains(edge.getSource())) continue;
        if (mf.getResidual(edge) <= 0) continue;
        tmp = new Subgraph(sub);
        tmp.addEdge(edge);
        tmp = getAugmentingPath(graph, mf, tmp, source, edge.getSource());
        if (tmp != null) return tmp;
    }

    return null;
}

protected void updateBackward(Graph graph, Subgraph sub, MaxFlow mf, double min) {
    boolean found;

    for (Edge edge : sub.getEdges()) {
        found = false;

        for (Edge rEdge : graph.getIncomingEdges(edge.getSource())) {
            if (rEdge.getSource() == edge.getTarget()) {
                mf.updateFlow(rEdge, -min);
                found = true;
                break;
            }
        }

        if (!found) {
            Edge rEdge = graph.setDirectedEdge(edge.getTarget(), edge.getSource(), 0);
            mf.updateFlow(rEdge, -min);
        }
    }
}