Exploring Graphs

Our final family of data structures, graphs, is a rich family with many applications. You’ll study graph algorithms extensively your (equivalent of) discrete mathematics and algorithms classes. For now, we’ll gain practice working with graphs in a computer program by implementing a basic graph data structures and fundamental operations over graphs.

In particular, in this lab, we’ll practice translating graph algorithms to code, a common practice in practical programming scenarios. It is important to be able to derive these algorithms on your own, a topic of subsequent courses. However, very often, you will be tasked with a problem, and if you can frame it as a graph problem, you can then find the relevant algorithm, e.g., online, and translate it to your particular context.

Setup

Add the following files, taking care to ensure that you add them to folders consistent with their declared packages, edu.ttap.graphs.

• Graph.java
• GraphEntry.java
• Edge.java

Part 1: The Graph Data Structure

First, let’s implement the basic data structure as we discussed in class. Specifically, we’ll implement a weighted, undirected graph although not all of our algorithms will require the weight.

Because real-world graphs typically contain many (at least hundreds of nodes, if not more), it behooves us to assume that the data for our graphs will come from files. Let’s assume that our graphs are specified in text files, where each line of the graph records an edge of the graph:

<node A> <node B> <weight>

For example, the line A B 10 says that there is an edge in the graph from node A to B with weight 10.

A good design pattern to follow is to factor out the file-reading code from the data structure itself. To do so, we’ll use the GraphEntry class to capture the data found on a line. We can then construct a graph from a list of these entries where, e.g., our main method would then read from a data file, create said list of entries, and feed that to the Graph constructor.

With this in mind, implementing the constructor for Graph using an adjacency list representation of graphs. Recall that an adjacency list is a map from a node (represented as a string in our program) to a list of nodes. An entry in this list denotes an edge from the first node to the second.

• public Graph(List<GraphEntry> data)

Since our graph is undirected, we can traverse an edge from either of its vertices to the other. Because of this, it’ll likely be useful to record that fact that for edge $(A,B)$ that $A$ is adjacent to $B$ and $B$ is adjacent to $A$ in your adjacency list.

Since our graph is weighted, we will also need to record more information than just the edges! Consider what additional fields you need for your Graph class to easily implement the following methods:

• public boolean contains(Node node)
• public Optional<Integer> weight(Node src, Node dst)

Implement these methods so that they take constant time ($O(1)$) by adding additional fields to your class that you, then, initialize in the constructor.

Interlude: An Example Graph and Basic Testing

At the end of this lab, we’ll provide a number of sample files for you to try out your graph implementations. Below, here is an example graph that we’ll use in our explanation of the algorithms you implement.

Additionally, we’ve provided this graph as a data file that you should place in a top-level /data directory in your project:

• graph-example.data

As well as a simple test file utilizing that data file Note that this test file exists in the edu.ttap.graphs package, so it should appear in a relevant subdirectory of /src/test/java/... of your project.

• GraphTest.java

Part 2: Depth-first Search

Previously, we learned about the various versions of depth-first search we could perform over trees. Since trees are a special case of graphs (a tree is a graph with no cycles), we can also perform depth-first search over graphs!

Recall that in a depth-first traversal, we intermix “processing” the current node, e.g., printing its value, and recursively exploring its children. For example, in our example graph, if we begin a pre-order depth-first traversal starting at $A$, we might process the nodes in the following order:

$A,D,G,F,I,C,E,H,B$

Observe in this traversal how we eventually reach $I$ and then backtrack to $F$ to explore a different edge that brings us to $C$. Similarly, we backtrack after reaching $H$ to $E$ in order to end at $B$.

The order in which we explore the children matters, so another pre-order depth-first traversal might yield:

$A,B,E,H,F,I,G,C,D$

Where we, instead, go down the $B$-side of the graph rather than the $D$-side first.

Implementation

Since graphs may have cycles, using recursion makes less sense because naively navigating into a cycle will cause us to go into an infinite loop. Subsequently, we tend to implement algorithms like depth-first search over graphs using iterative rather than recursive means. To perform depth-first traversal over a graph, we employ a stack to emulate the order in which our would-be recursive calls would have processed the nodes of the graph:

• Create an empty stack and push the starting node onto the stack.
• While the stack is not empty:
  • Pop the top node off the stack.
  • If the node is not already visited:
    • Process the node and mark it as visited.
    • Push all the nodes incident to this one (i.e., connected by an edge) onto the stack.

Implement depth-first traversal in the Graph class by adding the following method:

• List<String> collectDepthFirst(Node start): returns a list of the nodes obtained via a depth-first traversal of the graph starting with the given node.

Note that the marking scheme is necessary to ensure we do not go into an infinite loop. To implement this marking scheme, we recommend maintaining a local data structure during the traversal process that allows you to lookup whether a node has been marked.

