$ mkdir ~/cs170/labs/lab31 $ cd ~/cs170/labs/lab31
It's that time once again. hand in your class outlines for the Akinator program! I will try my best to get these back to you later today, if not by tomorrow morning.
Let's find a time that we can collectively meet for our exam. If we cannot find an agreeable time, we will be stuck with our 6:00 pm to 9:00 pm exam time.
I only received 10 Sudoku submissions over the weekend. I feel like I should go over the solution for everyone, since backtracking is a very important skill to know.
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. This past Friday, we saw how we could take some special types of data structures, and represent them using python lists. Luckily, graphs are one of the special forms of data structures that could be stored using a list, as opposed to a linked structure.
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 matrix 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: Since a tree is 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
Since this method returns a string, you need to create an empty string that the top of the method, which holds the result of the breadth-first traversal. When you 'explore' a vertex, you will simply add 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 lab31
directory. To create a tar file, execute the following commands:
cd ~/cs170/labs tar czvf lab31.tgz lab31/
To submit your activity, go to cseval.roanoke.edu. You should
see an available assignment called Lab Assignment 31.
Make sure you include a header listing the authors of the file.