001package algs44;
002import stdlib.*;
003import java.util.Iterator;
004import java.util.NoSuchElementException;
005/* ***********************************************************************
006 *  Compilation:  javac AdjMatrixEdgeWeightedDigraph.java
007 *  Execution:    java AdjMatrixEdgeWeightedDigraph V E
008 *  Dependencies: StdOut.java
009 *
010 *  An edge-weighted digraph, implemented using an adjacency matrix.
011 *  Parallel edges are disallowed; self-loops are allowd.
012 *
013 *************************************************************************/
014
015public class XAdjMatrixEdgeWeightedDigraph {
016        private final int V;
017        private int E;
018        private final DirectedEdge[][] adj;
019
020        // empty graph with V vertices
021        public XAdjMatrixEdgeWeightedDigraph(int V) {
022                if (V < 0) throw new Error("Number of vertices must be nonnegative");
023                this.V = V;
024                this.E = 0;
025                this.adj = new DirectedEdge[V][V];
026        }
027
028        // random graph with V vertices and E edges
029        public XAdjMatrixEdgeWeightedDigraph(int V, int E) {
030                this(V);
031                if (E < 0) throw new Error("Number of edges must be nonnegative");
032                if (E > V*V) throw new Error("Too many edges");
033
034                // can be inefficient
035                while (this.E != E) {
036                        int v = (int) (V * Math.random());
037                        int w = (int) (V * Math.random());
038                        double weight = Math.round(100 * Math.random()) / 100.0;
039                        addEdge(new DirectedEdge(v, w, weight));
040                }
041        }
042
043        // number of vertices and edges
044        public int V() { return V; }
045        public int E() { return E; }
046
047
048        // add directed edge v->w
049        public void addEdge(DirectedEdge e) {
050                int v = e.from();
051                int w = e.to();
052                if (adj[v][w] == null) {
053                        E++;
054                        adj[v][w] = e;
055                }
056        }
057
058        // return list of neighbors of v
059        public Iterable<DirectedEdge> adj(int v) {
060                return new AdjIterator(v);
061        }
062
063        // support iteration over graph vertices
064        private class AdjIterator implements Iterator<DirectedEdge>, Iterable<DirectedEdge> {
065                private final int v;
066                private int w = 0;
067                public AdjIterator(int v) { this.v = v; }
068
069                public Iterator<DirectedEdge> iterator() { return this; }
070
071                public boolean hasNext() {
072                        while (w < V) {
073                                if (adj[v][w] != null) return true;
074                                w++;
075                        }
076                        return false;
077                }
078
079                public DirectedEdge next() {
080                        if (hasNext()) { return adj[v][w++];                 }
081                        else           { throw new NoSuchElementException(); }
082                }
083
084                public void remove()  { throw new UnsupportedOperationException();  }
085        }
086
087
088        // string representation of Graph - takes quadratic time
089        public String toString() {
090                String NEWLINE = System.getProperty("line.separator");
091                StringBuilder s = new StringBuilder();
092                s.append(V + " " + E + NEWLINE);
093                for (int v = 0; v < V; v++) {
094                        s.append(v + ": ");
095                        for (DirectedEdge e : adj(v)) {
096                                s.append(e + "  ");
097                        }
098                        s.append(NEWLINE);
099                }
100                return s.toString();
101        }
102
103
104        // test client
105        public static void main(String[] args) {
106                int V = Integer.parseInt(args[0]);
107                int E = Integer.parseInt(args[1]);
108                XAdjMatrixEdgeWeightedDigraph G = new XAdjMatrixEdgeWeightedDigraph(V, E);
109                StdOut.println(G);
110        }
111
112}