001// Exercise 4.1.3 (Solution published at http://algs4.cs.princeton.edu/) 002package algs41; 003import stdlib.*; 004import algs13.Bag; 005 006/** 007 * The {@code Graph} class represents an undirected graph of vertices 008 * named {@code 0} through {@code V-1}. 009 * It supports the following operations: add an edge to the graph, 010 * iterate over all of the neighbors adjacent 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/51undirected">Section 5.1</a> of 014 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 015 */ 016public class Graph { 017 private final int V; 018 private int E; 019 private final Bag<Integer>[] adj; 020 021 /** 022 * Create an empty graph with V vertices. 023 */ 024 @SuppressWarnings("unchecked") 025 public Graph(int V) { 026 if (V < 0) throw new Error("Number of vertices must be nonnegative"); 027 this.V = V; 028 this.E = 0; 029 this.adj = new Bag[V]; 030 for (int v = 0; v < V; v++) { 031 adj[v] = new Bag<>(); 032 } 033 } 034 035 /** 036 * Return the number of vertices in the graph. 037 */ 038 public int V() { return V; } 039 040 /** 041 * Return the number of edges in the graph. 042 */ 043 public int E() { return E; } 044 045 046 /** 047 * Add the undirected edge v-w to graph. 048 * @throws java.lang.IndexOutOfBoundsException unless both {@code 0 <= v < V} and {@code 0 <= w < V} 049 */ 050 public void addEdge(int v, int w) { 051 if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); 052 if (w < 0 || w >= V) throw new IndexOutOfBoundsException(); 053 E++; 054 adj[v].add(w); 055 adj[w].add(v); 056 } 057 058 059 /** 060 * Return the list of neighbors of vertex v as in Iterable. 061 * @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= v < V} 062 */ 063 public Iterable<Integer> adj(int v) { 064 if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); 065 return adj[v]; 066 } 067 068 /** 069 * Returns the degree of vertex {@code v}. 070 * 071 * @param v the vertex 072 * @return the degree of vertex {@code v} 073 * @throws IllegalArgumentException unless {@code 0 <= v < V} 074 */ 075 public int degree(int v) { 076 if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); 077 return adj[v].size(); 078 } 079 080 /** 081 * Return a string representation of the graph. 082 */ 083 public String toString() { 084 StringBuilder s = new StringBuilder(); 085 String NEWLINE = System.getProperty("line.separator"); 086 s.append(V + " vertices, " + E + " edges " + NEWLINE); 087 for (int v = 0; v < V; v++) { 088 s.append(v + ": "); 089 for (int w : adj[v]) { 090 s.append(w + " "); 091 } 092 s.append(NEWLINE); 093 } 094 return s.toString(); 095 } 096 097 /** 098 * Save a graphviz representation of the graph. 099 * See <a href="http://www.graphviz.org/">graphviz.org</a>. 100 */ 101 public void toGraphviz(String filename) { 102 GraphvizBuilder gb = new GraphvizBuilder (); 103 for (int v = 0; v < V; v++) { 104 gb.addNode (v); 105 boolean showSelfLoop = false; 106 for (int w : adj[v]) { 107 if (v < w) // only once each edge 108 gb.addEdge (v, w); 109 if (v == w) { 110 showSelfLoop = !showSelfLoop; 111 if (showSelfLoop) 112 gb.addEdge (v, w); 113 } 114 } 115 } 116 gb.toFileUndirected (filename); 117 } 118 119 /** 120 * Test client. 121 */ 122 public static void main(String[] args) { 123 //args = new String [] { "data/tinyCG.txt" }; 124 args = new String [] { "data/tinyG.txt" }; 125 //args = new String [] { "20", "40" }; 126 127 Graph G; 128 if (args.length == 1) { 129 In in = new In(args[0]); 130 G = GraphGenerator.fromIn (in); 131 } else { 132 int V = Integer.parseInt (args[0]); 133 int E = Integer.parseInt (args[1]); 134 G = GraphGenerator.simple(V, E); 135 } 136 StdOut.println(G); 137 G.toGraphviz ("g.png"); 138 } 139}