Question

Java: Determining whether a tree exists in a directed graph

I'm trying to figure out how to determine if a tree exists in a directed graph, I need help with the isTree() function. the code for the Bag class used is below the main code if it's needed.

import algs13.Bag;
import java.util.HashSet;

// See instructions below
public class MyDigraph {

        static class Node {
                private String key;
                private Bag<Node> 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<Node> 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<V; 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<V; 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);
        }

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

}

====bag class code====

package algs13;
import stdlib.*;

public class Bag<T> implements Iterable<T> {
   private int N; // number of elements in bag
   private Node<T> first; // beginning of bag

   // helper linked list class
   private static class Node<T> {
       public Node() { }
       public T item;
       public Node<T> 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<T> oldfirst = first;
       first = new Node<>();
       first.item = item;
       first.next = oldfirst;
       N++;
   }

   // check internal invariants
   protected static <T> boolean check(Bag<T> that) {
       int N = that.N;
       Bag.Node<T> 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<T> 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<T> iterator() {
       return new ListIterator();
   }

   // an iterator, doesn't implement remove() since it's optional
   private class ListIterator implements Iterator<T> {
       private Node<T> 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<String> 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);
       }
   }
}

Answer 1

import stdlib.*;
import algs13.Bag;
import algs13.Queue;
import algs41.Graph;

import java.util.HashSet;

// See instructions below
public class MyDigraph {

static class Node {
private String key;
private Bag<Node> 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<Node> 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<V; 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<V; 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);
}

// 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) {
           boolean nodeVisit[] = new boolean[s];
boolean cycleArray[] = new boolean[s];

for (int i = 0; i < s; i++) {
if (checkCycle(i, nodeVisit, cycleArray))
return true;
}
return false;
}

public boolean checkCycle(int vt, boolean[] nodeVisit, boolean[] cycleArray) {
nodeVisit[vt] = true;
cycleArray[vt] = true;

for (int i = 0; i < adjList[vt].size(); i++) {
int adjVertex = adjList[vt].get(i);
if (!nodeVisit[adjVertex] && checkCycle(adjVertex, nodeVisit, cycleArray)) {
return true;
} else if (cycleArray[adjVertex])
return true;
}
cycleArray[vt] = false;
return false;
}
}

====bag class code====

package algs13;
import stdlib.*;

public class Bag<T> implements Iterable<T> {
private int N; // number of elements in bag
private Node<T> first; // beginning of bag

// helper linked list class
private static class Node<T> {
public Node() { }
public T item;
public Node<T> 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<T> oldfirst = first;
first = new Node<>();
first.item = item;
first.next = oldfirst;
N++;
}

// check internal invariants
protected static <T> boolean check(Bag<T> that) {
int N = that.N;
Bag.Node<T> 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<T> 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<T> iterator() {
return new ListIterator();
}

// an iterator, doesn't implement remove() since it's optional
private class ListIterator implements Iterator<T> {
private Node<T> 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<String> 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);
}
}
}