Please fill out the TODO in MyDiagraph.java(public boolean[] mark (int s), public boolean isTree (int s), public boolean hasCycle (int s)):

MyDiagraph.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.

// mark returns an array of booleans: returnValue[i] should be true iff node[i] is

// reachable from node[s] by following the pointers in the adjacency list.

public boolean[] mark (int s) {

// TODO

return null;

}

// isTree returns true if the object graph rooted at node[s] is a (rooted out) tree

// (e.g. No duplicate paths or cycles)

public boolean isTree (int s) {

// TODO

return false;

}

// 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;

}

// Here are my results on three files from the data directory:

// marked( 0): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]

// marked( 1): [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

// marked( 2): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]

// marked( 3): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]

// marked( 4): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]

// marked( 5): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]

// marked( 6): [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]

// marked( 7): [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

// marked( 8): [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]

// marked( 9): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]

// marked(10): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]

// marked(11): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]

// marked(12): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]

// isTree:[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

// hasCycle:[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

//

// tinyDGex2.txt

// marked( 0): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]

// marked( 1): [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

// marked( 2): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]

// marked( 3): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]

// marked( 4): [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]

// marked( 5): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]

// marked( 6): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]

// marked( 7): [0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1]

// marked( 8): [0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]

// marked( 9): [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]

// marked(10): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]

// marked(11): [0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1]

// isTree:[0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0]

// hasCycle:[1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]

//

// tinyDAG.txt

// marked( 0): [1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1]

// marked( 1): [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

// marked( 2): [1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1]

// marked( 3): [0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]

// marked( 4): [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

// marked( 5): [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]

// marked( 6): [0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1]

// marked( 7): [0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1]

// marked( 8): [0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]

// marked( 9): [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]

// marked(10): [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]

// marked(11): [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

// marked(12): [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

// isTree:[0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1]

// hasCycle:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

private static class Test {

String name;

MyDigraph y;

public Test (String name, String filename) {

this.name = name;

this.y = new MyDigraph (new In (filename));

}

public Test (String name, Digraph G) {

this.name = name;

this.y = new MyDigraph (G);

}

}

public static String booleanArraytoString (boolean[] a) {

StringBuilder sb = new StringBuilder ();

sb.append ("[");

boolean comma = false;

if ( a != null ) {

for (boolean b : a) {

if (comma) { sb.append (", "); } else { comma = true; }

sb.append (b ? '1' : '0');

}

}

sb.append ("]");

return sb.toString ();

}

