Graph.java

package edgeconnectivity;

import java.io.*;
import java.util.*;

public class Graph {
    int n;
    int[][] m, g, gf;
    ArrayList<Integer> x, y, v;

    public Graph(File file) throws NoInputFileException,
            InputFileIsEmptyException, IncorrectGraphEntryException {
        try {
            Scanner sc = new Scanner(file);
            if (!sc.hasNextLine())
                throw new InputFileIsEmptyException();
            String str = sc.nextLine();
            String[] substr = null;
            if (!str.contains("x")) {
                throw new IncorrectGraphEntryException();
            } else {
                substr = str.split("x");
            }
            if (substr.length != 2)
                throw new IncorrectGraphEntryException();
            try {
                n = Integer.parseInt(substr[0]);
            } catch (NumberFormatException ex) {
                throw new IncorrectGraphEntryException();
            }
            int m;
            try {
                m = Integer.parseInt(substr[1]);
            } catch (NumberFormatException ex) {
                throw new IncorrectGraphEntryException();
            }
            this.m = new int[n][m];
            for (int i = 0; i < n; ++i) {
                if (!sc.hasNextLine())
                    throw new IncorrectGraphEntryException();
                str = sc.nextLine();
                int j = 0;
                String temp = "";
                for (char c : str.toCharArray()) {
                    if (j > m - 1)
                        if (Character.isDigit(c)) {
                            --j;
                            temp += c;
                            this.m[i][j] = Integer.parseInt(temp);
                            ++j;
                        } else
                            temp = "";
                    if (j == m - 1) {
                        if (c == '*')
                            this.m[i][j] = 0;
                        else if (Character.isDigit(c)) {
                            temp += c;
                            this.m[i][j] = Integer.parseInt(temp);
                            ++j;
                            temp = "";
                        }
                    }
                    if (c == '*') {
                        if (temp.length() > 0) {
                            this.m[i][j] = Integer.parseInt(temp);
                            ++j;
                            if (j > m)
                                throw new IncorrectGraphEntryException();
                            temp = "";
                        }
                        this.m[i][j] = 0;
                        ++j;
                        if (j > m)
                            throw new IncorrectGraphEntryException();
                    } else if (Character.isDigit(c))
                        temp += c;
                    else
                        throw new IncorrectGraphEntryException();
                }
            }
            x = new ArrayList<Integer>();
            y = new ArrayList<Integer>();
            v = new ArrayList<Integer>();
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j)
                    if (this.m[i][j] > 0) {
                        x.add(j);
                        y.add(i);
                        v.add(this.m[i][j]);
                    }
            n = v.size();
            g = new int[n][n];
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    g[i][j] = 0;
            while (sc.hasNextLine()) {
                if (!sc.hasNextInt())
                    throw new IncorrectGraphEntryException();
                int u = sc.nextInt();
                if (!v.contains(u))
                    throw new IncorrectGraphEntryException();
                int i = v.indexOf(u);
                if (!sc.hasNextInt())
                    throw new IncorrectGraphEntryException();
                u = sc.nextInt();
                if (!v.contains(u))
                    throw new IncorrectGraphEntryException();
                int j = v.indexOf(u);
                g[i][j] = g[j][i] = 1;
            }
        } catch (FileNotFoundException ex) {
            throw new NoInputFileException();
        }
    }

    public ArrayList<Integer> neighbours(int u) {
        var neighbours = new ArrayList<Integer>();
        for (int v = 0; v < n; ++v)
            if (g[u][v] != 0)
                neighbours.add(v);
        return neighbours;
    }

    public void printGraph() {
        for (int u = 0; u < n; ++u) {
            System.out.print(u + 1 + ": ");
            for (int v : neighbours(u))
                System.out.print(v + 1 + " ");
            System.out.println();
        }
    }

    private boolean bfs(int s, int t, int[] p) {
        boolean[] used = new boolean[n];
        for (int u = 0; u < n; ++u)
            used[u] = false;
        var q = new LinkedList<Integer>();
        q.add(s);
        used[s] = true;
        p[s] = -1;
        while (!q.isEmpty()) {
            int v = q.poll();
            for (int u = 0; u < n; ++u) {
                if (!used[u] && gf[v][u] > 0) {
                    q.add(u);
                    used[u] = true;
                    p[u] = v;
                }
            }
        }
        return used[t];
    }

    private void dfs(int u, boolean[] used) {
        used[u] = true;
        for (int v = 0; v < n; ++v)
            if (gf[u][v] > 0 && !used[v])
                dfs(v, used);
    }

    public int FordFulkerson(int s, int t) {
        gf = new int[n][n];
        for (int u = 0; u < n; ++u)
            for (int v = 0; v < n; ++v)
                gf[u][v] = g[u][v];
        int[] p = new int[n];
        int f = 0;
        while (bfs(s, t, p)) {
            int cf = Integer.MAX_VALUE;
            for (int u = t; u != s; u = p[u]) {
                int v = p[u];
                cf = Math.min(cf, gf[v][u]);
            }
            for (int u = t; u != s; u = p[u]) {
                int v = p[u];
                gf[v][u] -= cf;
                gf[u][v] += cf;
            }
            f += cf;
        }
        return f;
    }

    public boolean[][] minCut(int s) {
        var mincut = new boolean[n][n];
        for (int u = 0; u < n; ++u)
            for (int v = 0; v < n; ++v)
                mincut[u][v] = false;
        boolean[] used = new boolean[n];
        dfs(s, used);
        for (int u = 0; u < n; ++u)
            for (int v : neighbours(u))
                if (g[u][v] > 0 && used[u] && !used[v])
                    mincut[u][v] = mincut[v][u] = true;
        return mincut;
    }

    public boolean[][] edgeConnectivity() {
        int ans = Integer.MAX_VALUE;
        for (int s = 0; s < n; ++s)
            for (int t = s + 1; t < n; ++t) {
                int flow = FordFulkerson(s, t);
                ans = Math.min(ans, flow);
            }
        for (int s = 0; s < n; ++s)
            for (int t = s + 1; t < n; ++t) {
                int flow = FordFulkerson(s, t);
                if (flow == ans)
                    return minCut(s);
            }
        return null;
    }
}