## 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 the 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'll begin by building an undirected `Graph` class and outfitting it with some useful
methods.

## Testing

As part of the lab checkpoint, you'll have to write and show us that your code passes tests that show that your Graph constructors are working correctly. But writing more tests is strongly encouraged!

## Tasks

This lab will start out by building a graph structure.

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

**Create a**`Vertex`classWe'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 collection of Edges incident to this Vertex.`public boolean removeEdge(Edge edge)`

: removes this Edge from the collection of Edges incident to this Vertex. Returns`true`if this Edge was connected to this Vertex, otherwise returns`false`.`public Iterable<Vertex> adjacentVertices()`

: returns a collection of all the Vertices adjacent to this Vertex (the return type of this method is unimportant - it just needs to be something that is Iterable).`public Iterable<Edge> incidentEdges()`

: returns a collection of all the Edges incident to this Vertex (the return type of this method is unimportant - it just needs to be something that is Iterable).

**Create an**`Edge`classAs 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.`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`classAs 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 )`

: 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 verticies 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 collection 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(); System.out.println( this.edges ); } 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 Iterable<Vertex> getVertices()`

: returns an`Iterable`object that iterates over the vertices (don't re-invent the wheel here, this should be as simple as returning whatever structure you're using to keep track of the vertices)`public Iterable<Edge> getEdges()`

: returns an`Iterable`object that iterates over the edges.**Lab Checkpoint:**Write two tests for your graph constructors and show us that your code passes them. Test 1 should show that when you read in a graph from the supplied graph1.txt file, that it works. Test 2 should check that when you construct a random graph with probability p that your graph has around fraction p of the total possible edges it could have (compute the total possible edges using the number of vertices).`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 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`.`public HashMap<Vertex, Double> distanceFrom(Vertex source)`

: uses Djikstra'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 Djikstra's algorithm. That Psuedocode 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.