Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement