001package algs64; // section 6.4
002import stdlib.*;
003import algs13.Bag;
004/* ***********************************************************************
005 *  Compilation:  javac FlowNetwork.java
006 *  Execution:    java FlowNetwork V E
007 *  Dependencies: Bag.java FlowEdge.java
008 *
009 *  A capacitated flow network, implemented using adjacency lists.
010 *
011 *************************************************************************/
012public class FlowNetwork {
013        private final int V;
014        private int E;
015        private final Bag<FlowEdge>[] adj;
016
017        // empty graph with V vertices
018        @SuppressWarnings("unchecked")
019        public FlowNetwork(int V) {
020                this.V = V;
021                this.E = 0;
022                adj = new Bag[V];
023                for (int v = 0; v < V; v++)
024                        adj[v] = new Bag<>();
025        }
026
027        // random graph with V vertices and E edges
028        public FlowNetwork(int V, int E) {
029                this(V);
030                for (int i = 0; i < E; i++) {
031                        int v = StdRandom.uniform(V);
032                        int w = StdRandom.uniform(V);
033                        double capacity = StdRandom.uniform(100);
034                        addEdge(new FlowEdge(v, w, capacity));
035                }
036        }
037
038        // graph, read from input stream
039        public FlowNetwork(In in) {
040                this(in.readInt());
041                int E = in.readInt();
042                for (int i = 0; i < E; i++) {
043                        int v = in.readInt();
044                        int w = in.readInt();
045                        double capacity = in.readDouble();
046                        addEdge(new FlowEdge(v, w, capacity));
047                }
048        }
049
050
051        // number of vertices and edges
052        public int V() { return V; }
053        public int E() { return E; }
054
055        // add edge e in both v's and w's adjacency lists
056        public void addEdge(FlowEdge e) {
057                E++;
058                int v = e.from();
059                int w = e.to();
060                adj[v].add(e);
061                adj[w].add(e);
062        }
063
064        // return list of edges incident to  v
065        public Iterable<FlowEdge> adj(int v) {
066                return adj[v];
067        }
068
069        // return list of all edges - excludes self loops
070        public Iterable<FlowEdge> edges() {
071                Bag<FlowEdge> list = new Bag<>();
072                for (int v = 0; v < V; v++)
073                        for (FlowEdge e : adj(v)) {
074                                if (e.to() != v)
075                                        list.add(e);
076                        }
077                return list;
078        }
079
080
081        // string representation of Graph (excludes self loops) - takes quadratic time
082        public String toString() {
083                String NEWLINE = System.getProperty("line.separator");
084                StringBuilder s = new StringBuilder();
085                s.append(V + " " + E + NEWLINE);
086                for (int v = 0; v < V; v++) {
087                        s.append(v + ":  ");
088                        for (FlowEdge e : adj[v]) {
089                                if (e.to() != v) s.append(e + "  ");
090                        }
091                        s.append(NEWLINE);
092                }
093                return s.toString();
094        }
095
096        // test client
097        public static void main(String[] args) {
098                In in = new In(args[0]);
099                FlowNetwork G = new FlowNetwork(in);
100                StdOut.println(G);
101        }
102
103}