CS231

Graphs

A graph is a data structure that allows you to store two different kinds of objects: vertices and edges. Typically (but not always), we think of vertices as the objects that are actually being stored and edges define the connections between them. For example, one could imagine the graph of 'friend connections' of the Facebook world, where individual accounts are represented by vertices and two vertices are connected by an edge if the associated accounts are friends. Such a graph is called undirected since these edges have no inherent direction.

Another example could be the graph of instagram follows: in this case, since following an account does not necessarily mean they will follow you back, such a graph is considered 'directed' since there is an implied direction associated with an edge: perhaps an edge from some vertex u to v would denote that the account associated with vertex u follows the account associated with vertex v.

In this lab, you build an undirected Graph class and outfit it with some useful methods.

Tasks

This lab will start out by build a graph structure. You will start by building a Vertex and an Edge class. We suggest starting with the Vertex class, however both Vertex and Edge depend on each other. You will need to write both classes before being able to run code using either one.

Setup
Make a new folder for this week's project.

You will use this partial tester to show us that your Edge, Vertex and Graph constructors work for the checkpoint. When you have completed your graph, download and run the complete tester that we will use to evaluate your code. You will also need to download graph1.txt to run these tests.
Create a Vertex class
We'll let you decide how to organize this class, but you will need the following methods in the very least:
- public Vertex(): initializes a Vertex
- public Edge getEdgeTo(Vertex vertex): returns the Edge which connects this vertex and the given Vertex vertex if such an Edge exists, otherwise returns null.
- public void addEdge(Edge edge): adds the specified Edge edge to the ArrayList of Edges incident to this Vertex. Note: this should not do anything else. Any other book-keeping will be handled in the Graph class.
- public boolean removeEdge(Edge edge): removes this Edge from the ArrayList of Edges incident to this Vertex. Returns true if this Edge was connected to this Vertex, otherwise returns false. Note: this should not do anything else. Any other book-keeping will be handled in the Graph class.
- public ArrayList<Vertex> adjacentVertices(): returns an ArrayList of all the Vertices adjacent to this Vertex.
- public ArrayList<Edge> incidentEdges(): returns an ArrayList of all the Edges incident to this Vertex.
Create an Edge class
As above, we'll let you decide how to handle the fields of this class. However, you must include the following methods:
- public Edge(Vertex u, Vertex v, double distance): constructs an Edge consisting of the two vertices with a distance of the given distance. Note: all of the edges we'll be working with have distance 1, but you may want to explore edges with other distances as an extension. Note: this should not update any field for verticies v and u. This will be handled in the Graph class.
- public double distance(): returns the distance of this edge.
- public Vertex other(Vertex vertex): if vertex is one of the endpoints of this edge, returns the other end point. Otherwise returns null.
- public Vertex[] vertices(): returns an array of the two Vertices comprising this Edge. Order is arbitrary.
Create a Graph class
As above, we'll let you decide what structures you'd like to maintain in organizing this class. However, you must implement the following methods:
- public Graph(): equivalent to Graph(0).
- public Graph(int n): equivalent to Graph(n, 0.0).
- public Graph(int n, double probability): Creates a graph of n vertices where each pair of vertices has an edge between them of distance 1 with probability given by the supplied probability.
- public Graph( String filename ): One more constructor: Creates a graph based on the number of vertices and edges specified in a text file. You can copy in the following method after import import java.io.* ;. download graph1.txt to test it out with an example graph.
```
       /* *
                 * A graph constructor that takes in a filename and builds
                 * the graph with the number of vertices and specific edges
                 * specified.
                 * */
                public Graph( String filename ) {

                    try {
                        //Setup for reading the file
                        FileReader fr = new FileReader(filename);
                        BufferedReader br = new BufferedReader(fr);

                        //Get the number of vertices from the file and initialize that number of vertices
                        vertices = new ArrayList() ;
                        Integer numVertices = Integer.valueOf( br.readLine().split( ": " )[ 1 ] ) ;
                        for ( int i = 0 ; i < numVertices ; i ++ ) {
                            vertices.add( new Vertex() );
                        }
            
                        //Read in the edges specified by the file and create them
                        edges = new ArrayList() ; //If you used a different data structure to store Edges, you'll need to update this line
                        String header = br.readLine(); //We don't use the header, but have to read it to skip to the next line
                        //Read in all the lines corresponding to edges
                        String line = br.readLine();
                           while(line != null){
                               //Parse out the index of the start and end vertices of the edge
                                String[] arr = line.split(",");
                                Integer start = Integer.valueOf( arr[ 0 ] ) ;
                                Integer end = Integer.valueOf( arr[ 1 ] ) ;

                                //Make the edge that starts at start and ends at end with weight 1
                                Edge edge = new Edge( vertices.get( start ) , vertices.get( end ) , 1. ) ;
                             //Add the edge to the set of edges for each of the vertices
                             vertices.get( start ).addEdge( edge ) ;
                            vertices.get( end ).addEdge( edge ) ;
                            //Add the edge to the ArrayList of edges in the graph
                            this.edges.add( edge );

                            //Read the next line
                            line = br.readLine();
                        }
                        // call the close method of the BufferedReader:
                        br.close();
                      }
                      catch(FileNotFoundException ex) {
                        System.out.println("Graph constructor:: unable to open file " + filename + ": file not found");
                      }
                      catch(IOException ex) {
                        System.out.println("Graph constructor:: error reading file " + filename);
                      }
                }
```
- public int size(): returns the number of vertices
- public ArrayList<Vertex> getVertices(): returns an ArrayList object that can be used to iterate over the vertices (don't re-invent the wheel here, this should be as simple as returning the structure you're using to keep track of the vertices)
- public ArrayList<Edge> getEdges(): returns an ArrayList object that iterates over the edges.
- CHECKPOINT: Show us your code passes the partial tester that you downloaded at the start of the lab. Note that you must have graph1.txt downloaded as well.
- public Vertex addVertex(): Creates a new Vertex, adds it to the Graph, and returns it.
- public Edge addEdge(Vertex u, Vertex v, double distance): Creates a new Edge, adds it to the Graph (make sure the endpoints are aware of this new Edge), and returns it.
- public Edge getEdge(Vertex u, Vertex v): returns the Edge between u and v if such an Edge exists, otherwise returns null.
- public Vertex getVertex(int index): Returns the Vertex at index
- public boolean remove(Vertex vertex): if the given Vertex vertex is in this Graph, removes it and returns true. Otherwise, returns false. Remember to think about how removing a vertex impacts the edges.
- public boolean remove(Edge edge): if the given Edge is in the Graph, removes it and returns true. Otherwise, returns false. Remember to think about how removing an edge affects its endpoints!
- public HashMap<Vertex, Double> distanceFrom(Vertex source): uses Dijkstra's algorithm to compute the minimal distance in this Graph from the given Vertex source to all other Vertices in the graph. The HashMap returned maps each Vertex to its distance from the source.
  You can reference the Pseudocode in the linked Wikipedia article under the "Using a priority queue" heading when implementing Dijkstra's algorithm. That pseudocode assumes access to an add_with_priority and a decrease_priority method for the Priority Queue. Both our Priority Queue and Java's, which we suggest you use, consider the priority when adding an element. You can change the priority of an element--i.e. decrease its priority, by removing it from the Priority Queue and re-adding it. (We didn't code up a remove method but Java's Priority Queue has one.)
  
  This is another case where we will implement a custom comparator to define what priority means in this context. You can reference the Heap and the A* algorithm from the previous project as an example (remember to import java.util.Comparator). What should our custom Comparator do? Our goal is to use the Priority Queue to repeatedly get the node with the smallest distance from the source computed so far. How might we code that into the compare method for the Comparator?
  
  We recommend that you implement this using Java's implementation of a HashMap and a Priority Queue. The methods may be slightly different from what we've coded up during the semester, so remember to take a look at the documentation. You'll need to import them using import java.util.HashMap and import java.util.PriorityQueue.

Once you have completed the this lab, get started on the project.