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}