Lecture 30 - Graphs

As usual, create a directory to hold today's activities:

$mkdir ~/cs170/labs/lab30$ cd ~/cs170/labs/lab30


Graphs

Graphs here are not the same as what you do in your mathematics classes. Graphs are actually more related to trees than anything else we have seen up to this point. A graph is simply a tree that could have a cycle in it. Today we will cover how to represent a graph using an adjacency matrix, as well as how to perform graph traversals.

Lab Activity 1
Graph Representation

For the past two weeks, we have been using linked structures to represent our data structures. On Monday, you used a list to represent a tree. Luckily, graphs are one of the special forms of data structures that could be stored using a list, just like heaps.

We do need a 2-dimensional structure to store our data in. This is what is known as an adjacency matrix. If matrix[r][c] has a value of 1, that means the vertex with label r has an edge between the vertex with label c. A value of 0 says that there is not an edge between those two verticies.

We need some mechanism for building these matrices. You are going to write a program that reads a text file, and creates an adjacency matrix based off that text file.

Details

Create a file called graph.py, which holds a class called Graph. You are going to create a graph class that represents a graph using an adjacency matrix.

Your constructor for your graph class should take a string file_name, which is the name of a file that can be read that represents a graph. Your constructor will read this file, and store the adjacency matrix in an attribute called adjacency_matrix. Make sure you are following the conventions described above.

The text file you read will be in a very specific format. The first line will contain an integer N, which will define the number of verticies in the graph. The following lines will contain two integers i and j, separated by a single space. Each integer will be in the range [0, N). This will specify that there is a connection between the vertex i and j.

You should also write a method called matrix_print(self), which will output the adjacency matrix in a much better format than the typical 2-d list output.

Example

  >>> complete = Graph("complete.txt")
>>> complete.matrix_print()
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
>>> undirected = Graph("undirected.txt")
>>> undirected.matrix_print()
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
>>> directed = Graph("directed.txt")
>>> directed.matrix_print()
0 1 0 1 0
0 0 0 0 1
0 0 0 0 1
0 1 0 0 0
0 0 0 1 1


Hint

• The first integer N will tell you the size of your 2-D matrix. You should write a method create_matrix(self, n), which will initialize the adjacency_matrix attribute with a 2-D list of the correct size, with 0's in every location.

• Don't forget you can use the split method of string to split the strings on spaces. Don't forget to int the two elements as well!

• The rest of this exercise is simply file parsing. You are give two indices into the adjacency matrix. You simply need to set the value to be 1.

Challenge

Adjacency matrices are not the only list representation we can have for a graph. Adjacency matrices are always square, but can take up a lot of space for a very sparse graph. Instead, we could use an Adjacency List representation of a graph. This is still a 2-dimensional python list. Instead of each row being a list of size N, it is simply the a list of the indicies of the verticies connected to it.

Modify your class written above to store both the adjacency_matrix and adjacency_list attributes. Make sure you also add a method for printing the adjacency list in a better format.

Lab Activity 2
Traversals

We performed tree traversals last week in lab. The nice thing about traversing a tree is that you don't need to keep track of anything additional in your traversals. Trees are inherently acyclic; You will never try to visit a node more than once. However, graphs can have cycles, and can have multiple paths to an arbitrary location. So, the concepts of the traversals are much the same. We just need to be a little more careful than before.

Details

Add a method to your Graph class called breadth_first_traversal(self, start_vertex). This method takes an integer, which is the index of the vertex to start the traversal from. It should return a string, the result of the breadth-first traversal of the current graph. Recall that a breadth-first traversal requires a queue, so you might want to download my queue for use during this lab activity.

Example

The following example uses the previously constructed graphs.
  >>> print(complete.breadth_first_traversal(0))
0 1 2 3 4
3 0 1 2 4
0 1 4 2 3
1 0 2 4 3
0 1 3 4
4 3 1


Hint

• You should first create a string accumulator which will hold the result of the breadth-first traversal. "Exploration" of a vertex requires simply adding its label to the string.

• When you dequeue a vertex from the queue, you need to check to see if it has been visited or not. If it has, you just move to the next thing in the queue. If it hasn't, you need to enqueue all of the unvisited neighbors of that vertex. This means you need to have some mechanism of knowing which verticies have been visited already. Luckily, you do have a string that is storing that information.

Challenge

A breadth-first traversal can be used as a solution to the shortest-path problem. We will see more sophisticated solutions to this problem later this week, but this is a sufficiently efficient method to use if you know both the source and destinations. Write a method called shortest_path(self, source, destination), which takes two integers: two verticies in the graph. This should return a list of integers, the shortest path you need to traverse to get from the source to the destination.

Hint: You might need to enqueue tuples, which represents the parent of how you got to this node, to recover the path.

Submission

When you have finished, create a tar file of your lab30 directory. To create a tar file, execute the following commands:

cd ~/cs170/labs
tar czvf lab30.tgz lab30/


To submit your activity, go to inquire.roanoke.edu. You should see an available assignment called Lab Assignment 30. Make sure you include a header listing the authors of the file.