$ mkdir ~/cs170/labs/lab32 $ cd ~/cs170/labs/lab32
What we constructed on Monday were unweighted graphs. Each edge in an unweighted graph has the same "weight." However, In real life connections between verticies don't have the same weights. These weights could be based on the length of the edge, the complexity of path between the verticies, etc. We can do this by using integers in our adjacency matrix, as opposed to just the values 0 or 1.
With a weighted graph, we can talk about minimum spanning trees: A minimum weighted set of verticies that can fully connect a graph. This will give us a solution to the single-source shortest-path problem.
Tree's 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.
Finding a minimum spanning tree requires 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 .
Copy your Graph class into your lab32 directory:
$ cd ~/cs170/labs/lab32 $ cp ../lab31/graph.py .
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("tree.txt")
>>> print(tree.has_cycle())
False
>>> tree.adjacency_matrix[5][6] = 1
>>> tree.adjacency_matrix[6][5] = 1
>>> print(tree.has_cycle())
True
>>> lst = Graph("list.txt")
>>> print(lst.has_cycle())
False
>>> lst.adjacency_matrix[0][2] = 1
>>> lst.adjacency_matrix[2][0] = 1
>>> 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. If the adjacency matrix is non-zero at a cell (row,
col), you have a directed edge from row -> col.
You need to see if both row and col 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. You need to make sure you only iterate over the upper right triangle of the adjacency matrix. Otherwise, you will always fail the check!
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.
There are a lot of algorithms that can compute a minimum spanning tree. Even with the cornucopia of algorithms for determining a minimum spanning tree , historically only two are ever really taught: Prim and Kruskal.
Prim's algorithm is a greedy algorithm: It always tries to pick the edge with the smallest weight. However, it has to maintain the tree structure of it's output. So it only adds an edge if it doesn't cause a cycle to appear in the output tree. While this seems like it would be a fairly complicated check, it is actually pretty straight forward.
Create a method called prim(self, start_vertex) in
your Graph class. This method should take an integer
representing the label of the vertex to start generating the MST
from. It should return a list of edges that are in the minimum
spanning tree.
The algorithm utilizes a priority queue. At the start of the algorithm, you will add all of the edges of the starting vertex to the priority queue, prioritized by their weights. You will then start dequeue-ing the nodes from the queue. If the edge E = (src, dest) you just dequeue-ed does not create a cycle in the spanning tree, you add it to the spanning tree. You then enqueue all of the edges from dest into the priority queue. You continue this process until all of the verticies have been reached.
You can get my priority_queue.py and my linked_list.py code for use with this activity.
>>> weights = Graph("test_files/weighted.txt")
>>> print(weights.prim(0))
[(0, 5), (0, 1), (0, 2), (0, 4), (1, 3)]
>>> print(weights.prim(3))
[(3, 1), (1, 0), (0, 5), (0, 2), (0, 4)]
>>> weights.adjacency_matrix[4][5] = .1
>>> weights.adjacency_matrix[5][4] = .1
>>> print(weights.prim(0))
[(0, 5), (5, 4), (0, 1), (0, 2), (1, 3)]
>>> print(weights.prim(3))
[(3, 1), (1, 0), (0, 5), (5, 4), (0, 2)]
The first half of this lab was how to determine if a graph has a cycle. That process is an efficient one. However, you don't want to directly apply that process here. You want to use the idea of that algorithm here.
Create a list that initially only has the starting vertex in it. When you dequeue an edge, if the destination is not in this list, you don't have a cycle. If the destination is in the set, adding that edge would cause a cycle.
You might want to write a method called
add_edges(self, p_queue, vertex), which takes a
priority queue and an integer label for a vertex as parameters.
The sole purpose of this method is to add all of the edges that
have vertex as a source into the priority queue, with
the appropriate weights.
Prim's algorithm is very useful as a solution to the single-source shortest path problem: Given the MST, you know the shortest path from that source to every other vertex in the graph. However, this is not the only application of an MST, as generated by Prim's algorithm.
One of the more interesting things you can do with Prim's algorithm
is generate mazes. A maze can simply be thought of as a
2-dimensional orthogonal graph. This means that every node is only
connected to it's four adjacent neighbors.
Initialize a 2-d adjacency matrix to represent this orthogonal grid.
Initialize the weights randomly, using the
random.uniform function.
Then simply generate a MST starting at (0, 0).
Generate a simple 10 × 10 maze using this algorithm. Save the MST output into a text file, and draw your maze by hand on paper. Turn in your maze at the end of class.
When you have finished, create a tar file of your lab32
directory. To create a tar file, execute the following commands:
cd ~/cs170/labs tar czvf lab32.tgz lab32/
To submit your activity, go to cseval.roanoke.edu. You should
see an available assignment called Lab Assignment 32.
Make sure you include a header listing the authors of the file.