$ 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
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)]
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.