I would like to measure the similarity between a pair of weighted tree graphs. According to this post, this can be done by regarding the trees as metric spaces and then applying the Gromov-Hausdorff distance.

Given two metric spaces, $(A, d_{A})$ and $(B, d_{B})$, the Gromov-Hausdorff distance is defined:

$$d_{GH}(A,B)=\inf\limits_{f:A\rightarrow M\\ g:B\rightarrow M}d_{H}(f(A), g(B))$$

where $f:A\rightarrow M$ and $g:B\rightarrow M$ are isometric embeddings of $A$ and $B$ into some metric space $M$, respectively. My question is: if the infimum is taken over all possible such embeddings, and there is an infinity of such embeddings, then how can one compute this distance?

Moreover, in this paper the authors took the approach described above to compare between brain networks and defined $f:A\rightarrow B$ and $g:B\rightarrow A$. That is, no common metric space $M$ is involved. What allows to discard M when using the Gromov-Hausdorff metrics?

Thanks a lot for your time.