Java: Return an array of booleans in a directed graph. Please complete the TODO section in the mark(int s) function
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); }
// 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;
}
===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);
}
}
}
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);
}
//depth first search algorithm, mark all nodes you visit starting
from node[s] as true
public void dfs(Node v, boolean[] marks){
marks[node.indexOf(v)] = true;
for (Node n : v.adj())
{
if(marks[node.indexOf(n)] == false)
dfs(n,marks);
}
}
// 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) {
//create a boolean array of size V, intially all nodes are marked
as false
boolean[] marks = new boolean[V];
Arrays.fill(marks, false);
//perform dfs starting from node s to populate the marks
array
dfs(node[s],marks);
return marks;
}
}
===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);
}
}
}
COMMENT DOWN FOR ANY QUERIES AND,
LEAVE A THUMBS UP IF THIS ANSWER HELPS YOU.
Java: Return an array of booleans in a directed graph. Please complete the TODO section in...
Consider the java Graph class below which represents an undirected graph in an adjacency list. How would you add a method to delete an edge from the graph? // Exercise 4.1.3 (Solution published at http://algs4.cs.princeton.edu/) package algs41; import stdlib.*; import algs13.Bag; /** * The <code>Graph</code> class represents an undirected graph of vertices * named 0 through V-1. * It supports the following operations: add an edge to the graph, * iterate over all of the neighbors adjacent to a vertex....
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements DoubleEndedList { private Node front; // first node in list private Node rear; // last node in list private int size; // number of elements in list ////////////////////////////////////////////////// // YOU MUST IMPLEMENT THE LOCATE METHOD BELOW // ////////////////////////////////////////////////// /** * Returns the position of the node containing the given value, where * the front node is at position zero and the rear node is...
Can someone help me to figure that error I have put below. JAVA ----jGRASP exec: javac -g P4Program.java P4Program.java:94: error: package list does not exist Iterator i = new list.iterator(); ^ 1 error ----jGRASP wedge2: exit code for process is 1. ----jGRASP: operation complete. Note: Below there are two different classes that work together. Each class has it's own fuctions/methods. import java.util.*; import java.io.*; public class P4Program{ public void linkedStackFromFile(){ String content = new String(); int count = 1; File...
Java Double Max Function
I need help with this top problem. The bottom is the
assignment
// return Double .NEGATIVE-INFINİTY if the linked list is empty public double max return max (first); h private static double max (Node x) f e I TODO 1.3.27 return 0; 1 package algs13; 2 import stdlib.*; 4 public class MyLinked f static class Node public Node() t 1 public double item; public Node next; 10 int N; Node first; 12 13 14 public MyLinked...
JAVA Have not gotten the public Iterator<Item> iterator() . Can someone explain it please? import java.util.Iterator; /* * GroupsQueue class supporting addition and removal of items * with respect to a given number of priorities and with * respect to the FIFO (first-in first-out) order for items * with the same priority. * * An example, where GroupsQueue would be useful is the airline * boarding process: every passenger gets assigned a priority, * usually a number, e.g., group 1,...
Complete P16.1 and P16.4 (Class Name: NewMethodDemo) Once complete, upload all .java files. For primary test class: Remember your header with name, date, and assignment. Also include class names that will be tested. Psuedocode (level 0 or mixture of level 0 and algorithm [do not number steps]) is required if main() contains more than simple statements (for example, your program includes constructs for decisions (if/else), loops, and methods. For Secondary class(es): Include a JavaDoc comment that describes the purpose of...
Improve the speed of public T get(int i) by having it work backward from the end of the array if you attempt to get a member which is closer to the end than the start. This improvement will be tested through timing tests on large lists. The method should still return null if i is not a valid index. Code import java.util.Iterator; public class DLList<T> implements Iterable<T> { private static class Node<T> { public Node<T> prev, next;...
Java help! Please help complete the min method below in bold. import java.util.Arrays; import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.List; /** * Provides an implementation of a binary search tree * with no balance constraints, implemented with linked nodes. * * * */ public class Bst<T extends Comparable<T>> implements Iterable<T> { ////////////////////////////////////////////////////////////////// // I M P L E M E N T T H E M I N M E T H O D B E L O W...
Can anyone helps to create a Test.java for the following classes please? Where the Test.java will have a Scanner roster = new Scanner(new FileReader(“roster.txt”); will be needed in this main method to read the roster.txt. public interface List { public int size(); public boolean isEmpty(); public Object get(int i) throws OutOfRangeException; public void set(int i, Object e) throws OutOfRangeException; public void add(int i, Object e) throws OutOfRangeException; public Object remove(int i) throws OutOfRangeException; } public class ArrayList implements List { ...
I need help with todo line please public class LinkedList { private Node head; public LinkedList() { head = null; } public boolean isEmpty() { return head == null; } public int size() { int count = 0; Node current = head; while (current != null) { count++; current = current.getNext(); } return count; } public void add(int data) { Node newNode = new Node(data); newNode.setNext(head); head = newNode; } public void append(int data) { Node newNode = new Node(data);...