How should I prepare comprehensive test cases for my maximum flow implementation?

I implemented push-relabel-algorithm using c++. I'm interested in testing the running time of my implementation using different comprehensive tests. (large tests of dense/sparse graph). How should I prepare the test cases?