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 a 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.

  1. Setup

    Make a new folder for this week's project.

  2. 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).

  3. 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.
    • 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.

  4. 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 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.
    • 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.

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