import java.util.*;

/** Container class to different classes, that makes the whole
 * set of classes one class formally.
 * @since 1.8
 */
public class FlowTask {

    /** Main method. */
    public static void main (String[] args) {
        FlowTask a = new FlowTask();
        a.run();
    }

    /** Actual main method to run examples and everything. */
    public void run() {
        Graph g = new Graph ("G");
        g.createRandomSimpleGraph(4, 5);
        // g.test3();
        Vertex source = g.first;
        Vertex target = g.first.next;
        g.correct (source, target);
        g.flowInit();
        int steps = 0;
        while (g.augment (source, target)) {
            steps++;
        }
        System.out.println (steps + " augmenting paths found");
        Vertex v = g.first;
        while (v != null) {
            v.flow = g.outFlow(v);
            v = v.next;
        }
        target.flow = source.flow;
        System.out.println (g);
//        Set<Arc> cut = g.findCut (source, target);
//        double flow = 0;
//        for (Arc a: cut) {
//            flow += a.flow;
//        }
//        System.out.println (source + " to " + target
//                + " flow " + flow + " cut " + cut);
    }

    class Vertex {

        private String id;
        private Vertex next;
        private Arc first;
        private int info = 0;
        private Vertex prev = null;
        private double capacity = 0.;
        private double correctedCapacity = 0.;
        private double flow = 0.;

        Vertex (String s, Vertex v, Arc e) {
            id = s;
            next = v;
            first = e;
        }

        Vertex (String s) {
            this (s, null, null);
        }

        @Override
        public String toString() {
            return id + " <" + String.format ("%4.2f", flow) + ">";
        }
    }


    /** Arc represents one arrow in the graph. Two-directional edges are
     * represented by two Arc objects (for both directions).
     */
    class Arc {

        private String id;
        private Vertex source;
        private Vertex target;
        private Arc next;
        private int info = 0;
        private double capacity = 1.;
        private double correctedCapacity = 0.;
        private double flow = 0.;


        Arc (String s, Vertex v, Arc a) {
            id = s;
            target = v;
            next = a;
        }

        Arc (String s) {
            this (s, null, null);
        }

        @Override
        public String toString() {
            return id + " <" + String.format ("%4.2f", flow) + "/" +String.format ("%4.2f", capacity) + ">";
        }
    }


    class Graph {

        private String id;
        private Vertex first;
        private int info = 0;

        Graph (String s, Vertex v) {
            id = s;
            first = v;
        }

        Graph (String s) {
            this (s, null);
        }

        @Override
        public String toString() {
            String nl = System.getProperty ("line.separator");
            StringBuffer sb = new StringBuffer (nl);
            sb.append (id);
            sb.append (nl);
            Vertex v = first;
            while (v != null) {
                sb.append (v.toString());
                sb.append (" -->");
                Arc a = v.first;
                while (a != null) {
                    sb.append (" ");
                    sb.append (a.toString());
                    sb.append (" (");
                    sb.append (v.id);
                    sb.append ("->");
                    sb.append (a.target.id);
                    sb.append (")");
                    a = a.next;
                }
                sb.append (nl);
                v = v.next;
            }
            return sb.toString();
        }

        public Vertex createVertex (String vid) {
            Vertex res = new Vertex (vid);
            res.next = first;
            first = res;
            return res;
        }

        public Arc createArc (String aid, Vertex from, Vertex to) {
            Arc res = new Arc (aid);
            res.next = from.first;
            from.first = res;
            res.source = from;
            res.target = to;
            return res;
        }

        /**
         * Create a connected undirected random tree with n vertices.
         * Each new vertex is connected to some random existing vertex.
         * @param n number of vertices added to this graph
         */
        public void createRandomTree (int n) {
            if (n <= 0)
                return;
            Vertex[] varray = new Vertex [n];
            for (int i = 0; i < n; i++) {
                varray [i] = createVertex ("v" + String.valueOf(n-i));
                if (i > 0) {
                    int vnr = (int)(Math.random()*i);
                    createArc ("a" + varray [vnr].id + "_"
                            + varray [i].id, varray [vnr], varray [i]);
                    createArc ("a" + varray [i].id + "_"
                            + varray [vnr].id, varray [i], varray [vnr]);
                }
            }
        }

        /**
         * Create an adjacency matrix of this graph.
         * Side effect: corrupts info fields in the graph
         * @return adjacency matrix
         */
        public int[][] createAdjMatrix() {
            info = 0;
            Vertex v = first;
            while (v != null) {
                v.info = info++;
                v = v.next;
            }
            int[][] res = new int [info][info];
            v = first;
            while (v != null) {
                int i = v.info;
                Arc a = v.first;
                while (a != null) {
                    int j = a.target.info;
                    res [i][j]++;
                    a = a.next;
                }
                v = v.next;
            }
            return res;
        }

        /**
         * Create a connected simple (undirected, no loops, no multiple
         * arcs) random graph with n vertices and m edges.
         * @param n number of vertices
         * @param m number of edges
         */
        public void createRandomSimpleGraph (int n, int m) {
            if (n <= 0)
                return;
            if (n > 2500)
                throw new IllegalArgumentException ("Too many vertices: " + n);
            if (m < n-1 || m > n*(n-1)/2)
                throw new IllegalArgumentException
                        ("Impossible number of edges: " + m);
            first = null;
            createRandomTree (n);       // n-1 edges created here
            Vertex[] vert = new Vertex [n];
            Vertex v = first;
            int c = 0;
            while (v != null) {
                vert[c++] = v;
                v = v.next;
            }
            int[][] connected = createAdjMatrix();
            int edgeCount = m - n + 1;  // remaining edges
            while (edgeCount > 0) {
                int i = (int)(Math.random()*n);  // random source
                int j = (int)(Math.random()*n);  // random target
                if (i==j)
                    continue;  // no loops
                if (connected [i][j] != 0 || connected [j][i] != 0)
                    continue;  // no multiple edges
                Vertex vi = vert [i];
                Vertex vj = vert [j];
                createArc ("a" + vi.id + "_" + vj.id, vi, vj);
                connected [i][j] = 1;
                createArc ("a" + vj.id + "_" + vi.id, vj, vi);
                connected [j][i] = 1;
                edgeCount--;  // a new edge happily created
            }
        }

        public void test1() {
            Vertex d = createVertex ("D");
            Vertex c = createVertex ("C");
            Vertex b = createVertex ("B");
            Vertex e = createVertex ("E");
            Vertex a = createVertex ("A");
            Arc de = createArc ("DE", d, e);
            de.capacity = 7.;
            Arc be = createArc ("BE", b, e);
            be.capacity = 2.;
            Arc bd = createArc ("BD", b, d);
            bd.capacity = 2.;
            Arc cd = createArc ("CD", c, d);
            cd.capacity = 5.;
            Arc ac = createArc ("AC", a, c);
            ac.capacity = 3.;
            Arc ab = createArc ("AB", a, b);
            ab.capacity = 5.;
        }

        public void test2() {
            Vertex e = createVertex ("E");
            Vertex d = createVertex ("D");
            Vertex c = createVertex ("C");
            Vertex b = createVertex ("B");
            Vertex f = createVertex ("F");
            Vertex a = createVertex ("A");
            Arc ab = createArc ("AB", a, b);
            ab.capacity = 11.;
            Arc ac = createArc ("AC", a, c);
            ac.capacity = 13.;
            Arc bc = createArc ("BC", b, c);
            bc.capacity = 10.;
            Arc bd = createArc ("BD", b, d);
            bd.capacity = 12.;
            Arc cb = createArc ("CB", c, b);
            cb.capacity = 4.;
            Arc ce = createArc ("CE", c, e);
            ce.capacity = 14.;
            Arc dc = createArc ("DC", d, c);
            dc.capacity = 9.;
            Arc df = createArc ("DF", d, f);
            df.capacity = 20.;
            Arc ed = createArc ("ED", e, d);
            ed.capacity = 7.;
            Arc ef = createArc ("EF", e, f);
            ef.capacity = 4.;
        }

        public void test3() {
            Vertex c = createVertex ("C");
            Vertex b = createVertex ("B");
            Vertex d = createVertex ("D");
            Vertex a = createVertex ("A");
            Arc bd = createArc ("BD", b, d);
            bd.capacity = 3.;
            Arc cd = createArc ("CD", c, d);
            cd.capacity = 5.;
            Arc ac = createArc ("AC", a, c);
            ac.capacity = 3.;
            Arc ab = createArc ("AB", a, b);
            ab.capacity = 5.;
            Arc bc = createArc ("BC", b, c);
            bc.capacity = 5.;
            Arc cb = createArc ("CB", c, b);
            cb.capacity = 3.;
        }


        public List<Arc> arcs() {
            ArrayList<Arc> res = new ArrayList<Arc>();
            Vertex v = first;
            while (v != null) {
                v.info = 0;
                Arc a = v.first;
                while (a != null) {
                    // a.source = v;
                    a.info = 0;
                    res.add (a);
                    a = a.next;
                }
                v = v.next;
            }
            Collections.sort (res, (a1, a2) -> a1.capacity > a2.capacity?1:
                    (a1.capacity < a2.capacity?-1:0));
            return res;
        }

        public void correct (Vertex source, Vertex target) {
            initializeCapacities();
            source.correctedCapacity = outCapacity (source);
            target.correctedCapacity = inCapacity (target);
            Vertex v = first;
            boolean loopMore = true; // TODO!!! list of affected nodes needed
            while (loopMore) {
                loopMore = false;
                v = first;
                while (v != null) {
                    if (v != source && v != target) {
                        if (correctVertex(v)) {
                            loopMore = true;
                        }
                    }
                    v = v.next;
                }
                if (!loopMore) {
                    double in = inCapacity (target);
                    double out = outCapacity (source);
                    if (target.correctedCapacity > out) {
                        target.correctedCapacity = out;
                        loopMore = true;
                    }
                    if (source.correctedCapacity > in) {
                        source.correctedCapacity = in;
                        loopMore = true;
                    }
                    if (source.correctedCapacity < target.correctedCapacity) {
                        target.correctedCapacity = source.correctedCapacity;
                        loopMore = true;
                    }
                    if (source.correctedCapacity > target.correctedCapacity) {
                        source.correctedCapacity = target.correctedCapacity;
                        loopMore = true;
                    }
                }
            }
            // evaluate flow for printing purposes only!
            v = first;
            while (v != null) {
                v.flow = v.correctedCapacity;
                Arc a = v.first;
                while (a != null) {
                    a.flow = a.correctedCapacity;
                    a = a.next;
                }
                v = v.next;
            }
        }

        public boolean correctVertex (Vertex v) {
            boolean changed = false;
            // ükski väljuv kaar ei pea olema suurem tipust
            Arc a = v.first;
            while (a != null) {
                if (a.correctedCapacity > v.correctedCapacity) {
                    a.correctedCapacity = v.correctedCapacity;
                    changed = true;
                }
                a = a.next;
            }
            // ükski sisenev kaar ei pea olema suurem tipust
            Vertex vc = first;
            while (vc != null) {
                a = vc.first;
                while (a != null) {
                    if (a.target == v) {
                        if (a.correctedCapacity > v.correctedCapacity) {
                            a.correctedCapacity = v.correctedCapacity;
                            changed = true;
                        }
                    }
                    a = a.next;
                }
                vc = vc.next;
            }
            // tipp ei ole suurem sisenevate summast
            double sum = inCapacity (v);
            if (v.correctedCapacity > sum) {
                v.correctedCapacity = sum;
                changed = true;
            }
            // tipp ei ole suurem väljuvate summast
            sum = outCapacity (v);
            if (v.correctedCapacity > sum) {
                v.correctedCapacity = sum;
                changed = true;
            }
            return changed;
        }

        public void initializeCapacities() {
            Vertex v = first;
            while (v != null) {
                Arc a = v.first;
                while (a != null) {
                    a.correctedCapacity = a.capacity;
                    a.flow = 0.; // a.correctedCapacity;
                    a = a.next;
                }
                v = v.next;
            }
            v = first;
            while (v != null) {
                v.capacity = Math.min (inCapacity(v), outCapacity(v));
                v.correctedCapacity = v.capacity;
                v.flow = 0.; // v.correctedCapacity;
                v = v.next;
            }
        }

