package Deadlock;

import java.util.*;

public class graph implements MyConstants {
    // Graphs, digraphs and algorithms - see appendix B of my thesis.
    // The vertices are stored as integers
    public intpair[] arcs;
    public int nvertices;
    int[] componentsort, cindex, componentnumber;
    int ncomponents, nrealcomponents = 0;
    public graph() {}
    public graph(intpair[] arcs, int n) {this.arcs = arcs; nvertices = n;}
    public graph(Object[] o,int n) {
        nvertices = n;
        arcs = new intpair[o.length];
        for (int i = 0; i < o.length; i++) arcs[i] =(intpair)o[i];
    }
    public graph(int n) {nvertices = n;};
    public boolean empty() {return (nvertices == 0 || arcs.length == 0);}
    public void stronglyconnectedcomponents () {
        // This method partitions a digraph into strongly connected
        // components. It sets up various arrays to record this
        // information which are subsequently used by certain other
        // methods
        int[] father = new int[nvertices];
        int[] low = new int[nvertices];
        int[] order = new int[nvertices];
        cindex = new int[nvertices + 1];
        componentsort = new int[nvertices];
        componentnumber = new int[nvertices];
        Stack S = new Stack();
        int cp = 0;
        ncomponents = 0;
        boolean[] onstack = new boolean[nvertices];
        intset[] unusedadjacentarcs = new intset[nvertices];
        for (int j = 0; j < nvertices; j++) {
            father[j] = UNDEF; order[j] = 0; onstack[j] = false;
            unusedadjacentarcs[j] = new intset();
        } 
        for (int j = 0; j < arcs.length; j++) {
            unusedadjacentarcs[arcs[j].left] =
            unusedadjacentarcs[arcs[j].left].union(j);
        } 
        int i = 0;
        int v = 0;
        int u = 0;
        intpair nextarc;
        onstack[v] = true;
        int step = 2;
        while (true) {
            switch (step) {
            case 2:
                i++;
                order[v] = i;
                low[v] = i;
                onstack[v] = true;
                S.push(new Integer(v));
                step = 3;
                break;
            case 3:
                if (unusedadjacentarcs[v].empty())step = 7;
                else step = 4;
                break;
            case 4:
                u = arcs[unusedadjacentarcs[v].head].right;
                unusedadjacentarcs[v] = unusedadjacentarcs[v].tail;
                if (order[u] == 0) {
                    father[u] = v;
                    v = u;
                    step = 2;
                }
                else step = 5;
                break;
            case 5:
                if (order[u] > order[v]) step = 3;
                else if (!onstack[u]) step = 3;
                else step = 6; 
                break;
            case 6:
                low[v] = Math.min(low[v],order[u]);
                step = 3;
                break;
            case 7:
                if (low[v] == order[v]) {
                    ncomponents = ncomponents + 1;
                    cindex[ncomponents - 1] = cp;
                    int next;
                    do {
                        next = ((Integer)(S.pop())).intValue();
                        onstack[next] = false;
                        componentsort[cp] = next;
                        cp++;
                        componentnumber[next] = ncomponents - 1;
                    } while (next != v);
                    // Check if new component is non-trivial
                    if (cp > cindex[ncomponents-1]+1) nrealcomponents++;
                }
                step = 8;
                break;
            case 8:
                if (father[v] != UNDEF) {
                    low[father[v]] = Math.min(low[father[v]],low[v]);
                    v = father[v];
                    step = 3;
                }
                else step = 9;
                break;
            case 9:
                boolean found = false;
                for (int j = 0; (j < nvertices) && !found; j++) {
                    if (order[j] == 0) {
                        v = j;
                        found = true;
                        step = 2;
                    }
                }
                if (!found) step = 10; 
                break;
            case 10:
                cindex[ncomponents] = cp;
                return;
            }
        }
    }
    public graph findcircuit() {
        // Try to find a directed circuit 
        int[] father = new int[nvertices];
        int[] order = new int[nvertices];
        boolean[] searchpath = new boolean[nvertices];
        intset[] unusedadjacentarcs = new intset[nvertices];
        for (int j = 0; j < nvertices; j++) {
            father[j] = UNDEF; order[j] = 0; searchpath[j] = false;
            unusedadjacentarcs[j] = new intset();
        } 
        for (int j = 0; j < arcs.length; j++) {
            unusedadjacentarcs[arcs[j].left] =
            unusedadjacentarcs[arcs[j].left].union(j);
        } 
        int i = 0;
        int v = 0;
        int u = 0;
        intpair nextarc;
        searchpath[v] = true;
        int step = 2;
        while (true) {
            switch (step) {
            case 2:
                i++;
                order[v] = i; 
            case 3:
                if (unusedadjacentarcs[v].empty()) step = 5; else step = 4;
                break;
            case 4:
                int a = unusedadjacentarcs[v].head;
                unusedadjacentarcs[v]=unusedadjacentarcs[v].tail;
                u = arcs[a].right;
                if (searchpath[u]) { //found a circuit
                    set carcs = new set();
                    carcs = carcs.union(new intpair(v, u));
                    while (v != u) {
                        carcs = carcs.union(new intpair(father[v], v));
                        v = father[v];
                    }
                    return new graph(carcs.arr(), nvertices);
                }
                if (order[u] != 0) step = 3;
                else {
                    father[u] = v;
                    v = u;
                    searchpath[v] = true;
                    step = 2;
                }
                break;
            case 5:
                if (father[v] != UNDEF) {
                    searchpath[v] = false;
                    v = father[v];
                    step = 3;
                } 
                else step = 6;
                break;
            case 6:
                boolean found = false;
                for (int j = 0; (j < nvertices) && !found; j++) {
                    if (order[j] == 0) {
                        searchpath[v] = false;
                        v = j;
                        searchpath[v] = true;
                        found = true;
                        step = 2;
                    }
                }
                if (!found) step = 7; 
                break;
            case 7: // No circuits found
                return new graph(0);
            }
        }
    }
    public graph findpath(int v1, int v2) {
        // Find a directed path from v1 to v2. Return a empty graph if
        // none exist.
        int[] father = new int[nvertices];
        int[] order = new int[nvertices];
        intset[] unusedadjacentarcs = new intset[nvertices];
        for (int j = 0; j < nvertices; j++) {
            father[j] = UNDEF; order[j] = 0;
            unusedadjacentarcs[j] = new intset();
        } 
        for (int j = 0; j < arcs.length; j++) {
            unusedadjacentarcs[arcs[j].left] =
            unusedadjacentarcs[arcs[j].left].union(j);
        } 
        int i = 0;
        int v = v1;
        int u = 0;
        intpair nextarc;
        int step = 2;
        while (true) {
            switch (step) {
            case 2:
                i++;
                order[v] = i; 
            case 3:
                if (unusedadjacentarcs[v].empty()) step = 5; else step = 4;
                break;
            case 4:
                int a = unusedadjacentarcs[v].head;
                unusedadjacentarcs[v]=unusedadjacentarcs[v].tail;
                u = arcs[a].right;
                if (u == v2) { //found a path
                    set carcs = new set();
                    carcs = carcs.union(new intpair(v, v2));
                    while (v != v1) {
                        carcs = carcs.union(new intpair(father[v], v));
                        v = father[v];
                    }
                    return new graph(carcs.arr(), nvertices);
                }
                if (order[u] != 0) step = 3;
                else {
                    father[u] = v;
                    v = u;
                    step = 2;
                }
                break;
            case 5:
                if (father[v] != UNDEF) {
                    v = father[v];
                    step = 3;
                } 
                else step = 6;
                break;
            case 6: // No path found
                return new graph(0);
            }
        }
    }
    public graph getcircuit(intpair arc) {
        // Given that arc lies on some circuit, construct such a circuit 
        graph g = findpath(arc.right, arc.left);
        if (g.empty()) return g;
        intpair[] newarcs = new intpair[g.arcs.length + 1];
        newarcs[0] = arc;
        for (int i = 0; i < g.arcs.length; i++) newarcs[i+1] = g.arcs[i];
        g.arcs = newarcs;
        return g;
    }
    public intpair[] inducededges() {
        // Calculate egdes of simple graph induced from digraph. For this
        // we define class twoints with a special partial ordering (see
        // below) then sort the directed arcs of the graph according to
        // this ordering.
        twoints[] induced = new twoints[arcs.length];
        for (int i = 0; i < arcs.length; i++) 
            induced[i] = new twoints(arcs[i].left, arcs[i].right);
        Sorting.Sort(induced);
        Sortable[] newlist = Sorting.Purge(induced);
        intpair[] edges = new intpair[newlist.length];
        for (int i = 0; i < newlist.length; i++) 
            edges[i] = (intpair)newlist[i];
        return edges;
    }
    public int search3circuit() {
        // for each strongly connected component of the digraph, check
        // its induced graph is a tree, i.e. it has one less edge than
        // it has vertices. It is not a tree if and only if there is
        // a circuit of length at least 3 in that component. Proof
        // => trivial <= the induced graph must contain a proper circuit.
        // either (i) all edges of this circuit are bidirectional arcs
        // in the digraph which implies a proper directed circuit or (ii)
        // one edge in this circuit only goes in one direction (a,b) 
        // within the digraph which implies that there is some directed
        // path from b to a of length 2 or mores as (a,b) is within
        // a strongly connected component and this also gives us a
        // proper directed circuit. Due to A.W.Roscoe
        stronglyconnectedcomponents();
        intpair[] edges = inducededges();
        int[] edgecount = new int[ncomponents];
        int[] vertexcount = new int[ncomponents];
        for (int i = 0; i < edges.length; i++)
            if (componentnumber[edges[i].left] ==
                componentnumber[edges[i].right]) 
                edgecount[componentnumber[edges[i].left]]++;
        for (int i = 0; i < ncomponents; i++) {
            vertexcount[i] = cindex[i + 1] - cindex[i];
            if (edgecount[i] >= vertexcount[i]) return i; 
        }
        return -1;   
    }
}

class twoints extends intpair implements Sortable {
    // Version of intpair with a relaxed ordering function le so that
    // (a,b) is never distinguishable from (b,a)
    public twoints(int x, int y) {super(x,y);}
    public boolean le(Sortable i) {
        twoints i2 = (twoints) i;
        int m1 = Math.min(left,right);
        int m2 = Math.min(i2.left,i2.right);
        int M1 = Math.max(left,right);
        int M2 = Math.max(i2.left,i2.right);
        return (m1 < m2 || (m1 == m2 && M1 <= M2));
    }
}