  This paper studies algorithms for computing a Gomory-Hu tree, which is a
classical data structure that compactly stores all minimum $s$-$t$ cuts of an
undirected weighted graph. We consider two classes of algorithms: the original
method by Gomory and Hu and the method based on "OrderedCuts" that we recently
proposed. We describe practical implementations of these methods, and compare
them experimentally with the algorithms from the previous experimental studies
by Goldberg and Tsioutsiouliklis (2001) and by Akibo et al. (2016) (designed
for unweighted simple graphs). Results indicate that the method based on
OrderedCuts is the most robust, and often outperforms other implementations by
a large factor.