        public double outCapacity (Vertex v) {
            double sum = 0.;
            Arc a = v.first;
            while (a != null) {
                sum += a.correctedCapacity;
                a = a.next;
            }
            return sum;
        }

        public double outFlow (Vertex v) {
            double sum = 0.;
            Arc a = v.first;
            while (a != null) {
                sum += a.flow;
                a = a.next;
            }
            return sum;
        }

        public double inCapacity (Vertex w) {
            double sum = 0.;
            Vertex v = first;
            while (v != null) {
                Arc a = v.first;
                while (a != null) {
                    if (a.target == w) {
                        sum += a.correctedCapacity;
                    }
                    a = a.next;
                }
                v = v.next;
            }
            return sum;
        }

        public boolean augment (Vertex source, Vertex target) {
            boolean found = false;
            Vertex v = first;
            while (v != null) {
                v.info = 0; // white
                v = v.next;
            }
            List <Vertex> vq = new LinkedList<Vertex>();
            vq.add (source);
            source.prev = null;
            double additionalFlow = 0.;
            source.info = 1; // grey
            while (vq.size() > 0) {
                v = vq.remove(0);
                v.info = 2; // black
                if (v == target) {
                    found = true;
                    Vertex z = target;
                    while (z.prev != null) {
                        Vertex y = z.prev;
                        Arc aa = y.first;
                        while (aa != null) {
                            if (aa.target == z) {
                                aa.flow += additionalFlow;
                                // System.out.println ("Arc " + aa + " augmented by " + additionalFlow);
                                break;
                            }
                            aa = aa.next;
                        }
                        z = y;
                    }
                    break;
                }
                Arc a = v.first;
                while (a != null) {
                    Vertex w = a.target;
                    double delta = a.correctedCapacity - a.flow;
                    if (w.info == 0 &&  delta > 0) {
                        vq.add (w);
                        w.info = 1;
                        w.prev = v;
                        if (additionalFlow > 0.) {
                            additionalFlow = Math.min(additionalFlow, delta);
                        } else {
                            additionalFlow = delta;
                        }
                    }
                    a = a.next;
                }
            }
            return found;
        }

        public void flowInit() {
            Vertex v = first;
            while (v != null) {
                // v.flow = 0.;
                Arc a = v.first;
                while (a != null) {
                    a.flow = 0.;
                    a = a.next;
                }
                v = v.next;
            }
        }

        public Set<Arc> findCut (Vertex source, Vertex target) {
            Set<Arc> res = new HashSet<Arc>();
            if (source == target)
                return res;
            List<Arc> alist = arcs();
            source.info = 1;
            target.info = 2;
            for (Arc arc: alist) {
                if (arc.source.info == 1) {
                    if (arc.target.info == 2) {
                        arc.info = 5;
                        res.add (arc);
                    } else
                    if (arc.target.info == 0) {
                        arc.info = 7;
                        arc.target.info = 2;
                        res.add (arc);
                    } else
                    if (arc.target.info == 1) {
                        arc.info = 6;
                        // source
                    } else
                        throw new IllegalArgumentException
                                ("Vertex info: " + arc.target.info);
                } else
                if (arc.source.info == 2) {
                    if (arc.target.info == 2) {
                        arc.info = 9;
                        // target
                    } else
                    if (arc.target.info == 0) {
                        arc.info = 11;
                        arc.target.info = 2;
                    } else
                    if (arc.target.info == 1) {
                        arc.info = 10;
                        System.out.println ("Back edge: " + arc);
                    } else
                        throw new IllegalArgumentException
                                ("Vertex info: " + arc.target.info);
                } else
                if (arc.source.info == 0) {
                    if (arc.target.info == 2) {
                        arc.info = 1;
                        arc.source.info = 1;
                        res.add (arc);
                    } else
                    if (arc.target.info == 0) {
                        arc.info = 3;
                        arc.source.info = 1;
                        arc.target.info = 2;
                        res.add (arc);
                    } else
                    if (arc.target.info == 1) {
                        arc.info = 2;
                        arc.source.info = 1;
                    } else
                        throw new IllegalArgumentException
                                ("Vertex info: " + arc.target.info);
                } else
                    throw new IllegalArgumentException
                            ("Vertex info: " + arc.source.info);
            }
            return res;
        }
    }
}