001// Exercise 4.4.2 (Solution published at http://algs4.cs.princeton.edu/) 002package algs44; 003import stdlib.*; 004import algs13.Bag; 005import algs13.Stack; 006/** 007 * The {@code EdgeWeightedDigraph} class represents an directed graph of vertices 008 * named 0 through V-1, where each edge has a real-valued weight. 009 * It supports the following operations: add an edge to the graph, 010 * iterate over all of edges leaving a vertex. 011 * Parallel edges and self-loops are permitted. 012 * <p> 013 * For additional documentation, see <a href="http://algs4.cs.princeton.edu/44sp">Section 4.4</a> of 014 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 015 */ 016 017public class EdgeWeightedDigraph { 018 private final int V; 019 private int E; 020 private final Bag<DirectedEdge>[] adj; 021 022 /** 023 * Create an empty edge-weighted digraph with V vertices. 024 */ 025 @SuppressWarnings("unchecked") 026 public EdgeWeightedDigraph(int V) { 027 if (V < 0) throw new Error("Number of vertices must be nonnegative"); 028 this.V = V; 029 this.E = 0; 030 adj = new Bag[V]; 031 for (int v = 0; v < V; v++) 032 adj[v] = new Bag<>(); 033 } 034 035 /** 036 * Create a random edge-weighted graph with V vertices and E edges with no parallel edges or self loops. 037 * The expected running time is proportional to V + E. 038 */ 039 public EdgeWeightedDigraph(int V, int E) { this (V, E, false); } 040 /** 041 * Create a random edge-weighted graph with V vertices and E edges. 042 * The expected running time is proportional to V + E. 043 */ 044 public EdgeWeightedDigraph(int V, int E, boolean allowParallelEdgesAndSelfLoops) { 045 this(V); 046 if (E < 0) throw new Error("Number of edges must be nonnegative"); 047 if (allowParallelEdgesAndSelfLoops) { 048 for (int i = 0; i < E; i++) { 049 int v = (int) (Math.random() * V); 050 int w = (int) (Math.random() * V); 051 double weight = Math.round(100 * Math.random()) / 100.0; 052 DirectedEdge e = new DirectedEdge(v, w, weight); 053 addEdge(e); 054 } 055 } else { 056 if (E > V*(V-1)/2) throw new Error("Number of edges must be less than V*(V-1)/2"); 057 newEdge: while (E>0) { 058 int v = (int) (Math.random() * V); 059 int w = (int) (Math.random() * V); 060 if (v == w) continue; 061 for (DirectedEdge e: adj[v]) 062 if (w == e.to()) 063 continue newEdge; 064 double weight = Math.round(100 * Math.random()) / 100.0; 065 DirectedEdge e = new DirectedEdge(v, w, weight); 066 addEdge(e); 067 E--; 068 } 069 } 070 } 071 /** 072 * Create an edge-weighted digraph from input stream. 073 */ 074 public EdgeWeightedDigraph(In in) { 075 this(in.readInt()); 076 int E = in.readInt(); 077 for (int i = 0; i < E; i++) { 078 int v = in.readInt(); 079 int w = in.readInt(); 080 double weight = in.readDouble(); 081 addEdge(new DirectedEdge(v, w, weight)); 082 } 083 } 084 085 /** 086 * Copy constructor. 087 */ 088 public EdgeWeightedDigraph(EdgeWeightedDigraph G) { 089 this(G.V()); 090 this.E = G.E(); 091 for (int v = 0; v < G.V(); v++) { 092 // reverse so that adjacency list is in same order as original 093 Stack<DirectedEdge> reverse = new Stack<>(); 094 for (DirectedEdge e : G.adj[v]) { 095 reverse.push(e); 096 } 097 for (DirectedEdge e : reverse) { 098 adj[v].add(e); 099 } 100 } 101 } 102 103 /** 104 * Return the number of vertices in this digraph. 105 */ 106 public int V() { 107 return V; 108 } 109 110 /** 111 * Return the number of edges in this digraph. 112 */ 113 public int E() { 114 return E; 115 } 116 117 118 /** 119 * Add the edge e to this digraph. 120 */ 121 public void addEdge(DirectedEdge e) { 122 int v = e.from(); 123 adj[v].add(e); 124 E++; 125 } 126 127 128 /** 129 * Return the edges leaving vertex v as an Iterable. 130 * To iterate over the edges leaving vertex v, use foreach notation: 131 * {@code for (DirectedEdge e : graph.adj(v))}. 132 */ 133 public Iterable<DirectedEdge> adj(int v) { 134 return adj[v]; 135 } 136 137 /** 138 * Return all edges in this graph as an Iterable. 139 * To iterate over the edges, use foreach notation: 140 * {@code for (DirectedEdge e : graph.edges())}. 141 */ 142 public Iterable<DirectedEdge> edges() { 143 Bag<DirectedEdge> list = new Bag<>(); 144 for (int v = 0; v < V; v++) { 145 for (DirectedEdge e : adj(v)) { 146 list.add(e); 147 } 148 } 149 return list; 150 } 151 152 /** 153 * Return number of edges leaving v. 154 */ 155 public int outdegree(int v) { 156 return adj[v].size(); 157 } 158 159 160 161 /** 162 * Return a string representation of this graph. 163 */ 164 public String toString() { 165 String NEWLINE = System.getProperty("line.separator"); 166 StringBuilder s = new StringBuilder(); 167 s.append(V + " " + E + NEWLINE); 168 for (int v = 0; v < V; v++) { 169 s.append(v + ": "); 170 for (DirectedEdge e : adj[v]) { 171 s.append(e + " "); 172 } 173 s.append(NEWLINE); 174 } 175 return s.toString(); 176 } 177 178 /** 179 * Save a graphviz representation of the graph. 180 * See <a href="http://www.graphviz.org/">graphviz.org</a>. 181 */ 182 public void toGraphviz(String filename) { 183 GraphvizBuilder gb = new GraphvizBuilder (); 184 for (int v = 0; v < V; v++) { 185 gb.addNode (v); 186 for (DirectedEdge e : adj[v]) { 187 int w = e.to(); 188 gb.addLabeledEdge (v, w, e.weight ()); 189 } 190 } 191 gb.toFile (filename); 192 } 193 194 /** 195 * Test client. 196 */ 197 public static void main(String[] args) { 198 //args = new String [] { "data/tinyEWDAG.txt" }; 199 //args = new String [] { "data/tinyEWD.txt" }; 200 //args = new String [] { "data/tinyEWDn.txt" }; 201 //args = new String [] { "data/tinyEWDnc.txt" }; 202 args = new String [] { "20", "20" }; 203 204 EdgeWeightedDigraph G; 205 if (args.length == 1) { 206 In in = new In(args[0]); 207 G = new EdgeWeightedDigraph(in); 208 } else { 209 int V = Integer.parseInt (args[0]); 210 int E = Integer.parseInt (args[1]); 211 G = new EdgeWeightedDigraph(V, E, false); 212 } 213 StdOut.println(G); 214 G.toGraphviz ("g.png"); 215 } 216 217}