SHARE
TWEET

Untitled

a guest Dec 6th, 2016 190 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.LinkedHashSet;
  3.  
  4. class CircleNode extends Node<String> {
  5.   float x, y;
  6.   public CircleNode(String v, float x, float y) {
  7.     super(v);
  8.     this.x = x;
  9.     this.y = y;
  10.   }
  11.   void display() {
  12.     fill(255);
  13.     ellipse(x, y, 50, 50);
  14.     fill(0);
  15.     textSize(20);
  16.     text(value, x, y);
  17.   }
  18. }
  19. ArrayList<CircleNode> circles;
  20.  
  21. FordFulkerson<String> g;
  22. CircleNode source,sink;
  23.  
  24. void setup() {
  25.   //Console example:
  26.   if (true) {
  27.     g = new FordFulkerson<String>();
  28.     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");
  29.     g.link(s, o, 3).link(s, p, 3).link(o, p, 2).link(o, q, 3);
  30.     g.link(p, r, 2).link(r, t, 3).link(q, r, 4).link(q, t, 2);
  31.     System.out.println("Maximum flow: "+g.maxFlow(s, t));
  32.     for (Edge<String> e : g.edges) System.out.println("Edge from "+e.from+" to "+e.to+" used "+e.flow+" / "+e.capacity);
  33.   }
  34.  
  35.   //Graphical example
  36.   size(400, 400);
  37.   textAlign(CENTER);
  38.   circles = new ArrayList<CircleNode>();
  39.   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);
  40.   circles.add(s);
  41.   circles.add(o);
  42.   circles.add(p);
  43.   circles.add(q);
  44.   circles.add(r);
  45.   circles.add(t);
  46.   g = new FordFulkerson<String>();
  47.   g.link(s, o, 3).link(s, p, 3).link(o, p, 2).link(o, q, 3);
  48.   g.link(p, r, 2).link(r, t, 3).link(q, r, 4).link(q, t, 2);
  49.   source = s;
  50.   sink = t;
  51.   //  System.out.println("Maximum flow: "+g.maxFlow(s, t));
  52. }
  53.  
  54. void draw() {
  55.   background(255);
  56.   fill(0);
  57.   rectMode(CENTER);
  58.   for (CircleNode c : circles) {
  59.     for (Edge<String> e : g.edges) {
  60.       if(e.capacity == 0) continue;
  61.       CircleNode from = (CircleNode)e.from, to = (CircleNode)e.to;
  62.       line(from.x, from.y, to.x, to.y);
  63.       fill(0);
  64.       rect((from.x*3+to.x*7)/10,(from.y*3+to.y*7)/10,3,3); //draw dot to represent direction
  65.       if(e.updated) fill(0,0,255); else fill(0);
  66.       text(e.flow +"/"+e.capacity , (from.x+to.x)/2, (from.y+to.y)/2);
  67.     }
  68.   }
  69.   for(CircleNode c : circles) c.display();
  70. }
  71. void keyPressed() {
  72. for(Edge<String> e : g.edges) e.updated = false;
  73.   g.maxFlow(source,sink,false,true);
  74. }
  75.  
  76. class Node<T> {
  77.   public T value;
  78.   public Node(T v) {
  79.     value = v;
  80.   }
  81.   public ArrayList<Edge<T> > edgesOut = new ArrayList<Edge<T> >();
  82.   public String toString() {
  83.     return value.toString();
  84.   }
  85. }
  86. class Edge<T> {
  87.   boolean updated;  //<-- for processing sketch to color updated nodes
  88.   public Node<T> from, to;
  89.   public Edge<T> reverse;
  90.   public int capacity, flow;
  91.   public int residual() {
  92.     return capacity - flow;
  93.   }
  94.   public Edge(Node<T> f, Node<T> t, int c) {
  95.     this.from = f;
  96.     this.to= t;
  97.     this.capacity = c;
  98.   }
  99. }
  100. class FordFulkerson<T> {
  101.   public ArrayList<Edge<T> > edges = new ArrayList<Edge<T>>();
  102.   public Node<T> node(T v) {
  103.     return new Node<T>(v);
  104.   } //convenience helper
  105.   public FordFulkerson<T> link(Node<T> f, Node<T> t, int c) {
  106.     Edge<T> fe = new Edge<T>(f, t, c), re = new Edge<T>(t, f, 0);
  107.     f.edgesOut.add(re.reverse = fe);
  108.     t.edgesOut.add(fe.reverse = re);
  109.     edges.add(fe);
  110.     return this;
  111.   }
  112.   private LinkedHashSet<Edge<T>> dfs(Node<T> a, Node<T> b, LinkedHashSet<Edge<T>> path) {
  113.     if (path == null) path = new LinkedHashSet<Edge<T>>();
  114.     if (a==b) return path;
  115.     for (Edge<T> e : a.edgesOut) if (e.residual() > 0 && !path.contains(e)) {
  116.       path.add(e);    //rehashes reference to e
  117.       Object o = dfs(e.to, b, path);
  118.       if (o!=null) return path;
  119.       path.remove(e); //faster if we could just remove last
  120.     }
  121.     return null;
  122.   }
  123.   public int maxFlow(Node<T> a, Node<T> b) {
  124.     return maxFlow(a, b, true, false);
  125.   }
  126.   public Integer maxFlow(Node<T> a, Node<T> b, boolean zeroOutFlow, boolean executeOneIteration) {
  127.     if (zeroOutFlow) for (Edge<T> e : edges) e.flow = e.reverse.flow = 0;
  128.     while (true) {
  129.       LinkedHashSet<Edge<T>> path = dfs(a, b, new LinkedHashSet<Edge<T>>());
  130.       if (path == null && executeOneIteration) return null;
  131.       if (path == null) break;
  132.       Integer curmaxflow = null;
  133.       for (Edge<T> e : path) if (curmaxflow == null || e.residual() < curmaxflow) curmaxflow = e.residual();
  134.       for (Edge<T> e : path) {
  135.         e.flow += curmaxflow;
  136.         e.reverse.flow -= curmaxflow;
  137.         e.updated = e.reverse.updated = true; //for processing sketch
  138.       }
  139.       if(executeOneIteration) break;
  140.     }
  141.     int out = 0;
  142.     for (Edge<T> e : a.edgesOut) out += e.flow;
  143.     return out;
  144.   }
  145. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top