In this assignment, you'll implement Prim's algorithm, a non-trivial greedy algorithm used to construct minimum spanning trees.
- [TODO] Complete the
construct_mst
method found inmst/graph.py
. All necessary modules have already been imported. You should not rely on any other dependencies (e.g. networkx).
- [TODO] Add more assertions to the
check_mst
function intest/test_mst.py
. - [TODO] Write at least one more unit test (in the
test_mst.py
file) for yourconstruct_mst
implementation. (Two unit tests have already been provided: the first operates on a small graph of four nodes, and the second on a larger graph of 140 single cells, projected onto a lower dimensional subspace.) - [Optional] Make your package
pip
installable. (Refer to prevous assignments for more in-depth information.) - [Optional] Automate testing with
pytest
and GitHub Actions, and add a status badge to this README file. (Refer to previous assignments for more in-depth information.)
Fork this repository to your own GitHub account. Work on the codebase locally and commit changes to your forked repository.
You will need following packages:
We also strongly recommend you use the built-in heapq module.
Push your code to GitHub with passing unit tests, and submit a link to your repository through this google form link
- Minimum spanning tree construction works correctly (6)
- Correct implementation of Prim's algorithm (4)
- Produces expected output on small graph (1)
- Produces expected output on single cell data (1)
- Complete function "check_mst" (1)
- Write at least two unit tests for MST construction (2)
- Readable code with clear comments and method descriptions (1)
- Github actions/workflow (0.5)