A little graph coding
You may work alone or with a partner of your choosing.
Goals
- Have a little fun implementing simple graph algorithms
- Meet the DOT graph description language
Rubric
1 - author name(s) in comment at top of graphs.py
2 - correct BFS
2 - correct DFS
2 - correct topological sort
2 - code quality (readability, not excessively inefficient, etc.)
Starting materials
Here is a little python program I wrote, called graphs.py. It consists of a single class called Graph, plus a few testing functions and a main program that calls the testing functions.
Here are two graphs expressed in the DOT graph description language: undirected.dot and directed.dot. The file format should be self-explanatory, so you can make your own similar files if you want to try your code on more test cases (which you ought to do, for sure).
Your job
- Download copies of graphs.py, undirected.dot, and directed.dot. Put them all in a single working directory.
- Read all three files. Write down any questions and ask them in class or on Slack. Try to guess what's going to happen when you run graphs.py.
- Try running graphs.py ("python3 graphs.py" at the command-line or just executing graphs.py in VS Code ought to do the job). Does the output match your expectations?
- Implement the bfs_tree, dfs_tree, and topological_sort methods of the Graph class.
- Submit your copy of graphs.py with the three newly implemented methods. If you add tests to the main program, make sure to also submit any new dot files that your tests use.
We'll talk about the complexity issues in this graph implementation in class, but don't worry too much about that. Just get your methods working.