Graphs

Goals

• Learn different ways of implementing a graph.
• Find properties of a graph.

Graph representation:

For the final project you will need to implement a graph to represent maps. In this lab we will explore two different ways of representing a graph, as an adjacency matrix and as an adjacency list. The table below shows a graph and both representations.

Graph	Adjacency Matrix	Adjacency List
	A B G M A 0 0 1 1 B 0 0 0 0 G 1 0 0 0 M 1 0 0 0	A G, M B G A M A

In the adjacency matrix representation the graph with N vertices is represented by an N x N matrix where an entry (i,j) in the matrix is true if there is an edge from vertex i to vertex j

In the adjacency list representation the graph with N vertices is represented by a map of length N with one entry for each vertex. The vertex is mapped to the list of vertices it is connected to.

Programming Exercise:

The abstract class Graph.java partially implements a graph. The class GraphAdjMatrix.java extends Graph.java and finishes the implementation using the adjacency matrix representation.

For this part of the lab you should create GraphAdjList.java, a class that extends Graph.java and finishes the implementation using adjacency list representation of a graph.

• Create a new Eclipse project and add all provided .java files.
• Create a new class called GraphAdjList.java. Make sure to set the super class to be Graph.java this way Eclipse will auto-generate stubs for each method that you need to implement.
• Implement the required methods using the adjacency list representation of a graph.

Graph Properties:

Now that we can represent a graph we can ask what properties a graph has. In this lab we will explore connectivity, Eulerian Paths and Eulerian Cycles. The four graphs below exhibit different graph properties.

Disconnected Graph	Connected Graph	Graph w/Euler Path	Graph w/Euler Cycle

• A connected graph is a graph where there is a path from every node to every other node.
• A disconnected graph is a graph where there is not a path from every node to every other node.
• An Euler Path is a path that visits every edge exactly once, it may pass through a vertex as many times as it needs.
• An Euler Cycle is an Euler Path where the first and last vertices are the same.

Programming Exercise:

For the second part of the lab you will write methods that test if a graph:

• Is connected
• Has en Eulerian Path
• Has an Eulerian Cycle

GraphProperties.java has method stubs for each of these tests.

In order to test connectivity you may use a simplified version of depth first search (DFS) or breath first search (BFS) algorithms presented in class.

Testing for an Eulerian Path or Cycle is easier than actually finding one. To test you need only count the degree of each vertex. If the graph is connected and the degree of each vertex is even then the graph will have an Euler Cycle. If all but exactly two vertices have even degree then the graph will have an Eulerian Path.

We've provided a junit test to test these three methods GraphPropertiesTest.java. Currently it test using a GraphAdjMatrix you may change it to test with a GraphAdjList.

GraphProperties.java Also provides space to write the methods to find an Eulerian Path and Cycle. These methods are optional and should only be attempted if you've finished the rest of the lab.

Final Questions:

Now that you've had some experience implementing and using graphs which representation is better suited for each of the three tests done in part 2 of the lab?

In general, what type of graphs and graph properties would be better suited for a list representation and which for a matrix representation? Think about both the running time and the space required for each.