Are any of the state of the art Maximum Flow algorithms practical?
I am one of the authors of the paper linked above. 

Just want to mention that we used ``state-of-the-art'' to mean algorithms (with publicly available implementations) that perform well on max-flow instances arising in computer vision. 

I would also like to add that within that narrow (yet practical) context, often the algorithms that perform well are the ones with poor theoretical guarantees. For instance, ref [5] from our paper (Boykov-Kolmogorov algorithm) is widely used in the computer vision community, but does not have a strongly polytime runtime bound. 

Finally, in case anyone is interested, the data from our experiments is available here:
http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html

The code will also soon be available too.