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