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 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 always, as you are coding up this project write tests for each class you create exercising the public methods implemented in this class.

Tasks

This lab will start out by building a graph structure.

Setup
Make a new folder for this week's project.
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 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 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.
- 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 ): 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() ;
			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.
- 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.