An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs