Hand in the recurrence problems on paper as usual. In addition, submit both the recurrence PDF and your source code for #1 via Moodle.
Sometimes you want to create an image of a graph, or store the graph in a file for future use. This happens often if you're writing about graphs and graph algorithms, of course, but nicely drawn graphs can also be helpful in writing outside of computer science. I've even used graph-drawing software in one of my company's word games (Psychobabble).
The DOT language was developed to support the storage, processing, and visual layout of graphs. DOT graphs can be manipulated by a wide variety of tools, the most well-known of which are assembled into the Graphviz package. For this problem, you will implement some graph algorithms in Python, using DOT and the PyGraphviz library to give visual life to your implementations.
Your job will be to implement one single-source shortest path algorithm (Bellman-Ford or Dijkstra) and one minimum spanning tree algorithm (Kruskal or Prim) in Python. In each case, your program will take a graph G in DOT-file form as input, run the specified algorithm on G, and generate a new DOT file as output, representing the same graph but with suitably colored edges and nodes, depending on the algorithm.
To clarify what I'm asking for, I have written this graphs.py program that does the job I'm asking of you for Breadth-First Search. If you run "python graphs.py -h", you will get a detailed usage statement that describes what I expect from your programs. Please use graphs.py as the shell of your own program. All you have to do is implement two of the functions I have already provided for you (prim, kruskal, dijkstra, and bellmanford).
I have also created three sample graphs in .dot form: an undirected graph for testing BFS, the directed graph from page 652 of CLRS, and the same directed graph, but without pre-specified node positions. Read the comments in graphs.py for more details.
You will need to have pygraphviz installed on your development computer. We have it installed for python 2.7 in CMC 304 and 306, as well as on mirage.mathcs.carleton.edu. If you have python installed on your own computer, executing the command-line command "pip install pygraphviz" should install what you need. If you don't have pip, try "easy_install pip" first.
Here are some notes on the four algorithms.