001package algs44; 002import stdlib.*; 003import java.util.Iterator; 004import java.util.NoSuchElementException; 005 006/* *********************************************************************** 007 * Compilation: javac AdjMatrixEdgeWeightedDigraph.java 008 * Execution: java AdjMatrixEdgeWeightedDigraph V E 009 * Dependencies: StdOut.java 010 * 011 * An edge-weighted digraph, implemented using an adjacency matrix. 012 * Parallel edges are disallowed; self-loops are allowd. 013 * 014 *************************************************************************/ 015 016public class AdjMatrixEdgeWeightedDigraph { 017 private int V; 018 private int E; 019 private DirectedEdge[][] adj; 020 021 // empty graph with V vertices 022 public AdjMatrixEdgeWeightedDigraph(int V) { 023 if (V < 0) throw new RuntimeException("Number of vertices must be nonnegative"); 024 this.V = V; 025 this.E = 0; 026 this.adj = new DirectedEdge[V][V]; 027 } 028 029 // random graph with V vertices and E edges 030 public AdjMatrixEdgeWeightedDigraph(int V, int E) { 031 this(V); 032 if (E < 0) throw new RuntimeException("Number of edges must be nonnegative"); 033 if (E > V*V) throw new RuntimeException("Too many edges"); 034 035 // can be inefficient 036 while (this.E != E) { 037 int v = (int) (V * Math.random()); 038 int w = (int) (V * Math.random()); 039 double weight = Math.round(100 * Math.random()) / 100.0; 040 addEdge(new DirectedEdge(v, w, weight)); 041 } 042 } 043 044 // number of vertices and edges 045 public int V() { return V; } 046 public int E() { return E; } 047 048 049 // add directed edge v->w 050 public void addEdge(DirectedEdge e) { 051 int v = e.from(); 052 int w = e.to(); 053 if (adj[v][w] == null) { 054 E++; 055 adj[v][w] = e; 056 } 057 } 058 059 // return list of neighbors of v 060 public Iterable<DirectedEdge> adj(int v) { 061 return new AdjIterator(v); 062 } 063 064 // support iteration over graph vertices 065 private class AdjIterator implements Iterator<DirectedEdge>, Iterable<DirectedEdge> { 066 private int v, 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 AdjMatrixEdgeWeightedDigraph G = new AdjMatrixEdgeWeightedDigraph(V, E); 109 StdOut.println(G); 110 } 111 112}