Practical_7.pdf Department of Computer Science COS212: Practical 7 Release: Monday 31 May 2021, 18:00 Deadline: Friday 4 June 2021, 18:00 PLAGIARISM POLICY UNIVERSITY OF PRETORIA The Department of...

Assignment instructions in the file


Practical_7.pdf Department of Computer Science COS212: Practical 7 Release: Monday 31 May 2021, 18:00 Deadline: Friday 4 June 2021, 18:00 PLAGIARISM POLICY UNIVERSITY OF PRETORIA The Department of Computer Science considers plagiarism as a serious offence. Disciplinary action will be taken against students who commit plagiarism. Plagiarism includes copying someone else’s work without consent, copying a friend’s work (even with consent) and copying material (such as text or program code) from the Internet. Copying will not be tolerated in this course. For a formal definition of plagiarism, the student is referred to http://www.library.up.ac.za/ plagiarism/index.htm (from the main page of the University of Pretoria site, follow the Library quick link, and then choose the Plagiarism option under the Services menu). If you have any form of question regarding this, please ask one of the lecturers, to avoid any misunderstanding. Also note that the OOP principle of code re-use does not mean that you should copy and adapt code to suit your solution. http://www.library.up.ac.za/plagiarism/index.htm http://www.library.up.ac.za/plagiarism/index.htm Objectives The aim of this practical is to learn how to create Graphs and how to find shortest paths and articulation points. Instructions Complete the task below. Certain classes have been provided for you alongside this specifi- cation in the Student files folder. You have been given a main file which will test some code functionality, but it is by no means intended to provide extensive test coverage. You are encouraged to edit this file and test your code more thoroughly. Remember to test boundary cases. Submission instructions are given at the end of this document. Graphs - Shortest Path & Articulation Points A Graph is a collection of vertices and the connections between them. The connections are called edges. Each edge connects a pair of vertices. If the edges are not bi-directional, but directed from the start vertex to the end vertex, the graph is a directional graph or digraph. Each edge can be assigned a number that can represent values such as cost, distance, length or weight. Such a graph is then called a weighted digraph. You are required to implement a Shortest Path algorithm for a weighted digraph with positive and negative weights. Your algorithm must be able to deal with unreachable nodes. Your algorithm must also be able to handle cycles and self-cycles. Negative cycles should be detected. You have been given functional Vertex and Edge classes and a partially implemented WeightedDirectedGraph class to use. In addition, your second task requires you to find articulation points in an undirected graph. Articulation points are vertices in a graph which, when removed, cause the graph to separate into two subgraphs with no paths between the two subgraphs. A graph may have no articulation points at all, depending on its degree of connectivity. You have been given an UnweightedUndirectedGraph class for this task, which will also make use of the Vertex and Edge class. Task 1: Shortest Path [20] List getShortestPath(Vertex sourceVertex, Vertex targetVertex) This function should return the shortest path to the given targetVertex. The returned list should contain all the vertices from the source vertex to the target vertex in the order that describes the shortest path. Should the target vertex not be reachable, an empty list should be returned (not null). The predecessors can be stored in the provided field in the Vertex class. If a negative cycle is detected, null should be returned. The pre-condition is that the graph is a weighted digraph. This task makes use of the Edge, Vertex and WeightedDirectedGraph classes. 2 Task 2: Articulation Points [20] List getArticulationPoints() This function should return a sorted list of the vertices which are articulation points in an undirected graph . Your function should add all the vertices which are articulation points to the list called articulationPoints provided for you in the UnweightedUndirectedGraph class. A helper function has been provided called sortArticulationPoints() which will then sort your articulation points. After you have sorted the articulation points you have found, you can return the articulationPoints list. Refer to Section 8.6.1 in the textbook for a description of articulation points in an undirected graph. Figure 1 shows the articu- lation points on a graph highlighted in red. If there are no articulation points or the graph is empty, return an empty list. This task makes use of the Edge, Vertex, Unweighte- dUndirectedGraph and VertexNameSorter classes. Figure 1: Graph from figure 8.16 in the textbook with articulation points highlighted in red. You should use your own helper functions to assist in implementing these methods as per specification. However, you may not modify any of the given method signatures. You may add fields to the provided classes, but you should not add additional classes. Do not add any additional imports. Submission You need to submit your source files on the Fitch Fork website (https://ff.cs.up.ac.za/). All methods need to be implemented (or at least stubbed) before submission. The fol- lowing files: Edge.java, Vertex.java, WeightedDirectedGraph.java and Unweight- edUndirectedGraph.java, should be placed in a zip archive named uXXXXXXXX.zip where XXXXXXXX is your student number. There is no need to include any other files in your submission. You have 4 days to complete this practical, regardless of which practical session you attend. You have 5 submissions and your best mark will be your final mark. 3 https://ff.cs.up.ac.za/ Upload your archive to the Practical 7 slot on the Fitch Fork website. Submit your work before the deadline. No late submissions will be accepted! 4 PLAGIARISM POLICY Student files/Edge.java Student files/Edge.java public class Edge {     private Vertex startVertex;     private Vertex endVertex;     private double weight;     public Edge(Vertex startVertex, Vertex endVertex, double weight) {         this.startVertex = startVertex;         this.endVertex = endVertex;         this.weight = weight;     }     /*Returns the other vertex connected to the vertex in the argument*/     public Vertex getOtherVertex(Vertex in) {         if (startVertex == in)             return endVertex;         else if (endVertex == in)             return startVertex;         else             return null;     }     public Vertex getStartVertex() {         return startVertex;     }     public void setStartVertex(Vertex startVertex) {         this.startVertex = startVertex;     }     public Vertex getEndVertex() {         return endVertex;     }     public void setEndVertex(Vertex endVertex) {         this.endVertex = endVertex;     }     public double getWeight() {         return weight;     }     public void setWeight(double weight) {         this.weight = weight;     } } Student files/Main.java Student files/Main.java public class Main {     /* some helper functions to help you construct the two types of graphs */          private static void connectDirectedVertices(Vertex sourceVertex, Vertex destinationVertex, double cost) {         Edge e = new Edge(sourceVertex, destinationVertex, cost); /* edge has a cost */         sourceVertex.addNeighbour(e); /* only direct the edge from the source vertex to destination (but not vice-versa) */     }     private static void connectUndirectedVertices(Vertex v1, Vertex v2) {         Edge e = new Edge(v1, v2, 0); /* the weight of these edges are all set to 0 and can be ignored */         v1.addNeighbour(e);         v2.addNeighbour(e); /* add the edge to both vertices essentially making the edge function in both directions */     }     public static void main(String[] args) {         // TASK 1: Shortest path test         Vertex vertexL = new Vertex("L");         Vertex vertexM = new Vertex("M");         Vertex vertexN = new Vertex("N");         Vertex vertexO = new Vertex("O");         Vertex vertexP = new Vertex("P");         connectDirectedVertices(vertexL, vertexN, 10);         connectDirectedVertices(vertexL, vertexM, 17);         connectDirectedVertices(vertexN, vertexM, 5);         connectDirectedVertices(vertexN, vertexO, 9);         connectDirectedVertices(vertexN, vertexP, 11);         connectDirectedVertices(vertexM, vertexO, 1);         connectDirectedVertices(vertexO, vertexP, 6);         WeightedDirectedGraph directedGraph = new WeightedDirectedGraph();         directedGraph.addVertex(vertexL);         directedGraph.addVertex(vertexM);         directedGraph.addVertex(vertexN);         directedGraph.addVertex(vertexO);         directedGraph.addVertex(vertexP);         System.out.println("Shortest Path from " + vertexL.getName() + " to " + vertexP.getName() + " : " + directedGraph.getShortestPath(vertexL, vertexP));         /* Expected output            Shortest Path from L to P : [L, N, P]         */         // TASK 2 Constructing the undirected graph from page 430 in the text book Figure 8.16 (a)         Vertex vertexA = new Vertex("A");         Vertex vertexB = new Vertex("B");         Vertex vertexC = new Vertex("C");         Vertex vertexD = new Vertex("D");         Vertex vertexE = new Vertex("E");         Vertex vertexF = new Vertex("F");         Vertex vertexG = new Vertex("G");         Vertex vertexH = new Vertex("H");         Vertex vertexI = new Vertex("I");         Vertex vertexJ = new Vertex("J");         Vertex vertexK = new Vertex("K");         UnweightedUndirectedGraph undirectedGraph = new UnweightedUndirectedGraph();         connectUndirectedVertices(vertexA, vertexC);         connectUndirectedVertices(vertexA, vertexF);         connectUndirectedVertices(vertexA, vertexD);         connectUndirectedVertices(vertexC, vertexF);         connectUndirectedVertices(vertexF, vertexD);         connectUndirectedVertices(vertexD, vertexB);         connectUndirectedVertices(vertexD, vertexE);         connectUndirectedVertices(vertexB, vertexE);         connectUndirectedVertices(vertexB, vertexG);         connectUndirectedVertices(vertexB, vertexH);         connectUndirectedVertices(vertexG, vertexH);         connectUndirectedVertices(vertexG, vertexK);         connectUndirectedVertices(vertexH, vertexK);         connectUndirectedVertices(vertexH, vertexI);         connectUndirectedVertices(vertexI, vertexJ);         undirectedGraph.addVertex(vertexA);         undirectedGraph.addVertex(vertexB);         undirectedGraph.addVertex(vertexC);         undirectedGraph.addVertex(vertexD);         undirectedGraph.addVertex(vertexE);         undirectedGraph.addVertex(vertexF);         undirectedGraph.addVertex(vertexG);         undirectedGraph.addVertex(vertexH);         undirectedGraph.addVertex(vertexI);         undirectedGraph.addVertex(vertexJ);         undirectedGraph.addVertex(vertexK);         System.out.println("Articulation points: " + undirectedGraph.getArticulationPoints());         /* Expected output            Articulation points: [B, D, H, I]          */     } } Student files/UnweightedUndirectedGraph.java Student files/UnweightedUndirectedGraph.java import java.util.ArrayList; import java.util.List; public class UnweightedUndirectedGraph {     private List verticesList; //contains all vertices in this graph     private List articulationPoints; // add articulation points for this graph to this list     public UnweightedUndirectedGraph() {         this.verticesList = new ArrayList<>();         this.articulationPoints = new ArrayList<>();     }     public void addVertex(Vertex vertex) {         this.verticesList.add(vertex);     }     /*Sorts the articulationPoints list based on the names of the vertices. Do not modify this*/     public void sortArticulationPoints() {         if (articulationPoints != null)             articulationPoints.sort(new VertexNameSorter());     }     ////// Implement the methods below this line //////     public List getArticulationPoints() {         /*            Your code to add articulation points to the list goes here.          You may add helper functions and fields. No extra imports or classes.          */                  sortArticulationPoints(); // sort list before returning         return articulationPoints;     } } Student files/Vertex.java Student files/Vertex.java import java.util.ArrayList; import java.util.List; public class Vertex implements Comparable {     private String name;     private List adjacenciesList;     private double distance = Double.POSITIVE_INFINITY;     private boolean visited = false;     private Vertex predecessor;     public Vertex(String name) {         this.name = name;         this.adjacenciesList = new ArrayList<>();     }     public void addNeighbour(Edge edge) {         this.adjacenciesList.add(edge);     }     public String getName() {         return name;     }     public void setName(String name) {         this.name = name;     }     public List getAdjacenciesList() {         return adjacenciesList;     }     public void setAdjacenciesList(List adjacenciesList) {         this.adjacenciesList = adjacenciesList;     }     public double getDistance() {         return distance;     }     public void setDistance(double distance) {         this.distance = distance;     }     public boolean isVisited() {         return visited;     }     public void setVisited(boolean visited) {         this.visited = visited;     }     public Vertex getPredecessor() {         return predecessor;     }     public void setPredecessor(Vertex predecessor) {         this.predecessor = predecessor;     }     @Override     public String toString() {         return this.name; // Do not modify     }     @Override     public int compareTo(Vertex otherVertex) {         return Double.compare(this.distance, otherVertex.getDistance());     } } Student files/VertexNameSorter.java Student files/VertexNameSorter.java //DO NOT MODIFY THIS FILE import java.util.Comparator; public class VertexNameSorter implements Comparator {     @Override     public int compare(Vertex v1, Vertex v2) {         return v1.getName().compareTo(v2.getName());     } } Student files/WeightedDirectedGraph.java Student files/WeightedDirectedGraph.java import java.util.ArrayList; import java.util.Collections; import java.util.List; public class WeightedDirectedGraph {     private List verticesList; //contains all vertices in this graph     public WeightedDirectedGraph() {         this.verticesList = new ArrayList<>();     }     public void addVertex(Vertex vertex) {         this.verticesList.add(vertex);     }     ////// Implement the methods below this line //////     public List getShortestPath(Vertex sourceVertex, Vertex targetVertex) {         // your code goes here     } }