$ mkdir ~/cs170/labs/lab30 $ cd ~/cs170/labs/lab30
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.
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.
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.
You can download my sample input files here.
>>> 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
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.
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.
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.
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.
>>> print(complete.breadth_first_traversal(0)) 0 1 2 3 4 >>> print(complete.breadth_first_traversal(3)) 3 0 1 2 4 >>> print(undirected.breadth_first_traversal(0)) 0 1 4 2 3 >>> print(undirected.breadth_first_traversal(1)) 1 0 2 4 3 >>> print(directed.breadth_first_traversal(0)) 0 1 3 4 >>> print(directed.breadth_first_traversal(4)) 4 3 1
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.
Performing a breadth-first traversal on an adjacency list is very similar to performing one on an adjacency matrix. Modify your code to perform the traversal on an adjacency list instead.
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.
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.