BANKROB - SPOJ Solution MAXFLOW-Ford-Fulkerson

Algorithm:

1. Split each node into two nodes. Node start and node end. Connect these by links with capacity = 1 from start to end node. "Source node-start" connects to "source node-end" with Infinite capacity. Same with target node.

2. If the input is, for example, 2 - 4 for an edge, connect "node 2-end" to "node-4 start" and "node 4-end" to "node 2-start" with capacity = Infinite. Do this for all input edges.

3. Run Ford-Fulkerson.

4. The number of augmenting paths found is the solution.

Code (Java) :

import java.io.*;
import java.util.*;
 
public class MAXFLOWWC {
    static int s, t, V, E;
    static ArrayList<ArrayList<Edge>> g;  
    public static void main(String[] args) throws Exception{
        int[] line1 = IO.nextIntArray(2, " ");
        int[] line2 = IO.nextIntArray(2, " ");
        
        V = (line1[1])*2+1;
        E = line1[2];
        s = line2[1]*2-1;
        t = line2[2]*2-1; 
        g = new ArrayList<>();
        for(int i=0;i<V;++i)g.add(new ArrayList<>()); 
        int data[][] = IO.next2dInt(E, 2, " "); 
        
        for(int i=1;i<V;i+=2){ 
            int cap = 1;
            if(i==s || i==t)cap = Integer.MAX_VALUE;
            g.get(i).add(new Edge(i, i+1, cap));
            g.get(i+1).add(new Edge(i+1, i, cap));
        }
        
        for(int i=1;i<data.length;++i){
            int[] line = data[i];
            int cap = Integer.MAX_VALUE; 
            
            line[1] = line[1]*2;
            line[2] = line[2]*2; 
            
            Edge edge1 = new Edge(line[1], line[2]-1, cap); // 2-3
            Edge edge2 = new Edge(line[2], line[1]-1, cap); // 4-1 
            g.get(line[1]).add(edge1); 
            g.get(line[1]-1).add(edge2);
            g.get(line[2]-1).add(edge1); 
            g.get(line[2]).add(edge2); 
        }
        
        Fulkerson();
        IO.println(augPaths);
    }
    
    static int augPaths;
    
    public static void Fulkerson(){
        int flow=0;
        Edge[] path = hasAugmentingPath(); 
        while(path[t]!=null){
            augPaths++;
            int min = Integer.MAX_VALUE;   
            for(int i=t;i!=s;i = path[i].other(i)){ 
                if(path[i].capacityTo(i)<min) min = path[i].capacityTo(i);  
            } 
            flow+=min;
            for(int i=t;i!=s;i=path[i].other(i)) path[i].adjustFlow(i, min);  
            path = hasAugmentingPath();
        } 
    }
    
    
    public static Edge[] hasAugmentingPath(){ 
        Edge[] path = new Edge[V];
        Arrays.fill(path, null);
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        
        boolean marked[] = new boolean[V]; 
        marked[s] = true;
        boolean stop = false;
        while(!q.isEmpty()){
            int c = q.poll();  
            for(Edge edge:g.get(c)){  
                if(edge.to!=c && marked[edge.to]) continue;
                if(edge.capacityTo(edge.other(c))!=0){ 
                    q.add(edge.other(c)); 
                    marked[edge.other(c)] = true; 
                    if(path[edge.other(c)]==null)path[edge.other(c)] = edge; 
                    if(edge.other(c)==t){stop = true;break;}
                }
            }
            if(stop)break;
        } 
        return path;
    }
    
    static class Edge{
        int from, to, capacity, flow;
        Edge(int from, int to, int capacity){
            this.from = from;
            this.to = to;
            this.capacity = capacity;
            flow = 0;
        }
        int other(int e){
            if(e==from)return to;
            else return from;
        }
        int capacityTo(int v){
            if(v==to)return (capacity-flow);
            else return flow;
        }
        void adjustFlow(int v, int flow){
            if(v==to)this.flow += flow;
            else this.flow -= flow;
        }
        public String toString(){return "["+from+"-"+to+":"+flow+"/"+capacity+"]";}
    }
    static class IO {

        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public static int[][] next2dInt(int rows, int cols, String seperator) throws Exception {
            int[][] arr = new int[rows + 1][cols + 1];
            for (int i = 1; i <= rows; ++i) {
                arr[i] = nextIntArray(cols, seperator);
            }
            return arr;
        }

        public static int[] nextIntArray(int nInts, String seperator) throws IOException {
            String ints = br.readLine();
            String[] sArray = ints.split(seperator);
            int[] array = new int[nInts + 1];
            for (int i = 1; i <= nInts; ++i) {
                array[i] = Integer.parseInt(sArray[i - 1]);
            }
            return array;
        }

        public static long[] nextLongArray(int nLongs, String seperator) throws IOException {
            String longs = br.readLine();
            String[] sArray = longs.split(seperator);
            long[] array = new long[nLongs + 1];
            for (int i = 1; i <= nLongs; ++i) {
                array[i] = Long.parseLong(sArray[i - 1]);
            }
            return array;
        }

        public static double[] nextDoubleArray(int nDoubles, String seperator) throws IOException {
            String doubles = br.readLine();
            String[] sArray = doubles.split(seperator);
            double[] array = new double[nDoubles + 1];
            for (int i = 1; i <= nDoubles; ++i) {
                array[i] = Double.parseDouble(sArray[i - 1]);
            }
            return array;
        }

        public static char[] nextCharArray(int nChars, String seperator) throws IOException {
            String chars = br.readLine();
            String[] sArray = chars.split(seperator);
            char[] array = new char[nChars + 1];
            for (int i = 1; i <= nChars; ++i) {
                array[i] = sArray[i - 1].charAt(0);
            }
            return array;
        }

