Using Bag data structure

FordFulkerson.java

class Bag<Item extends Comparable<Item>> implements Iterable<Item> {
	
	private Node first;
	private int N;
	
	/************NODE CLASS************/
	
	private class Node{
		Item item; Node next;
		Node(Item k){
			this.item =k;
		}
	}
	
	/************isEmpty() IMPLEMENTATION************/
	
	private boolean isEmpty(){
		return N==0;
	}
	
	public int size(){return N;}
	
	/************	CONTAINS ************/
	
	public boolean contains(Item item){
		Node current = first;
		if(isEmpty()) return false;
		while(current != null){
			if(current.item.equals(item)){
				return true;
			}
			current = current.next;
		}
		return false;
	}
	
	
	/************ADD IMPLEMENTATION************/
	
	public void add(Item k){
		Node current = first;
		if(isEmpty()) { first = new Node(k);N++;return;}
		Node oldfirst = first;
		first = new Node(k);
		first.next = oldfirst;
		N++;
		return;		
	}
	
	/*********  DELETE IMPLEMENTATION ****************/
	
	public void delete(Item k){
		Node current = first;
		if(isEmpty()) return;
		
		Node previous = current;
		while(current != null){
			if(current.item.compareTo(k)==0) break;
			previous = current;			
			current = current.next;
		}
		
		if(current == first){first = first.next;return;}
		if(current == null) return;
		
		previous.next = current.next;
	}
	
	/************ITERATOR IMPLEMENTATION************/
	//returns an iterable list 
	public Iterator<Item> iterator(){
		return new ListIterator();
	}
	
	/************LIST ITERATOR CLASS ************/
	//making the datastructure iterable and returns an iterable list 
	private class ListIterator implements Iterator<Item>{

		private Node current = first;
		
		public boolean hasNext(){
			return current != null;
		}
		
		public Item next(){
			Item item = current.item;
			current = current.next;
			return item;
		}
		
		public void remove(){
			return;
		}
		
	}
}


class FlowEdge implements Comparable<FlowEdge>{
	
	private final int v,w;
	private final double capacity;
	private double flow;
	
	public FlowEdge(int v, int w, double capacity){
		this.v= v; this.w=w; this.capacity=capacity;
		this.flow=0.0;
	}
	
	public int from(){return v;}
	public int to(){return w;}
	public double capacity(){return capacity;}
	public int other(int o){
		if(o==v) return w;
		else if(o==w) return v;
		else throw new RuntimeException("Inconsistent Value");
	}
	
	public double flow(){return flow;}
	
	@Override
	public int compareTo(FlowEdge that) {
		if(this.capacity<that.capacity) return -1;
		else if(this.capacity> that.capacity) return 1;
		else return 0;
	}
	
	public double residualCapacityTo(int vertex){
		if(vertex==v) return flow;
		else if(vertex==w) return capacity-flow;
		else throw new RuntimeException("Inconsistent Edge");
	}
	
	public void addResidualFlowTo(int vertex, double delta){
		if(vertex==v) flow-=delta;
		else if(vertex==w) flow+=delta;
		else throw new RuntimeException("Inconsistent Edge");
	}
	
	public String toString(){
		return String.format("%d-->%d %.2f %.2f", v,w,capacity,flow);
	}

}

class FlowNetwork {
	private final int V;
	private int E;
	public Bag<FlowEdge>[] adj;
	
	/*************** CONSTRUCTORS ****************/
	
	public FlowNetwork(int V){
		this.V = V; this.E =0;
		adj = (Bag<FlowEdge>[]) new Bag[V];
		for(int i=0; i<V;i++)
			adj[i] = new Bag<FlowEdge>();
	}
	
	/*************** DELETE EDGE IMPLEMENTATION ****************/
	
	public void deleteEdge(FlowEdge e){
		int v= e.from(),w = e.other(v);
		adj[v].delete(e); adj[w].delete(e);
	}
	
	/*************** ADD EDGE IMPLEMENTATION ****************/
	
	public void addEdge(FlowEdge e){
		int v = e.from(), w = e.other(v);
		adj[v].add(e); adj[w].add(e);
		E++;
	}
	
	/*************** UTILITY METHODS ****************/
	
	public int V(){return V;}
	public int E(){return E;}
	
	public Iterable<FlowEdge> adj(int v){
		return adj[v];
	}
	
	public Iterable<FlowEdge> edges(){
		int count=0;
		Bag<FlowEdge> edges = new Bag<FlowEdge>();
		for(int i=0; i<V;i++){
			for(FlowEdge e: adj[i]){
				int w = e.other(i);
				if(i<w) {edges.add(e);count++;}
			}
		}
		return edges;
	}
	
	public String toString(){
		String str= "";
		str += "Number of vertices: "+ V+", Number of edges: "+E+"\n";
		for(int i=0; i<V; i++){			
			str +=  i+":";
			for(FlowEdge e: adj[i]){
				int w = e.other(i); double capacity = e.capacity();
				str += "- ("+w+","+capacity+")";
			}			
			str+= "\n";			
		}		
		
		return str;
	}
 
}

/*
 * FORD FULKERSON 
 * 
 * Number of augmenting paths to check is atmost EV/2
 * 
 * Shortest augmenting path algorithm takes time proportional to (VE^2)/2
 * 
 * */

public class FordFulkerson {
	
	private boolean[] marked;
	private FlowEdge[] edgeTo;
	private double value;
	private FlowNetwork G;
	private int s,t;
	
	public FordFulkerson(FlowNetwork G, int s, int t){
		//Finding MaxFlow in flow network G from s to t
		
		this.G=G;this.s=s; this.t=t;
		
		while(hasAugmentingPath(G,s,t)){
			
			//computing bottleneck capacity
			double bottle = Double.POSITIVE_INFINITY;
			for(int v=t; v!=s; v=edgeTo[v].other(v)){
				bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
			}
			
			//Augment flow
			for(int v=t; v!=s; v=edgeTo[v].other(v)){
				edgeTo[v].addResidualFlowTo(v, bottle);
			}
			
			value+=bottle;
			
		}
		
	}
	
	private boolean localEq(int v){
		double EPSILON=1E-11;
		double netflow=0.0;
		
		for(FlowEdge ed: G.adj(v)){
			if(v==ed.from()) netflow-=ed.flow();
			else netflow+=ed.flow();
		}
		
		return Math.abs(netflow) <EPSILON;
		
	}
	
	private boolean isFeasible(FlowNetwork G){
		//Flow on each edge should be non negative and not greater than capacity
		
		for(int v=0; v<G.V(); v++){
			for(FlowEdge ed:G.adj(v)){
				if(ed.flow()<0 || ed.flow()>ed.capacity()){
					return false;
				}
			}
		}
		
		//Local equilibrium at each vertex
		
		for(int v=0; v<G.V(); v++){
			if(v!=s && v!=t && !localEq(v)){
				return false;
			}
		}
		
		return true;		
	}
	
	public double value(){return value;}
	public boolean inCut(int v){return marked[v];}
	
	private boolean hasAugmentingPath(FlowNetwork G, int s, int t){
		marked = new boolean[G.V()];
		edgeTo = new FlowEdge[G.V()];
		Queue<Integer> q = new LinkedList<Integer>();
		
		q.add(s); marked[s]=true;
		while(!q.isEmpty()){
			int v = q.poll();
			
			for(FlowEdge ed:G.adj(v)){
				int w = ed.other(v);
				if(ed.residualCapacityTo(w)>0 &&!marked[w]){
					edgeTo[w]=ed;
					marked[w]=true;
					q.add(w);
				} 
			}			
		}
		
		return marked[t];		
	}

}