$ mkdir ~/cs170/labs/lab31 $ cd ~/cs170/labs/lab31
Your new assignment involves one of my favorite board games: Settlers of Catan. Settlers of Catan is a somewhat confusing game, and sometimes a little intimidating to others. You don't need to know the full rule set before you start on your assignment. However, I think a brief description of the game would be prudent to your understanding.
On Wednesday we started talking about Graphs, specifically focused on adjacency matricies. I mentioned that this was not the only way to create a graph. Another mechanism for representing graphs is a linked structure like our linked lists and our trees. Today, I want to go over this structure a little more carefully, as I think it would be advantageous for you to use linked representation in your next assignment.
An adjacency matrix can very easily represent the structure of a graph. Commonly, that is the most important part of the graph. There are occasions where what each vertex represents is important. It is somewhat difficult to represent data in the node with our adjacency matrix: all of the vertex labels must the integers. The common way around this is to create objects that represent verticies, very similar to how we represented a linked list using nodes.
Creating such a structure is very similar to building the adjacency matrix. Working with them is very different. To help get everyone some easier experience working with the linked structures, today you will write a program to read a graph specification file into a linked structure.
Download the linked_graph.py file.
This file contains a class called Graph, which contains a
template class that represents a graph using a linked structure. This
is the structure we talked about on Wednesday and today in lab. Your
job is to read in a file (the same files as the previous lab) into a
linked structure.
You will notice that there is already a dft method
(depth-first traversal) written for this instance of graphs. You
should be able to test your read code by using this method that has
already been written for you.
You can get my test case files here.
>>> tree = Graph("test_files/complete.txt")
>>> print(tree.compute_dft("0"))
0 1 2 3 4
>>> print(tree.compute_dft("4"))
4 0 1 2 3
>>> weighted = Graph("test_files/directed.txt")
>>> print(weighted.compute_dft("0"))
0 1 4 3
>>> print(weighted.compute_dft("4"))
4 3 1
The process by which you read in the rest file will largely be the same. The only major change is that everything is not in the same datastructure; There is a level of indirection that exists between the verticies. Each integer is an index into your vertex list, which you need to access in order to add to the neighbors. The first index is the "source", while the second is the "destination" of the edge to be added.
Trees are very special forms of a graph: They do not have any cycles in them. Graphs without cycles are easier to traverse, since you don't have to worry about determining if you have visited a node before. Without cycles, there is exactly one way to get to a node from some other arbitrary node.
Several graph algorithms require determining if there is a cycle in the graph. There are different techniques for determining this, but one of the most efficient mechanisms requires a little bit of .
Add a method called has_cycle(self), which will return
True if the current graph has a cycle. To determine whether a
graph has a cycle in it, you will need to create a set of all
of the verticies that are connected by edges. If you determine that
there are multiple ways of getting to a vertex, you know there is a cycle.
You need to iterate over all of the edges in the graph. When you examine an edge E = (v1, v2), you check to see if both v1 and v2 are in the set. If they both are in the set, your graph has a cycle. If either are not, you add the verticies that are not currently in the set into the set, and move on to the next edge. If you can perform this action on ALL edges without a problem, your graph does not have a cycle.
You can get my test case files here.
>>> tree = Graph("complete.txt")
>>> print(tree.has_cycle())
True
>>> lst = Graph("directed.txt")
>>> print(lst.has_cycle())
True
>>> lst = Graph("simple.txt")
>>> print(lst.has_cycle())
False
>>> lst = Graph("simple_cycle.txt")
>>> print(lst.has_cycle())
True
You can use a list to represent a set. You can use the
in operator to determine if something exists in the
set. You can use the append method to add things
to the set.
You will need a nested for loop to iterate over the unique edges of the
graph. Since you have a list of neighbors in each vertex, you
need to just iterate over these edges. Pull the data for each
vertex as part of the edge. See if both are in the set
using the in operator.
Note: We are dealing with an undirected graph. This means that the above check will always fail given our current input.
Like I mentioned above, this is not the only mechanism for determining if a graph has a cycle. As a matter of fact, a depth-first traversal can also tell you if a graph has a cycle.
Write a method called has_cycle_dfs(self,
curr_node=0), which will perform a depth-first traversal to
determine if the graph has a cycle. You may need to add additional
parameters, to simplify your computations.
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 inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
31. Make sure you include a header
listing the authors of the file.