Advertisement
Guest User

Untitled

a guest
Dec 6th, 2016
654
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. }
Advertisement
RAW Paste Data Copied
Advertisement