        public static int nextInt() throws IOException {
            String in = br.readLine();
            return Integer.parseInt(in);
        }

        public static double nextDouble() throws IOException {
            String in = br.readLine();
            return Double.parseDouble(in);
        }

        public static long nextLong() throws IOException {
            String in = br.readLine();
            return Long.parseLong(in);
        }

        public static int nextChar() throws IOException {
            String in = br.readLine();
            return in.charAt(0);
        }

        public static String nextString() throws IOException {
            return br.readLine();
        }

        public static void print(Object... o) {
            for (Object os : o) {
                System.out.print(os);
            }
        }

        public static void println(Object... o) {
            for (Object os : o) {
                System.out.print(os);
            }
            System.out.print("\n");
        }

        public static void printlnSeperate(String seperator, Object... o) {
            StringBuilder sb = new StringBuilder();
            sb.delete(sb.length() - seperator.length(), sb.length());
            System.out.println(sb);
        }
    } 
}

Maximum Bipartite Matching using Ford Fulkerson Algorithm (using DFS) - Java

Maximum Bipartite Matching is an application of the Ford Fulkerson Algorithm. 

1. Create a single source vertex for all vertices in one group-A.

2. Create a single sink vertex for all vertices in the other group-B.

3. Source vertex -> (group-A) vertices edges capacity = 1

4. (group-B) vertices -> sink edges capacity = 1

5. (group-A) vertices -> (group-B) edges capacity = 1

Example Graph used (Algorithms-Part II - coursera.com) -

Source:

import java.util.ArrayList;
import java.util.LinkedList;

public class MaximumBipartiteMatching {
    class Edge{
        int from, to;
        double capacity, flow;
        
        Edge(int f, int t, double capacity){
            from = f;
            to = t;
            this.capacity = capacity;
        }
        
        int other(int vertex){
            if(vertex==from)return to; else return from;
        }
        
        double capacity(){ return capacity; } 
        
        double flow(){ return flow; }
        
        double residualCapacityTo(int vertex){
            if(vertex==from)return flow; else return (capacity-flow);
        } 
        
        void increaseFlowTo(int vertex, double delta){
            if(vertex==from)flow = flow-delta;
            else flow = flow+delta;
        }
        
        @Override
        public String toString(){
            return from+" - "+to;
        }
    }
    
    ArrayList<ArrayList<Edge>> graph;
    private int V;
    private Edge[] edgeTo;
    private boolean[] marked;
    private double flow;
    
    MaximumBipartiteMatching(int V){
        this.V = V;
        graph = new ArrayList<>(V);
        for(int i=0;i<V;++i)graph.add(new ArrayList<>());
    }
    
    public void addEdge(int from, int to, double capacity){
        Edge e = new Edge(from, to, capacity); 
        graph.get(from).add(e);
        graph.get(to).add(e);
    }
    
    public void fordFulkerson(int s, int t){
        edgeTo = new Edge[V];
        while(augmentingPathExists(s, t)){ 
            double maxIncrease = 1; 
            
            System.out.print(" Matched Vertices -> "+(1+edgeTo[t].other(t))+" ");
            for(int i=t;i!=s;i=edgeTo[i].other(i)){ 
                if(edgeTo[i].other(i)==s)System.out.print((i+1)+"\n");
                maxIncrease = Math.min(maxIncrease, edgeTo[i].residualCapacityTo(i));
            }
            
            for(int i=t;i!=s;i=edgeTo[i].other(i)){ 
                edgeTo[i].increaseFlowTo(i, maxIncrease);
            } 
            flow+=maxIncrease;
        }
        System.out.println("Max flow = "+flow); 
    }
    
    public boolean augmentingPathExists(int s, int t){
        marked = new boolean[V]; 
        marked[s] = true; 
        quit = false;
        System.out.print("Augmenting Path : ");
        dfs(s, t);
        return marked[t];
    }
     
    boolean quit;
    public void dfs(int v, int sink){
        if(v==sink)quit = true;
        
        for(Edge e:graph.get(v)){
            if(quit)return;
                int other = e.other(v);
                if(!marked[other] && e.residualCapacityTo(other)>0){
                    System.out.print((1+other)+" ");  
                    edgeTo[other] = e;
                    marked[other] = true;  
                    dfs(other, sink);
                }
            }
    }
    
    public static void main(String[] args){
        int v = 10;
        MaximumBipartiteMatching m = new MaximumBipartiteMatching(v+2);
        int source = v, sink = v+1;
        m.addEdge(0,5,1);
        m.addEdge(0,6,1);
        m.addEdge(0,8,1);
        m.addEdge(1,5,1);
        m.addEdge(1,6,1);
        m.addEdge(2,5,1);
        m.addEdge(2,7,1);
        m.addEdge(2,8,1);
        m.addEdge(3,6,1);
        m.addEdge(3,9,1);
        m.addEdge(4,6,1);
        m.addEdge(4,9,1);
        
        for(int i=0;i<v/2;++i){ 
            m.addEdge(source, i, 1); 
            m.addEdge(v/2+i, sink, 1);
        }
        m.fordFulkerson(source, sink);
    }
}

Output:

Augmenting Path : 1 6 12  Matched Vertices -> 6 1

Augmenting Path : 2 6 1 7 12  Matched Vertices -> 7 2

Augmenting Path : 3 6 2 7 1 9 12  Matched Vertices -> 9 3

Augmenting Path : 4 7 2 6 3 8 12  Matched Vertices -> 8 4

Augmenting Path : 5 7 4 10 12  Matched Vertices -> 10 5

Augmenting Path : Max flow = 5.0