Create proptest tests for TopoSort using our graph generation strategies and available assert_valid function. Test both algorithms (DFS, Kahn). Use DebugGraph as the graph being generated because it provides very useful information in case of a failed assert.
It would be nice to implement a function for removing cycles from a graph by removing back edges from DfsEvents so that there could be also proptest tests which use acyclic graphs for testing. This should increase test coverage of the algorithm since more of valid graphs will be tested.
pnevyk
commented
1 year ago
Create proptest tests for
TopoSortusing our graph generation strategies and availableassert_validfunction. Test both algorithms (DFS, Kahn). UseDebugGraphas the graph being generated because it provides very useful information in case of a failed assert.It would be nice to implement a function for removing cycles from a graph by removing back edges from
DfsEventsso that there could be also proptest tests which use acyclic graphs for testing. This should increase test coverage of the algorithm since more of valid graphs will be tested.