JAVA

package algs42;

import stdlib.*; import algs13.Bag; import algs13.Queue; import java.util.HashSet;

// See instructions below public class MyDigraph {

///////////////////////////////////////////////////////////////////////// // Do not modify anything in this section // This is a representation of a graph using Node objects, rather than ints. // To build the graph, we use an array of Node objects. ///////////////////////////////////////////////////////////////////////// static class Node { private String key; private Bag adj; public Node (String key) { this.key = key; this.adj = new Bag<> (); } public String toString () { return key; } public void addEdgeTo (Node n) { adj.add (n); } public Bag adj () { return adj; } } Node[] node; int V; int E; public static boolean DEBUG = false; public MyDigraph (int V) { if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative"); this.V = V; this.E = 0; this.node = new Node[V]; for (int i=0; i node[i] = new Node ("n" + (DEBUG ? i : StdRandom.uniform (100))); } } public MyDigraph(Digraph G) { this (G.V ()); // run the first constructor for (int v=0; v for (int w : G.adj (v)) addEdge(v, w); } } public MyDigraph(In in) { this (in.readInt()); // run the first constructor int E = in.readInt(); if (E < 0) throw new IllegalArgumentException("Number of edges in a Digraph must be nonnegative"); for (int i = 0; i < E; i++) { int v = in.readInt(); int w = in.readInt(); addEdge(v, w); } } public void addEdge(int v, int w) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException("vertex " + v + " is not between 0 and " + (V-1)); if (w < 0 || w >= V) throw new IndexOutOfBoundsException("vertex " + w + " is not between 0 and " + (V-1)); node[v].addEdgeTo (node[w]); E++; } public String toString() { StringBuilder s = new StringBuilder(); String NEWLINE = System.getProperty("line.separator"); s.append(V + " vertices, " + E + " edges " + NEWLINE); for (int v = 0; v < V; v++) { s.append(String.format("%s: ", node[v])); for (Node w : node[v].adj ()) { s.append(String.format("%s ", w)); } s.append(NEWLINE); } return s.toString(); } public void toGraphviz(String filename) { GraphvizBuilder gb = new GraphvizBuilder (); for (int v = 0; v < V; v++) { gb.addNode (node[v]); for (Node n : node[v].adj ()) gb.addEdge (node[v], n); } gb.toFile (filename); }

///////////////////////////////////////////////////////////////////////// // You may modify anything below this. ///////////////////////////////////////////////////////////////////////// // Your goal is to complete the methods below. // All of these methods may take time order V+E (where E is the number of edges) // You should not need to add any new fields. // You can define new functions.

// hasCycle returns true if there is a cycle reachable from node[s]. // hint: track the path through each node and adjacent nodes. public boolean hasCycle (int s) { // TODO return false; }