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