$ mkdir ~/cs170/labs/lab32 $ cd ~/cs170/labs/lab32
For the final time this semester, it is time for you to hand in your pseudocodes! As usual, I will get these scanned in and will have comments back to you as soon as humanly possible.
One type of graph we have yet to discuss so far is a weighted graph. In a weighted graph, edges have some (usually non-zero) weight associated with them. I will discuss in class how we can represent these types of graphs using both graph representations we have used. Today, we will only be using the adjacency matrix representation, however.
There are a lot of algorithms that deal exclusively with graphs. Some of the most well known ones are used in the computation of minimum spanning trees . A minimum spanning tree of a graph is a sub-graph (a graph that contains a subset of the edges of the original graph), which is connected (every vertex is reachable by some path) and the sum of all of the weights of the edges is as small as possible. The two main algorithms for computing these are Prim's algorithm and Kruskal's algorithm, which we will discuss in class today.
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.
>>> 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)]
You wrote a method earlier that could tell if a graph has a cycle. However, using that here would be inefficient. Instead, use the idea of the 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.
Kruskal's algorithm is based on set theory more than it is
based in graph theory. It is some what similar to the code you wrote
for has_cycle, except that instead of determining if a
cycle exists you simply add edges until all of the verticies exist in
a single set.
Create a method called kruskal(self) in
the Graph class.
It should return a list of edges that are in the minimum
spanning tree.
The algorithm utilizes a priority queue of edges. At the start of the algorithm, you will add all of the edges of the graph into the priority queue, prioritized by their weights. Each vertex begins as part of a set containing only that vertex. You will then start dequeue-ing the nodes from the queue. If the end points of the edge \(E = (src, dest)\) do not belong to the same set, you add the edge to the spanning tree and merge the two sets together. You continue doing this until all of the verticies belong to the same set.
>>> weights = Graph("test_files/weighted.txt")
>>> print(weights.kruskal())
[(0, 5), (0, 1), (0, 2), (0, 4), (1, 3)]
>>> weights.adjacency_matrix[4][5] = .1
>>> weights.adjacency_matrix[5][4] = .1
>>> print(weights.kruskal())
[(4, 5), (0, 5), (0, 1), (0, 2), (1, 3)]
At the beginning of the algorithm, you need to initialize the list of sets. For this purpose, you should create a list of lists, where each internal list only contains one element, the label of each vertex.
When you dequeue an edge, you need to check to see which set the end points of the edge belong to. For this, just iterate over the list of sets, looking for the one containing those labels. Use the index of the overal list as an identifier of the sets.
You can merge sets using the + operator. Just don't
forget to pop one of the sets.
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 inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
32. Make sure you include a header
listing the authors of the file.