Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· OpenAIAi2 WildChat-4.8M (AI2)

1. Complete a new class for this scenario called SocialNetwork Create a class called…

  1. User
    1. Complete a new class for this scenario called SocialNetwork Create a class called SocialNetwork. This class should be based on the class DiGraph. You can either: • Have a field in the class SocialNetwork that is an object DiGraph (better) • Make SocialNetwork a subclass of DiGraph with additional methods given below (best) The constructor for this class should have no parameters, and it should create and initialise an adjacency-list-based directed graph that represents the SocialNetwork network as shown in the diagram. For example: SocialNetwork theSocialNetwork = new SocialNetwork(); should create the graph as shown in the diagram above. [Up to 10 marks for use of inheritance]
    2. Write the method: public ArrayList broadcastsTo(String person) This method takes the name of a person and should return an ArrayList of String objects, which contains the names all the followers of person. For example: theSocialNetwork.broadcastsTo(Names.networkMembers[DANA]); should return an ArrayList that contains [Bina, Cato, Fern, Geno] and nothing else. Check the edges to resolve this method [10 marks]
    3. Refactor the depth first search method in the class Traversal Current method header: public static void DFS(ArrayList[] adjList, Integer startNode) Refactored method header: public static boolean DFS(ArrayList[] adjList, Integer startNode, Integer destinationNode) The refactored method will return true if the destinationNode is encountered in the subgraph descending from startNode. [5 marks]
    4. Write the method: public boolean canReach(String source, String target) This method takes the name of a person starting a broadcasting a story (source) and the name of the person that the story is broadcast to (target). It uses the refactored depth first search to see if the story will get from the source to the target and should return true if the story will get from the source to the target, and false if there is no path from the source to the target. [5 marks]
    5. Refactor the breadth first search method in the class Traversal Current method header: public static void BFS(ArrayList[] adjList, Integer startNode) Refactored method header: public static ArrayList BFS(ArrayList[] adjList, Integer startNode) The refactored method will return an ArrayList of all of the names of the visited nodes in the graph structure descending from startNode. [5 marks]
    6. Write the method: public ArrayList receiversOf(String person) This method takes the name of a person who has started a story and uses a breadth first search to return an ArrayList of String objects that contains the names of all the person who will receive the story broadcast by that person. For example: theSocialNetwork.receiversOf(Names.networkMembers[ABEL]); should return an ArrayList that contains [Bina, Cato, Dana, Eden, Fern, Geno, Hedy, Inez, Jodi] and nothing else. [5 marks] Correct Output for each test

    broadcastTo test Followers of Abel: [Cato] Followers of Bina: [Abel] Followers of Cato: [Abel] Followers of Dana: [Bina, Cato, Fern, Geno] Followers of Eden: [Cato, Dana, Fern, Jodi] Followers of Fern: [Dana] Followers of Geno: [Fern, Inez] Followers of Hedy: [Fern, Jodi] Followers of Inez: [Geno] Followers of Jodi: [Inez]

    canReach test Abel can reach Bina Cato Dana Eden Fern Geno Hedy Inez Jodi Bina can reach Dana Eden Fern Geno Hedy Inez Jodi Cato can reach Abel Bina Dana Eden Fern Geno Hedy Inez Jodi Dana can reach Eden Fern Geno Hedy Inez Jodi Eden can reach no one! Fern can reach Dana Eden Geno Hedy Inez Jodi Geno can reach Dana Eden Fern Hedy Inez Jodi Hedy can reach no one! Inez can reach Dana Eden Fern Geno Hedy Jodi Jodi can reach Eden Hedy

    receiversOf test Receivers of Abel: [Bina, Cato, Dana, Eden, Fern, Geno, Hedy, Inez, Jodi] Receivers of Bina: [Dana, Fern, Eden, Geno, Hedy, Inez, Jodi] Receivers of Cato: [Abel, Dana, Eden, Bina, Fern, Geno, Hedy, Inez, Jodi] Receivers of Dana: [Fern, Eden, Geno, Hedy, Inez, Jodi] Receivers of Eden: [] Receivers of Fern: [Dana, Eden, Geno, Hedy, Inez, Jodi] Receivers of Geno: [Dana, Inez, Fern, Eden, Jodi, Hedy] Receivers of Hedy: [] Receivers of Inez: [Geno, Jodi, Dana, Eden, Hedy, Fern] Receivers of Jodi: [Eden, Hedy]

  2. Assistant

    import java.util.ArrayList;

    public class SocialNetwork extends DiGraph { // The constructor for the SocialNetwork class public SocialNetwork() { super(Names.networkMembers.length); for (int i = 0; i < Names.networkEdges.length; i++) { addEdge(Names.networkEdges[i][0], Names.networkEdges[i][1]); } }

    // Method to return the followers of a person
    public ArrayList<String> broadcastsTo(String person) {
        return getNameList(getFollowers(getIndex(person)));
    }
    
    // Method to check if the story will reach from source to target
    public boolean canReach(String source, String target) {
        return Traversal.DFS(adjList, getIndex(source), getIndex(target));
    }
    
    // Method to return the names of all the person who will receive the story broadcast by a person
    public ArrayList<String> receiversOf(String person) {
        return Traversal.BFS(adjList, getIndex(person));
    }
    
    private int getIndex(String name) {
        for (int i = 0; i < Names.networkMembers.length; i++) {
            if (name.equals(Names.networkMembers[i])) {
                return i;
            }
        }
        return -1;
    }
    
    private ArrayList<String> getNameList(ArrayList<Integer> indexList) {
        ArrayList<String> nameList = new ArrayList<String>();
        for (Integer index : indexList) {
            nameList.add(Names.networkMembers[index]);
        }
        return nameList;
    }
    
    public static void main(String[] args) {
        SocialNetwork theSocialNetwork = new SocialNetwork();
    
        // Test broadcastTo
        System.out.println("Broadcast to test");
        for (String person : Names.networkMembers) {
            System.out.println("Followers of " + person + ": " + theSocialNetwork.broadcastsTo(person));
        }
    
        // Test canReach
        System.out.println("Can reach test");
        for (String source : Names.networkMembers) {
            System.out.print(source + " can reach ");
            for (String target : Names.networkMembers) {
                if (theSocialNetwork.canReach(source, target)) {
                    System.out.print(target + " ");
                }
            }
            System.out.println();
        }
    
        // Test receiversOf
        System.out.println("Receivers of test");
        for (String person : Names.networkMembers) {
            System.out.println("Receivers of " + person + ": " + theSocialNetwork.receiversOf(person));
        }
    }
    

    }

  3. User

    Here are the classes I already have so rewrite the code accordingly: public interface Stack { /** * Removes and returns the item at the top of the stack * @return the item at the top the stack */ public Object pop();

    /**
     * Inserts an object to the top of the stack
     * @param o the object to be pushed
     */
    public void push(Object o);
    
    /**
     * Tells us if the stack is empty
     * @return true if the stack is empty
     */
    public boolean isEmpty();
    
    /**
     * Returns the number of items in the stack
     * @return the number of items in the stack
     */
    public int size();
    
    /**
     * Tells us the item at the top without removing it
     * @return the object at the top of the stack
     */
    public Object top();
    

    }

    import java.util.ArrayList;

    public class Traversal { /** * REFACTOR THIS METHOD * Perform a BFS traversal of the graph, printing the nodes in the order visited */ public static void BFS(ArrayList[] adjList, Integer startNode) { //create the list of visited nodes and the queue ArrayList visitedNodes = new ArrayList<>(); Queue theQueue = new ArrayQueue();

        //mark the start as visited and put it in the Queue
        visitedNodes.add(startNode);
        theQueue.enqueue(startNode);
    
        while(!theQueue.isEmpty()){
            Integer item = (Integer) theQueue.dequeue();
            //mark all the neighbours of the item which have not been visited as visited and add them to the queue
            for (Integer neighbour:adjList[item]){
                if (!visitedNodes.contains(neighbour)){
                    visitedNodes.add(neighbour);
                    theQueue.enqueue(neighbour);
                }
            }
        }
    }
    
    /**
     * REFACTOR THIS METHOD
     * Perform a DFS traversal of the graph
     * The refactored method will return true if the destinationNode is encountered in the subgraph descending from
     * startNode
     */
    public static void DFS(ArrayList<Integer>[] adjList, Integer startNode){
    
        //create the list of visited nodes and the stack
        ArrayList<Integer> visitedNodes = new ArrayList<>();
        Stack theStack = new ArrayStack();
    
        //mark the start as visited and put it in the stack
        visitedNodes.add(startNode);
        theStack.push(startNode);
    
        while(!theStack.isEmpty()){
            Integer item = (Integer) theStack.pop();
    
            //mark all the neighbours of the item which have not been visited as visited and add them to the stack
            for (Integer neighbour:adjList[item]){
                if (!visitedNodes.contains(neighbour)){
                    visitedNodes.add(neighbour);
                    theStack.push(neighbour);
                }
            }
        }
    }
    

    }

    public class ArrayQueue implements Queue { //fields to represent our stack in an array

    //the array of items
    private Object[] items;
    
    //maximum capacity
    private int maximum;
    
    //pointer to the position of the front of the queue
    //this points to 0 when the stack is empty
    private int front;
    
    //Actual number of items in the queue
    private int size;
    
    //Constructor
    public ArrayQueue(){
        //set the capacity to 20
        maximum = 20;
        
        //create the array
        items = new Object[maximum];
        
        //set the front to 0 as the stack is empty
        front = 0;
        
        //set the size to 0
        size = 0;
    }
            
    
    @Override
    public Object dequeue() {
        // first check if the queue is empty. 
        // If it is, print an error message and return null,
        // otherwise return the item at the front,
        // decrement the size and increment the front pointer.
        if (isEmpty()) {
            System.out.println("Stack Empty");
            return null;
        } else {
            Object answer = items[front];
            front = (front + 1) % maximum;
            size--;
            return answer;
        }
    }
    
    @Override
    public void enqueue(Object o) {
        // first check if the queue is full.
        // If it is, print an error message,
        // else calculate the position of the back of the queue
        // and put the item in the back, 
        // and finally increment the size
        if (size == maximum){
           System.out.println("Queue full");
        } else {
            int back = (front + size) % maximum;
            items[back] = o;
            size++;
        }
    }
    
    @Override
    public boolean isEmpty() {
        //use the size!
        return (size==0);
    }
    
    @Override
    public int size() {
        //use the size!
        return size;
    }
    
    @Override
    public Object front() {
        // First check if the queue is empty.
        // If it is, print an error message and return null,
        // otherwise return the item at the front.
        
        if (isEmpty()) {
            System.out.println("Stack Empty");
            return null;
        } else {
            return items[front];
        }
    }
    

    }

    public class ArrayStack implements Stack { //fields to represent our stack in an array

    //the array of items
    private Object[] items;
    
    //maximum capacity
    private int maximum;
    
    //pointer to the position of the top of the stack
    //this points to -1 when the stack is empty
    private int top;
    
    public ArrayStack(){
        //set the capacity to 20
        maximum = 20;
        
        //create the array
        items = new Object[maximum];
        
        //set the top to -1 as the stack is empty
        top = -1;
    }
    
    @Override
    public Object pop() {
        // First check if the stack is empty.
        // If it is, print an error message and return null,
        // otherwise, return the item the top is pointing to 
        // and decrement the top pointer
        if (isEmpty()) {
            System.out.println("Stack Empty");
            return null;
        } else {
            Object answer = items[top];
            top--;
            return answer;
        }
    }
    
    @Override
    public void push(Object o) {
        // First check if the array is full.
        // If it is, print an error message,
        // else increment the top and put the item in that space
        if (top == (maximum - 1)){
           System.out.println("Stack full");
        } else {
            top++;
            items[top] = o;
        }
    }
    
    @Override
    public boolean isEmpty() {
        // The stack is empty if the top is pointing to -1
        return (top == -1);
    }
    
    @Override
    public int size() {
        // The size of the stack can be calculated using the position of top
        return(top + 1);
    }
    
    @Override
    public Object top() {
        // First check if the stack is empty. 
        // If it is, print an error message and return null,
        // otherwise, return the item the top is pointing to. 
        if (isEmpty()) {
            System.out.println("Stack Empty");
            return null;
        } else {
            return items[top];
        }
    }
    

    }

    import java.util.ArrayList;

    public class DiGraph { protected int numberOfNodes; protected ArrayList[] adjacencyList;

    /**
     * Constructor for a directed graphs with a number of nodes but no edges.
     * @param nodes the number of nodes in the graph
     */
    public DiGraph(int nodes) {
        //initialise the number of nodes
        numberOfNodes = nodes;
        //make the array of ArrayLists
        adjacencyList = new ArrayList [nodes];
        //go through each node and make a new ArrayList for that node
        for (int i = 0; i < nodes; i++) {
            adjacencyList[i] = new ArrayList<Integer>();
        }
    }
    
    /**
     * Add an edge between the two nodes given
     * @param fromNode the node the edge starts from
     * @param toNode the node that the edge goes to
     */
    public void addEdge(int fromNode, int toNode){
        adjacencyList[fromNode].add(toNode);
    }
    
    /**
     * Return the number of nodes in the graph
     * @return the number of nodes in the graph
     */
    public int getNumberOfNodes() {return numberOfNodes; }
    
    /**
     * Determine whether there is an edge between the two nodes given
     * @param fromNode the node the edge starts from
     * @param toNode the node that the edge goes to
     * @return true if there is an edge between fromNode and toNode, false otherwise
     */
    public boolean hasEdge(int fromNode, int toNode) {return adjacencyList[fromNode].contains(toNode); }
    
    /**
     * Print the adjacency list representation of the graph
     */
    public void printAdjacencyList(){
        System.out.println("Number of nodes = "+ numberOfNodes);
        for (int i = 0; i< adjacencyList.length; i++){
            System.out.print("Neighbours of " + i + " : ");
            for (Integer neighbour: adjacencyList[i]) {
                System.out.print(neighbour + " ");
            }
            System.out.println();
        }
    }
    

    }

    public class Main { public static final String DASHES = new String(new char[80]).replace("\0", "-"); /** * COMPLETE THIS METHOD to create the graph structure shown in the project brief * @param socialNetwork stores the graph structure */ private static void buildGraph(SocialNetwork socialNetwork) {

    }
    
    /**
     * Full test for the broadcastTo method
     * @param theSocialNetwork stores the graph structure
     */
    private static void testBroadCastTo(SocialNetwork theSocialNetwork) {
        System.out.println(DASHES);
        System.out.println("broadcastTo test\n");
        for (int i = 0; i < Names.networkMembers.length; i++) {
            System.out.print("Followers of " + Names.networkMembers[i] + ": ");
            System.out.println(theSocialNetwork.broadcastsTo(Names.networkMembers[i]));
        }
        System.out.println();
    }
    /**
     * Full test for the canReach method
     * @param theSocialNetwork stores the graph structure
     */
    private static void canReachTest(SocialNetwork theSocialNetwork) {
        System.out.println(DASHES);
        System.out.println("canReach test\n");
        StringBuilder canReach = new StringBuilder();
        for (int i = 0; i < Names.networkMembers.length; i++) {
            for (int j = 0; j < Names.networkMembers.length; j++) {
                if (j != i && theSocialNetwork.canReach(Names.networkMembers[i], Names.networkMembers[j])) {
                    canReach.append(Names.networkMembers[j]).append(" ");
                }
            }
            if (canReach.length() == 0) {
                canReach = new StringBuilder(" no one!");
            }
            System.out.println(Names.networkMembers[i] + " can reach " + canReach);
            canReach = new StringBuilder();
        }
    }
    /**
     * Full test for the receiversOf method
     * @param theSocialNetwork stores the graph structure
     */
    private static void receiversOfTest(SocialNetwork theSocialNetwork) {
        System.out.println(DASHES);
        System.out.println("receiversOf test\n");
        for (int i = 0; i < Names.networkMembers.length; i++) {
            System.out.print("Receivers of " + Names.networkMembers[i] + ": ");
            System.out.println(theSocialNetwork.receiversOf(Names.networkMembers[i]));
        }
        System.out.println();
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        SocialNetwork theSocialNetwork = new SocialNetwork();
        buildGraph(theSocialNetwork);
        testBroadCastTo(theSocialNetwork);
    
        canReachTest(theSocialNetwork);
    
        receiversOfTest(theSocialNetwork);
    }
    

    }

    public class Names { public static final int ABEL = 0; public static final int BINA = 1; public static final int CATO = 2; public static final int DANA = 3; public static final int EDEN = 4; public static final int FERN = 5; public static final int GENO = 6; public static final int HEDY = 7; public static final int INEZ = 8; public static final int JODY = 9; public static final String [] networkMembers = { "Abel", "Bina", "Cato", "Dana", "Eden", "Fern", "Geno", "Hedy", "Inez", "Jodi" }; }

    public interface Queue { /** * Removes and returns the item at the front of the queue * @return the item at the front the queue */ public Object dequeue();

    /**
     * Inserts an object to the back of the queue
     * @param o the object to be pushed
     */
    public void enqueue(Object o);
    
    
    /**
     * Tells us if the queue is empty
     * @return true if the queue is empty
     */
    public boolean isEmpty();
    
    /**
     * Returns the number of items in the queue
     * @return the number of items in the queue
     */
    public int size();
    
    /**
     * Tells us the item at the front without removing it
     * @return the object at the front of the queue 
     */
    public Object front();
    

    }

    import java.util.ArrayList; import java.util.Arrays; public class SocialNetwork { /** * COMPLETE THIS METHOD * takes the name of a person and should return an ArrayList of String objects, which contains * the names all the followers of person. * @param person - the name of the Person to check * @return */ public ArrayList broadcastsTo(String person){ return null; }

    /**
     * COMPLETE THIS METHOD
     * Method takes the name of a person starting a broadcasting a story (source) and the name of the person that the
     * story is broadcast to (target).
     * It uses the refactored depth first search to see if the story will get from the source to the target and
     * should return true if the story will get from the source to the target
     * and false if there is no path from the source to the target.
     * @param source - the name of the Person to check
     * @param target - the name of the target to check
     * @return true if the story will get from the source to the target and false if there is no path from the
     * source to the target.
     */
    public boolean canReach(String source, String target) {
        return false;
    }
    
    /**
     * COMPLETE THIS METHOD
     * Method takes the name of a person who has started a story and uses a breadth first search to return an
     * ArrayList of String objects that contains the names of all the person who will receive the story
     * broadcast by that person.
     * @param person name of the person to check
     * @return an ArrayList of String objects that contains the names of all the person who will receive the story
     */
    public ArrayList<String> receiversOf(String person){
        return null;
    }
    

    }

  4. Assistant

    Based on the previously provided code for classes, I have adjusted the SocialNetwork, Traversal, and Main classes according to the given requirements:

    public class SocialNetwork extends DiGraph {
        public SocialNetwork() {
            super(Names.networkMembers.length);
            for (int i = 0; i < Names.networkEdges.length; i++) {
                addEdge(Names.networkEdges[i][0], Names.networkEdges[i][1]);
            }
        }
    
        public ArrayList<String> broadcastsTo(String person) {
            return getNameList(getFollowers(getIndex(person)));
        }
    
        public boolean canReach(String source, String target) {
            return Traversal.DFS(adjList, getIndex(source), getIndex(target));
        }
    
        public ArrayList<String> receiversOf(String person) {
            return Traversal.BFS(adjList, getIndex(person));
        }
    
        private int getIndex(String name) {
            for (int i = 0; i < Names.networkMembers.length; i++) {
                if (name.equals(Names.networkMembers[i])) {
                    return i;
                }
            }
            return -1;
        }
    
        private ArrayList<String> getNameList(ArrayList<Integer> indexList) {
            ArrayList<String> nameList = new ArrayList<String>();
            for (Integer index : indexList) {
                nameList.add(Names.networkMembers[index]);
            }
            return nameList;
        }
    }
    
    public class Traversal {
        public static ArrayList<String> BFS(ArrayList<Integer>[] adjList, Integer startNode) {
            ArrayList<Integer> visitedNodes = new ArrayList<>();
            ArrayList<String> visitedNames = new ArrayList<>();
            Queue theQueue = new ArrayQueue();
    
            visitedNodes.add(startNode);
            theQueue.enqueue(startNode);
    
            while(!theQueue.isEmpty()){
                Integer item = (Integer) theQueue.dequeue();
                for (Integer neighbour:adjList[item]){
                    if (!visitedNodes.contains(neighbour)){
                        visitedNodes.add(neighbour);
                        visitedNames.add(Names.networkMembers[neighbour]);
                        theQueue.enqueue(neighbour);
                    }
                }
            }
    
            return visitedNames;
        }
    
        public static boolean DFS(ArrayList<Integer>[] adjList, Integer startNode, Integer destinationNode){
            ArrayList<Integer> visitedNodes = new ArrayList<>();
            Stack theStack = new ArrayStack();
    
            visitedNodes.add(startNode);
            theStack.push(startNode);
    
            while(!theStack.isEmpty()){
                Integer item = (Integer) theStack.pop();
                if (item.equals(destinationNode)) {
                    return true;
                }
                for (Integer neighbour:adjList[item]){
                    if (!visitedNodes.contains(neighbour)){
                        visitedNodes.add(neighbour);
                        theStack.push(neighbour);
                    }
                }
            }
    
            return false;
        }
    }
    
    public class Main {
        private static void testBroadCastTo(SocialNetwork theSocialNetwork) {
            System.out.println("Broadcast to test");
            for (String person : Names.networkMembers) {
                System.out.println("Followers of " + person + ": " + theSocialNetwork.broadcastsTo(person));
            }
            System.out.println();
        }
    
        private static void canReachTest(SocialNetwork theSocialNetwork) {
            System.out.println("Can reach test");
            for (String source : Names.networkMembers) {
                System.out.print(source + " can reach ");
                for (String target : Names.networkMembers) {
                    if (theSocialNetwork.canReach(source, target)) {
                        System.out.print(target + " ");
                    }
                }
                System.out.println();
            }
        }
    
        private static void receiversOfTest(SocialNetwork theSocialNetwork) {
            System.out.println("Receivers of test");
            for (String person : Names.networkMembers) {
                System.out.println("Receivers of " + person + ": " + theSocialNetwork.receiversOf(person));
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            SocialNetwork theSocialNetwork = new SocialNetwork();
    
            testBroadCastTo(theSocialNetwork);
            canReachTest(theSocialNetwork);
            receiversOfTest(theSocialNetwork);
        }
    }
    

    After updating the classes, the provided code for other classes remains unchanged. To make sure the code compiles, please compile it with all the given classes in the same directory.