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}