001// Exercise 4.2.3 (Solution published at http://algs4.cs.princeton.edu/) 002package algs42; 003import stdlib.*; 004import algs13.Stack; 005 006import java.util.NoSuchElementException; 007 008import algs13.Bag; 009 010/** 011 * The {@code Digraph} class represents an directed graph of vertices 012 * named 0 through V-1. 013 * It supports the following operations: add an edge to the graph, 014 * iterate over all of the neighbors incident to a vertex. 015 * Parallel edges and self-loops are permitted. 016 * <p> 017 * For additional documentation, 018 * see <a href="http://algs4.cs.princeton.edu/52directed">Section 5.2</a> of 019 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 020 */ 021public class Digraph { 022 private final int V; 023 private int E; 024 private final Bag<Integer>[] adj; 025 private int[] indegree; 026 027 /** 028 * Create an empty digraph with V vertices. 029 */ 030 @SuppressWarnings("unchecked") 031 public Digraph(int V) { 032 if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative"); 033 this.V = V; 034 this.E = 0; 035 indegree = new int[V]; 036 adj = new Bag[V]; 037 for (int v = 0; v < V; v++) { 038 adj[v] = new Bag<>(); 039 } 040 } 041 042 /** 043 * Initializes a digraph from the specified input stream. 044 * The format is the number of vertices <em>V</em>, 045 * followed by the number of edges <em>E</em>, 046 * followed by <em>E</em> pairs of vertices, with each entry separated by whitespace. 047 * 048 * @param in the input stream 049 * @throws IllegalArgumentException if {@code in} is {@code null} 050 * @throws IllegalArgumentException if the endpoints of any edge are not in prescribed range 051 * @throws IllegalArgumentException if the number of vertices or edges is negative 052 * @throws IllegalArgumentException if the input stream is in the wrong format 053 */ 054 @SuppressWarnings("unchecked") 055 public Digraph(In in) { 056 if (in == null) throw new IllegalArgumentException("argument is null"); 057 try { 058 this.V = in.readInt(); 059 if (V < 0) throw new IllegalArgumentException("number of vertices in a Digraph must be non-negative"); 060 indegree = new int[V]; 061 adj = (Bag<Integer>[]) new Bag[V]; 062 for (int v = 0; v < V; v++) { 063 adj[v] = new Bag<Integer>(); 064 } 065 int E = in.readInt(); 066 if (E < 0) throw new IllegalArgumentException("number of edges in a Digraph must be non-negative"); 067 for (int i = 0; i < E; i++) { 068 int v = in.readInt(); 069 int w = in.readInt(); 070 addEdge(v, w); 071 } 072 } 073 catch (NoSuchElementException e) { 074 throw new IllegalArgumentException("invalid input format in Digraph constructor", e); 075 } 076 } 077 078 /** 079 * Initializes a new digraph that is a deep copy of the specified digraph. 080 * 081 * @param G the digraph to copy 082 * @throws IllegalArgumentException if {@code G} is {@code null} 083 */ 084 @SuppressWarnings("unchecked") 085 public Digraph(Digraph G) { 086 if (G == null) throw new IllegalArgumentException("argument is null"); 087 088 this.V = G.V(); 089 this.E = G.E(); 090 if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be non-negative"); 091 092 // update indegrees 093 indegree = new int[V]; 094 for (int v = 0; v < V; v++) 095 this.indegree[v] = G.indegree(v); 096 097 // update adjacency lists 098 adj = (Bag<Integer>[]) new Bag[V]; 099 for (int v = 0; v < V; v++) { 100 adj[v] = new Bag<Integer>(); 101 } 102 103 for (int v = 0; v < G.V(); v++) { 104 // reverse so that adjacency list is in same order as original 105 Stack<Integer> reverse = new Stack<Integer>(); 106 for (int w : G.adj[v]) { 107 reverse.push(w); 108 } 109 for (int w : reverse) { 110 adj[v].add(w); 111 } 112 } 113 } 114 /** 115 * Return the number of vertices in the digraph. 116 */ 117 public int V() { 118 return V; 119 } 120 121 /** 122 * Return the number of edges in the digraph. 123 */ 124 public int E() { 125 return E; 126 } 127 128 /** 129 * Add the directed edge {@code v->w} to the digraph. 130 * @throws java.lang.IndexOutOfBoundsException unless both {@code 0 <= v < V} and {@code 0 <= w < V} 131 */ 132 public void addEdge(int v, int w) { 133 if (v < 0 || v >= V) throw new IndexOutOfBoundsException("vertex " + v + " is not between 0 and " + (V-1)); 134 if (w < 0 || w >= V) throw new IndexOutOfBoundsException("vertex " + w + " is not between 0 and " + (V-1)); 135 adj[v].add(w); 136 indegree[w]++; 137 E++; 138 } 139 140 /** 141 * Return the list of vertices pointed to from vertex v as an Iterable. 142 * @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= v < V} 143 */ 144 public Iterable<Integer> adj(int v) { 145 if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); 146 return adj[v]; 147 } 148 149 /** 150 * Returns the number of directed edges incident from vertex {@code v}. 151 * This is known as the <em>outdegree</em> of vertex {@code v}. 152 * 153 * @param v the vertex 154 * @return the outdegree of vertex {@code v} 155 * @throws IllegalArgumentException unless {@code {@code 0 <= v < V}} 156 */ 157 public int outdegree(int v) { 158 if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); 159 return adj[v].size(); 160 } 161 162 /** 163 * Returns the number of directed edges incident to vertex {@code v}. 164 * This is known as the <em>indegree</em> of vertex {@code v}. 165 * 166 * @param v the vertex 167 * @return the indegree of vertex {@code v} 168 * @throws IllegalArgumentException unless {@code 0 <= v < V} 169 */ 170 public int indegree(int v) { 171 if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); 172 return indegree[v]; 173 } 174 /** 175 * Return the reverse of the digraph. 176 */ 177 public Digraph reverse() { 178 Digraph R = new Digraph(V); 179 for (int v = 0; v < V; v++) { 180 for (int w : adj(v)) { 181 R.addEdge(w, v); 182 } 183 } 184 return R; 185 } 186 187 /** 188 * Return a string representation of the digraph. 189 */ 190 public String toString() { 191 StringBuilder s = new StringBuilder(); 192 String NEWLINE = System.getProperty("line.separator"); 193 s.append(V + " vertices, " + E + " edges " + NEWLINE); 194 for (int v = 0; v < V; v++) { 195 s.append(String.format("%d: ", v)); 196 for (int w : adj[v]) { 197 s.append(String.format("%d ", w)); 198 } 199 s.append(NEWLINE); 200 } 201 return s.toString(); 202 } 203 204 /** 205 * Save a graphviz representation of the graph. 206 * See <a href="http://www.graphviz.org/">graphviz.org</a>. 207 */ 208 public void toGraphviz(String filename) { 209 GraphvizBuilder gb = new GraphvizBuilder (); 210 for (int v = 0; v < V; v++) { 211 gb.addNode (v); 212 for (int w : adj[v]) 213 gb.addEdge (v, w); 214 } 215 gb.toFile (filename); 216 } 217 218 /** 219 * Test client. 220 */ 221 public static void main(String[] args) { 222 //args = new String[] { "data/mediumDG.txt" }; 223 args = new String[] { "data/tinyDG.txt" }; 224 //args = new String[] { "data/tinyDGeuler1.txt" }; 225 //args = new String[] { "data/tinyDGeuler2.txt" }; 226 //args = new String[] { "data/tinyDGeuler3.txt" }; 227 //args = new String[] { "data/tinyDGeuler4.txt" }; 228 //args = new String[] { "data/tinyDGeuler5.txt" }; 229 //args = new String[] { "data/tinyDGeuler6.txt" }; 230 //args = new String[] { "data/tinyDGex2.txt" }; 231 //args = new String [] { "10", "20" }; 232 233 Digraph G; 234 if (args.length == 1) { 235 In in = new In(args[0]); 236 G = DigraphGenerator.fromIn(in); 237 } else { 238 int V = Integer.parseInt (args[0]); 239 int E = Integer.parseInt (args[1]); 240 G = DigraphGenerator.simple(V, E); 241 } 242 StdOut.println(G); 243 G.toGraphviz ("g.png"); 244 } 245 246}