pnevyk / gryf

Graph data structure library aspiring to be convenient, versatile, correct and performant.
MIT License
69 stars 1 forks source link

Create property-based tests for shortest paths algorithms #12

Closed pnevyk closed 1 month ago

pnevyk commented 2 years ago

Create proptest tests for ShortestPaths using our graph generation ~strategies~ strategies. Test both algorithms (Dijkstra, Bellman-Ford). ~Use DebugGraph as the graph being generated because it provides very useful information in case of a failed assert.~

What properties to test? ~One possibility is to implement a function for removing isolated vertices from a graph so that the tested graphs are connected. Then,~ For connected graphs after finishing an algorithm, it should be possible to reconstruct path and get distance from every vertex in the graph to the starting vertex. Also, the distances (not the paths, generally) should be equal as returned by Dijkstra and Bellman-Ford.

pnevyk commented 1 year ago

Update after #46:

pnevyk commented 1 year ago

In #64 I added proptests that at least check that the algorithms do not panic. But the properties mentioned in the original post in this issue should still be added.