Part 3: Breadth-first Search

Once we make iterative the depth-first search process, you might have noticed another way to extend the search! Recall that a stack is a first-in-last-out (FILO) data structure. A queue on the other hand is a first-in-first-out (FIFO) data structure. What happens when we replace the stack with a queue in our search?

We obtain a new kind of search, a breadth-first search. By “breadth,” we mean that we’ll explore the graph by levels rather than diving as deeply as possible and back-tracking. We’ll discover all the nodes that are 1 edge away from the start node, then 2 edges, 3 edges, and so forth.

On our example graph, a breadth-first traversal explores nodes in the following order:

$A,B,D,C,E,G,F,H,I$

Observe how:

• $B$ and $D$ are 1 edge away from $A$.
• $C$, $E$, $G$ are 2 edges away from $A$.
• $F$ and $H$ are 3 edges away from $A$.
• $I$ is 4 edges away from $A$.

Like our depth-first search, the order of visiting children is arbitrary, so we may intermix nodes within each of these buckets, but we’ll always explore all the distance 1 nodes before the distance 2 nodes, distance 2 before distance 3, and so forth.

Implementation

The implementation of breadth-first search is identical to depth-first search save for the replacement of the stack with the queue.

• Create an empty queue and push the starting node onto the queue.
• While the queue is not empty:
  • Dequeue the top node off the stack.
  • If the node is not already visited:
    • Process the node and mark it as visited.
    • Enqueue all the nodes incident to this one (i.e., connected by an edge) onto the queue.

Implement breadth-first traversal in the Graph class by adding the following method:

• List<String> collectBreadthFirst(Node start): returns a list of the nodes obtained via a depth-first traversal of the graph starting with the given node.

Part 4: Minimum Spanning Trees

Finally, let’s implement a basic graph algorithm to get a flavor of what working with graphs is like. Consider identifying a minimal subset of the edges of a graph that connects all the nodes together, i.e., spans the vertices. If this subset is minimal in terms of edges, we can observe from graph theory such a subset must contain $v-1$ edges where $v$ is the number of vertices. Such a subset of the graph is a called a tree, thus we call it a spanning tree of the graph. For example the following is a spanning tree of the graph (the dotted edges are not part of the spanning tree) since it is a tree where every node is reachable

There are potentially many ways to create a spanning tree for a graph. In the case where the graph has weighted edges, we would like to further minimize the total weight of such a tree, i.e., the sum of the weights of its edges. Below is the minimum spanning tree for the example graph.

Implementation

Unlike depth- and breadth-first searches, deriving the minimum spanning tree for an undirected, weighted graph requires some care. One of the fundamental algorithms for deriving a minimum spanning tree is Prim’s algorithm. To find the minimum spanning tree of a graph beginning at some starting vertex:

• Create three collection:
  1. The vertices visited so far, initially empty.
  2. The edges visited so far, initial empty.
  3. A mapping from each vertex $v$ in the graph to the minimum weight edge from the vertices visited so far to $v$. Initially, there are no such mappings in the graph.
• Beginning with the start vertex:
  • Add the start vertex to the visited collection.
  • Update the vertex-edge mapping with the start vertex:
    • For each vertex incident to the start vertex, add a binding from that vertex to the edge connecting it and the start vertex to the map.
• While there is a vertex that does not appear in the visited collection:
  • Choose an unvisited vertex $v$ in the mapping whose corresponding edge has minimum weight among all the unvisited vertices. Add that edge to the visited edge collection.
  • Add $v$ to the visited collection.
  • Update the vertex-edge mapping with $v$:
    • For each vertex $u$ incident to $v$, add/update the binding with the edge $(u,v)$ if it does not exist yet or is smaller than the current edge for $u$.

This algorithm is decidedly more complicated than our traversal algorithms! I recommend that you first trace through the algorithm on the example graph and observe how we eventually derive the minimum spanning tree given above.

Implement this algorithm in the following method of the Graph class:

• public List<Edge> deriveMST(String start): returns a MST of the given graph starting at the given node as a list of edges.

Additionally, put some care into the data structures you choose for the three collections that the algorithm maintains. What data structures efficiently implement the operations required of that structure by the algorithm?

Part 5: Applying Graph Algorithms

Finally, with some basic graph algorithms defined, let’s employ them to solve a variety of tasks! The beauty of graphs is that they are applicable to many situations. Below, you’ll find a link to a data set you can use for this exploration:

• example-dataset.data

Look at the data set and infer from the content what it is about. And for each of the algorithms we’ve implemented—DFS, BFS, and Prim’s algorithm—describe in a comment in Graph.java:

1. What kind of question could each algorithm answer of this data set?
2. The answer to the question you posed, obtained by applying the algorithm to the data set.