import java.util.ArrayList;
import java.util.LinkedHashSet;

class CircleNode extends Node<String> {
  float x, y;
  public CircleNode(String v, float x, float y) {
    super(v);
    this.x = x;
    this.y = y;
  }
  void display() {
    fill(255);
    ellipse(x, y, 50, 50);
    fill(0);
    textSize(20);
    text(value, x, y);
  }
}
ArrayList<CircleNode> circles;

FordFulkerson<String> g;
CircleNode source,sink;

void setup() {
  //Console example:
  if (true) {
    g = new FordFulkerson<String>();
    Node<String> s = g.node("s"), o = g.node("o"), p = g.node("p"), q = g.node("q"), r = g.node("r"), t = g.node("t");
    g.link(s, o, 3).link(s, p, 3).link(o, p, 2).link(o, q, 3);
    g.link(p, r, 2).link(r, t, 3).link(q, r, 4).link(q, t, 2);
    System.out.println("Maximum flow: "+g.maxFlow(s, t));
    for (Edge<String> e : g.edges) System.out.println("Edge from "+e.from+" to "+e.to+" used "+e.flow+" / "+e.capacity);
  }

  //Graphical example
  size(400, 400);
  textAlign(CENTER);
  circles = new ArrayList<CircleNode>();
  CircleNode s = new CircleNode("s", 50, 200), o = new CircleNode("o", 150, 100), p = new CircleNode("p", 150, 300), q = new CircleNode("q", 250, 100), r = new CircleNode("r", 250, 300), t = new CircleNode("t", 350, 200);
  circles.add(s);
  circles.add(o);
  circles.add(p);
  circles.add(q);
  circles.add(r);
  circles.add(t);
  g = new FordFulkerson<String>();
  g.link(s, o, 3).link(s, p, 3).link(o, p, 2).link(o, q, 3);
  g.link(p, r, 2).link(r, t, 3).link(q, r, 4).link(q, t, 2);
  source = s;
  sink = t;
  //  System.out.println("Maximum flow: "+g.maxFlow(s, t));
}

void draw() {
  background(255);
  fill(0);
  rectMode(CENTER);
  for (CircleNode c : circles) {
    for (Edge<String> e : g.edges) {
      if(e.capacity == 0) continue;
      CircleNode from = (CircleNode)e.from, to = (CircleNode)e.to;
      line(from.x, from.y, to.x, to.y);
      fill(0);
      rect((from.x*3+to.x*7)/10,(from.y*3+to.y*7)/10,3,3); //draw dot to represent direction
      if(e.updated) fill(0,0,255); else fill(0);
      text(e.flow +"/"+e.capacity , (from.x+to.x)/2, (from.y+to.y)/2);
    }
  }
  for(CircleNode c : circles) c.display();
}
void keyPressed() {
for(Edge<String> e : g.edges) e.updated = false;
  g.maxFlow(source,sink,false,true);
}

class Node<T> {
  public T value;
  public Node(T v) {
    value = v;
  }
  public ArrayList<Edge<T> > edgesOut = new ArrayList<Edge<T> >();
  public String toString() {
    return value.toString();
  }
}
class Edge<T> {
  boolean updated;  //<-- for processing sketch to color updated nodes
  public Node<T> from, to;
  public Edge<T> reverse;
  public int capacity, flow;
  public int residual() {
    return capacity - flow;
  }
  public Edge(Node<T> f, Node<T> t, int c) {
    this.from = f;
    this.to= t;
    this.capacity = c;
  }
}
class FordFulkerson<T> {
  public ArrayList<Edge<T> > edges = new ArrayList<Edge<T>>();
  public Node<T> node(T v) {
    return new Node<T>(v);
  } //convenience helper
  public FordFulkerson<T> link(Node<T> f, Node<T> t, int c) {
    Edge<T> fe = new Edge<T>(f, t, c), re = new Edge<T>(t, f, 0);
    f.edgesOut.add(re.reverse = fe);
    t.edgesOut.add(fe.reverse = re);
    edges.add(fe);
    return this;
  }
  private LinkedHashSet<Edge<T>> dfs(Node<T> a, Node<T> b, LinkedHashSet<Edge<T>> path) {
    if (path == null) path = new LinkedHashSet<Edge<T>>();
    if (a==b) return path;
    for (Edge<T> e : a.edgesOut) if (e.residual() > 0 && !path.contains(e)) {
      path.add(e);    //rehashes reference to e
      Object o = dfs(e.to, b, path);
      if (o!=null) return path;
      path.remove(e); //faster if we could just remove last
    }
    return null;
  }
  public int maxFlow(Node<T> a, Node<T> b) {
    return maxFlow(a, b, true, false);
  }
  public Integer maxFlow(Node<T> a, Node<T> b, boolean zeroOutFlow, boolean executeOneIteration) {
    if (zeroOutFlow) for (Edge<T> e : edges) e.flow = e.reverse.flow = 0;
    while (true) {
      LinkedHashSet<Edge<T>> path = dfs(a, b, new LinkedHashSet<Edge<T>>());
      if (path == null && executeOneIteration) return null;
      if (path == null) break;
      Integer curmaxflow = null;
      for (Edge<T> e : path) if (curmaxflow == null || e.residual() < curmaxflow) curmaxflow = e.residual();
      for (Edge<T> e : path) {
        e.flow += curmaxflow;
        e.reverse.flow -= curmaxflow;
        e.updated = e.reverse.updated = true; //for processing sketch
      }
      if(executeOneIteration) break;
    }
    int out = 0;
    for (Edge<T> e : a.edgesOut) out += e.flow;
    return out;
  }
}