Create a Python class which supports a weighted, directed graph. The nodes are named by strings, and the arc weights are integers. Place your class in a separate file which a client program can import. Use a class name of Graph and implement the following interface for a graph g:
Remove the contents of the graph.
Return the number of nodes.
Return the number of arcs.
Insert a link, from a source node src to a destination node dst with weight weight. If the arc already exists, change its weight to weight. Src and dst are strings, and weight is an integer.
Remove the link from source node src to destination node dst. If no such link exists, do nothing. (In particular, don't crash.)
Return the weight of the arc from a source node src to a destination node dst. If no such arc exists, return the string "infinity". The method may be called with node names that have never been mentioned before. That's fine; the arc doesn't exist, so just return "infinity". Note: This function will return an integer if the arc exists, and string if it doesn't. Just try that in Java.
Return a list (array) of all direct successors of node src. List each successor exactly once, in any order which is convenient to your implementation. (The successors of node n are those which n has been liked from. That is, if g.link(n, m) has been called (and not delinked), then m is a successor of n.)
Returns a list (array) of all direct predecessors of node src. List each predecessor exactly once, in any order which is convenient to your implementation. (The predecessors of node n are those which have been liked to n. That is, if g.link(m, n) has been called (and not delinked), then m is a predecessor of n.)
The assignment is to create the class only. To make it easier to test, here is some Python code which makes use of the class. When run using your class, these programs should produce the output given. The program grtest.py is a test program that creates a graph and runs some operations on it. A correct implementation should produce exactly the same output.
The search.py creates a graph then finds the cheapest path between pairs of nodes as requested in the input.
The programs have import statements which assume the Graph class is in a file named graph.py. You will need to change the import statement if you use a different file name, but you should call your class Graph whatever file it's in.
| Program | I/O Files | |
|---|---|---|
| grtest.py | grtest.out | |
| search.py | grin3.txt | grin3.out |
Your class needs to keep track of the existing nodes, arcs and costs. One simple way is to represent each arc as a tuple of its source and destination node. Then keep a dictionary mapping arcs to cost. Then the entire link method can look something like this:
There are probably more efficient ways to do it, but make it work first. After it works with grtest.py, try with search.py.
I would recommend that you start by creating a python file that can be run with the grtest.py program posted above. At first, just worry about completing without any syntax or run-time errors. You can write short stubs for each method; ones that need to return something can return zero or empty string or list, or whatever makes sense. Ones that don't return can have empty bodies. When that runs without error, you can start filling in serious code. This will let you make incremental changes and proceed gradually to a fully working program. You might occasionally save a copy of a partially-working version in case you wish to scrap your latest increment, and back up to the last version that didn't blow up. In the immortal words of Fred Brooks, “Plan to throw the first one away. You will anyway.”
When your program works, submit over the web here.
 Python Assignment 4 |
![[^]](http://sandbox.mc.edu/icons/local//up3.gif){kind=icon}