001package algs42; 002 003import stdlib.*; 004import algs13.Bag; 005 006// See instructions below 007public class MyGarbageCollector { 008 009 ///////////////////////////////////////////////////////////////////////// 010 // Do not modify anything in this section 011 // This is a representation of a graph using Node objects, rather than ints. 012 // To build the graph, we use an array of Node objects. 013 ///////////////////////////////////////////////////////////////////////// 014 static class Node { 015 private String key; 016 private Bag<Node> adj; 017 public Node (String key) { 018 this.key = key; 019 this.adj = new Bag<> (); 020 } 021 public String toString () { return key; } 022 public void addEdgeTo (Node n) { adj.add (n); } 023 public Bag<Node> adj () { return adj; } 024 } 025 Node[] node; 026 int V; 027 int E; 028 public static boolean DEBUG = false; 029 public MyGarbageCollector (int V) { 030 if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative"); 031 this.V = V; 032 this.E = 0; 033 this.node = new Node[V]; 034 for (int i=0; i<V; i++) { 035 node[i] = new Node ("n" + (DEBUG ? i : StdRandom.uniform (100))); 036 } 037 } 038 public MyGarbageCollector(Digraph G) { 039 this (G.V ()); // run the first constructor 040 for (int v=0; v<V; v++) { 041 for (int w : G.adj (v)) 042 addEdge(v, w); 043 } 044 } 045 public MyGarbageCollector(In in) { 046 this (in.readInt()); // run the first constructor 047 int E = in.readInt(); 048 if (E < 0) throw new IllegalArgumentException("Number of edges in a Digraph must be nonnegative"); 049 for (int i = 0; i < E; i++) { 050 int v = in.readInt(); 051 int w = in.readInt(); 052 addEdge(v, w); 053 } 054 } 055 public void addEdge(int v, int w) { 056 if (v < 0 || v >= V) throw new IndexOutOfBoundsException("vertex " + v + " is not between 0 and " + (V-1)); 057 if (w < 0 || w >= V) throw new IndexOutOfBoundsException("vertex " + w + " is not between 0 and " + (V-1)); 058 node[v].addEdgeTo (node[w]); 059 E++; 060 } 061 public String toString() { 062 StringBuilder s = new StringBuilder(); 063 String NEWLINE = System.getProperty("line.separator"); 064 s.append(V + " vertices, " + E + " edges " + NEWLINE); 065 for (int v = 0; v < V; v++) { 066 s.append(String.format("%s: ", node[v])); 067 for (Node w : node[v].adj ()) { 068 s.append(String.format("%s ", w)); 069 } 070 s.append(NEWLINE); 071 } 072 return s.toString(); 073 } 074 public void toGraphviz(String filename) { 075 GraphvizBuilder gb = new GraphvizBuilder (); 076 for (int v = 0; v < V; v++) { 077 gb.addNode (node[v]); 078 for (Node n : node[v].adj ()) 079 gb.addEdge (node[v], n); 080 } 081 gb.toFile (filename); 082 } 083 084 ///////////////////////////////////////////////////////////////////////// 085 // You may modify anything below this. 086 ///////////////////////////////////////////////////////////////////////// 087 // Your goal is to complete the methods below. 088 // All of these methods may take time order V+E (where E is the number of edges) 089 // You should not need to add any new fields. 090 // You can define new functions. 091 // 092 // mark returns an array of booleans: returnValue[i] should be true iff node[i] is 093 // reachable from node[s] by following the pointers in the adjacency list. 094 public boolean[] mark (int s) { 095 // TODO 096 return null; 097 } 098 099 // isTree returns true if the object graph rooted at node[s] is a (rooted out) tree. 100 public boolean isTree (int s) { 101 // TODO 102 return false; 103 } 104 105 // hasCycle returns true if there is a cycle reachable from node[s]. 106 public boolean hasCycle (int s) { 107 // TODO 108 return false; 109 } 110 111 // I used the following function to print boolean arrays: 112 // 113 // public static String booleanArraytoString (boolean[] a) { 114 // StringBuilder sb = new StringBuilder (); 115 // sb.append ("["); 116 // boolean comma = false; 117 // for (boolean b : a) { 118 // if (comma) { sb.append (", "); } else { comma = true; } 119 // sb.append (b ? '1' : '0'); 120 // } 121 // sb.append ("]"); 122 // return sb.toString (); 123 // } 124 // 125 // Here are my results on three files from the data directory: 126 // 127 // tinyDG.txt 128 // marked( 0): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] 129 // marked( 1): [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 130 // marked( 2): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] 131 // marked( 3): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] 132 // marked( 4): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] 133 // marked( 5): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] 134 // marked( 6): [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1] 135 // marked( 7): [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 136 // marked( 8): [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1] 137 // marked( 9): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1] 138 // marked(10): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1] 139 // marked(11): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1] 140 // marked(12): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1] 141 // isTree: [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 142 // hasCycle: [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 143 // 144 // tinyDGex2.txt 145 // marked( 0): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0] 146 // marked( 1): [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 147 // marked( 2): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0] 148 // marked( 3): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0] 149 // marked( 4): [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0] 150 // marked( 5): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0] 151 // marked( 6): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0] 152 // marked( 7): [0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1] 153 // marked( 8): [0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0] 154 // marked( 9): [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0] 155 // marked(10): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0] 156 // marked(11): [0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1] 157 // isTree: [0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0] 158 // hasCycle: [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0] 159 // 160 // tinyDAG.txt 161 // marked( 0): [1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1] 162 // marked( 1): [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 163 // marked( 2): [1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1] 164 // marked( 3): [0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] 165 // marked( 4): [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0] 166 // marked( 5): [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0] 167 // marked( 6): [0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1] 168 // marked( 7): [0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1] 169 // marked( 8): [0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1] 170 // marked( 9): [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1] 171 // marked(10): [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0] 172 // marked(11): [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1] 173 // marked(12): [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 174 // isTree: [0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1] 175 // hasCycle: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 176 177 public static void main (String[] args) { 178 //MyGarbageCollector.DEBUG = true; // Gives nice node names for debugging 179 //StdRandom.setSeed (0); // Gives reproduceable results for debugging 180 //MyGarbageCollector G = new MyGarbageCollector (new In ("data/tinyDG.txt")); 181 //MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.binaryTree (20)); 182 //MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.rootedInTree (20)); 183 //MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.rootedOutTree (20)); 184 //MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.cycle (10)); 185 //MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.dag (20, 20)); 186 //MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.tournament (8)); 187 //MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.strong (20, 36, 4)); 188 //MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.strong (20, 36, 4)); 189 MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.simple (20, 20)); 190 StdOut.println(G.toString ()); 191 G.toGraphviz ("g.png"); 192 193 // TODO 194 // write some tests. 195 } 196 197}