Part 1 - Graph Implementation

Your goal for this part of the assignment is to develop an efficient implementation for a directed, unweighted, graph ADT.

• Graph.java - Graph Interface
• HashGraph.java - You need to provide this

The following table indicates the methods in the graph ADT and the required efficiency for each.

Here is some sample code illustrating how this Graph ADT may be used:

    // Create a graph using Strings as node labels
    Graph<String> graph1 = new HashGraph<>();

    graph1.addNode("A");             // The node A is added
    graph1.addEdge("B", "A");        // The node B is be added, 
                                     // and the edge B -> A
    
    System.out.println(graph1.hasEdge("A", "B")); // Prints false

    System.out.println(graph1.hasEdge("B", "A")); // Prints true

    
    // Make a fully connected graph with 10 nodes...
    Graph<Integer> graph2 = new HashGraph<>();
    for (int i = 0; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        graph2.addEdge(i, j);
      }
    }
    
    // This should print 10
    System.out.println(graph2.numNodes()); 
    
    // This should print 90 (no self links are allowed)
    System.out.println(graph2.numEdges()); 

Part 1 - Implementation Advice

Data Structure Selection

Our textbook describes two basic data structures for implementing a Graph ADT: adjacency matrix and adjacency list. An adjacency matrix is not a good choice for this application because it doesn't provide a good mechanism for dynamically adding and removing nodes.

An adjacency list is a more promising approach, but there are some efficiency issues with a simple implementation using an array of singly linked lists. For one, determining whether two nodes are neighbors may require a \(\Theta(|V|)\) sequential search through a node's neighbor list. Checking and modifying edges can be implemented more efficiently if the adjacency "List" is actually stored as a hash-table-backed Set.

Note that you are not required to provide your own hashing implementation for this project. You are welcome to use the HashMap and HashSet classes from the Java Collections Framework.

Node Removal

Consider the problem of removing node A from the graph pictured below:

Efficiently removing the edge (A, E) is straightforward. However, a correct implementation will also need to remove the edges (B, A), (C, A) and (D, A). This could by done be checking each node in the graph to find those that are connected to A. Unfortunately, this approach would require \(\Omega(|V|)\) operations. An efficient implementation will require a mechanism for quickly finding both outgoing and incoming edges for any node.

Part 2 - Graph Algorithms

Complete the unfinished method in GraphUtils.java.

Part 2 - Implementation Advice

The OpenDSA textbook contains implementations of both BFS traversal and topological sort. You are welcome to use these implementations as a starting point for developing your solutions to Part 2.

A BFS traversal is useful for finding shortest paths in an unweighted graph: BFS will visit all nodes within \(n\) steps of the starting node before visiting any nodes that are \(n + 1\) steps away. This means that as soon as the traversal visits a node, we are guaranteed that we have discovered the shortest path to that node. The challenge is in reconstructing the path. This can be accomplished by maintaining a record of the predecessor of each node in the traversal. Once the goal node is reached, we can then reconstruct the entire path by stepping backward through the predecessors until we reach the starting node.

JUnit Tests (New 4/17)

• HashGraphTest.java - Part 1 Correctness
• HashGraphSpeedTest.java - Part 1 Efficiency
• GraphUtilsTest.java - Part 2 Tests

Sample Application (New 4/17)

Here is a simple GUI application that reads in a graph specification from a file and displays the shortest path between any two nodes.

• PathFinder.java

The file states.txt contains a graph where each node represents a U.S. state, and two nodes are connected if the states share a common border.

Submission and Grading (Updated 4/17)

For Part 1, submit only HashGraph.java. For Part 2 submit only GraphUtils.java.

The project will be graded as follows:

Note that it will not be possible to receive any credit for the efficiency tests for Part 1 if your submission fails any of the Part 1 functionality tests.