public static void main (String[] args) {

StdRandom.setSeed (0);

MyDigraph.DEBUG = false;

Test t = new Test("tinyDGex2", "data/tinyDGex2.txt");

MyDigraph Y = t.y;

StdOut.println (t.name);

Y.toGraphviz (t.name + ".png");

boolean[][] marked = new boolean[Y.V][];

boolean[] isTree = new boolean[Y.V];

boolean[] hasCycle = new boolean[Y.V];

for (int v=0; v

marked[v] = Y.mark (v);

isTree[v] = Y.isTree (v);

hasCycle[v] = Y.hasCycle (v);

}

String[] expected_result =

{

"[1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]",

"[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]",

"[1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]",

"[1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]",

"[0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]",

"[1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]",

"[1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]",

"[0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1]",

"[0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]",

"[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]",

"[1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]",

"[0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1]",

"[0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0]", // isTree

"[1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]" // hasCycle

};

int v = 0;

for (v=0; v

{

if ( v > 0 ) StdOut.format(", ");

StdOut.format ("%s(%d)", Y.node[v].key, v );

}

StdOut.println ();

StdOut.println ();

for (v=0; v

{

String result = booleanArraytoString (marked[v]);

String validate = result.equals(expected_result[v]) ? "Correct" : "ERROR: Expecting " + expected_result[v];

StdOut.format ("marked(%2d): %s- %s ", v, result, validate );

}

String istree_result = booleanArraytoString (isTree);

String istree_validate = istree_result.equals(expected_result[v]) ? "Correct" : "ERROR: Expecting " + expected_result[v];

StdOut.format ("isTree:%s- %s ", istree_result, istree_validate);

String hascycle_result = booleanArraytoString (hasCycle);

String hascycle_validate = hascycle_result.equals(expected_result[++v]) ? "Correct" : "ERROR: Expecting " + expected_result[v];

StdOut.format ("hasCycle:%s- %s ", hascycle_result, hascycle_validate);

StdOut.println ();

}

}

Queue.java:

package algs13;

importstdlib.*;

import java.util.Iterator;

import java.util.NoSuchElementException;

/* ***********************************************************************

*Compilation:javac Queue.java

*Execution:java Queue < input.txt

*Data files:http://algs4.cs.princeton.edu/13stacks/tobe.txt

*

*A generic queue, implemented using a linked list.

*

*% java Queue < tobe.txt

*to be or not to be (2 left on queue)

*

*************************************************************************/

/**

*The Queue class represents a first-in-first-out (FIFO)

*queue of generic items.

*It supports the usual enqueue and dequeue

*operations, along with methods for peeking at the top item,

*testing if the queue is empty, and iterating through

*the items in FIFO order.

*

*All queue operations except iteration are constant time.

*

*For additional documentation, see Section 1.3 of

*Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

*/

public class Queue implements Iterable {

private int N;// number of elements on queue

private Node first;// beginning of queue

private Node last;// end of queue

// helper linked list class

private static class Node {

public Node() { }

public T item;

public Node next;

}

/**

* Create an empty queue.

*/

public Queue() {

first = null;

last= null;

N = 0;

}

/**

* Is the queue empty?

*/

public boolean isEmpty() {

return first == null;

}

/**

* Return the number of items in the queue.

*/

public int size() {

return N;

}

/**

* Return the item least recently added to the queue.

* @throws java.util.NoSuchElementException if queue is empty.

*/

public T peek() {

if (isEmpty()) throw new NoSuchElementException("Queue underflow");

return first.item;

}

/**

* Add the item to the queue.

*/

public void enqueue(T item) {

Node oldlast = last;

last = new Node<>();

last.item = item;

last.next = null;

if (isEmpty()) first = last;

elseoldlast.next = last;

N++;

}

/**

* Remove and return the item on the queue least recently added.

* @throws java.util.NoSuchElementException if queue is empty.

*/

public T dequeue() {

if (isEmpty()) throw new NoSuchElementException("Queue underflow");

T item = first.item;

first = first.next;

N--;

if (isEmpty()) last = null;

return item;

}

/**

* Return string representation.

*/

public String toString() {

StringBuilder s = new StringBuilder();

for (T item : this)

s.append(item + " ");

return s.toString();

}

// check internal invariants

private static boolean check(Queue that) {

int N = that.N;

Queue.Node first = that.first;

Queue.Node last = that.last;

if (N == 0) {

if (first != null) return false;

if (last!= null) return false;

}

else if (N == 1) {

if (first == null || last == null) return false;

if (first != last)return false;

if (first.next != null)return false;

}

else {

if (first == last)return false;

if (first.next == null) return false;

if (last.next!= null) return false;

// check internal consistency of instance variable N

int numberOfNodes = 0;

for (Queue.Node x = first; x != null; x = x.next) {

numberOfNodes++;

}

if (numberOfNodes != N) return false;

// check internal consistency of instance variable last

Queue.Node lastNode = first;

while (lastNode.next != null) {

lastNode = lastNode.next;

}

if (last != lastNode) return false;

}

return true;

}

/**

* Return an iterator that iterates over the items on the queue in FIFO order.

*/

public Iterator iterator(){

return new ListIterator();

}

// an iterator, doesn't implement remove() since it's optional

private class ListIterator implements Iterator {

private Node current = first;

public boolean hasNext(){ return current != null;}

public void remove(){ throw new UnsupportedOperationException();}

public T next() {

if (!hasNext()) throw new NoSuchElementException();

T item = current.item;

current = current.next;

return item;

}

}

public void toGraphviz(String filename) {

GraphvizBuilder gb = new GraphvizBuilder ();

toGraphviz (gb, null, first);

gb.toFile (filename, "rankdir=\"LR\"");

}

private void toGraphviz (GraphvizBuilder gb, Node prev, Node n) {

if (n == null) { gb.addNullEdge (prev); return; }

gb.addLabeledNode (n, n.item.toString ());

if (prev != null) gb.addEdge (prev, n);

toGraphviz (gb, n, n.next);

}

/**

* A test client.

*/

public static void main(String[] args) {

Trace.drawStepsOfMethod("main");

Trace.drawStepsOfMethod("enqueue");

Trace.drawStepsOfMethod("dequeue");

Trace.run();

StdIn.fromString ("to be or not to - be - - that - - - is");

Queue q = new Queue<>();

int count = 0;

//q.toGraphviz ("queue" + count + ".png"); count++;

while (!StdIn.isEmpty()) {

String item = StdIn.readString();

if (!item.equals("-")) q.enqueue(item);

else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");

//q.toGraphviz ("queue" + count + ".png"); count++;

}

StdOut.println("(" + q.size() + " left on queue)");

}

}

Bag.java:

package algs13;

importstdlib.*;

/* ***********************************************************************

*Compilation:javac Bag.java

*Execution:java Bag < input.txt

*

*A generic bag or multiset, implemented using a linked list.

*

*% more tobe.txt

*to be or not to - be - - that - - - is

*

*% java Bag < tobe.txt

*size of bag = 14

*is

*-

*-

*-

*that

*-

*-

*be

*-

*to

*not

*or

*be

*to

*

*************************************************************************/

import java.util.Iterator;

import java.util.NoSuchElementException;

/**

*The Bag class represents a bag (or multiset) of

*generic items. It supports insertion and iterating over the

*items in arbitrary order.

*

*The add, isEmpty, and sizeoperation

*take constant time. Iteration takes time proportional to the number of items.

*

*For additional documentation, see Section 1.3 of

*Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

*/

public class Bag implements Iterable {

private int N;// number of elements in bag

private Node first;// beginning of bag

// helper linked list class

private static class Node {

public Node() { }

public T item;

public Node next;

}

/**

* Create an empty stack.

*/

public Bag() {

first = null;

N = 0;

}

/**

* Is the BAG empty?

*/

public boolean isEmpty() {

return first == null;

}

/**

* Return the number of items in the bag.

*/

public int size() {

return N;

}

/**

* Add the item to the bag.

*/

public void add(T item) {

Node oldfirst = first;

first = new Node<>();

first.item = item;

first.next = oldfirst;

N++;

}

// check internal invariants

protected static boolean check(Bag that) {

int N = that.N;

Bag.Node first = that.first;

if (N == 0) {

if (first != null) return false;

}

else if (N == 1) {

if (first == null)return false;

if (first.next != null) return false;

}

else {

if (first.next == null) return false;

}

// check internal consistency of instance variable N

int numberOfNodes = 0;

for (Bag.Node x = first; x != null; x = x.next) {

numberOfNodes++;

}

if (numberOfNodes != N) return false;

return true;

}

/**

* Return an iterator that iterates over the items in the bag.

*/

public Iterator iterator(){

return new ListIterator();

}

// an iterator, doesn't implement remove() since it's optional

private class ListIterator implements Iterator {

private Node current = first;

public boolean hasNext(){ return current != null;}

public void remove(){ throw new UnsupportedOperationException();}

public T next() {

if (!hasNext()) throw new NoSuchElementException();

T item = current.item;

current = current.next;

return item;

}

}

/**

* A test client.

*/

public static void main(String[] args) {

StdIn.fromString ("to be or not to - be - - that - - - is");

Bag bag = new Bag<>();

while (!StdIn.isEmpty()) {

String item = StdIn.readString();

bag.add(item);

}

StdOut.println("size of bag = " + bag.size());

for (String s : bag) {

StdOut.println(s);

}

}

}