Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 GromovHausdorffDistance

Source Notebook

Computes Gromov–Hausdorff distance of finite metric spaces

Contributed by: Pavel Hajek

ResourceFunction["GromovHausdorffDistance"][d1,d2]

computes Gromov–Hausdorff distance of distance matrices d1 and d2.

ResourceFunction["GromovHausdorffDistance"][g1,g2]

computes Gromov–Hausdorff distance of graphs g1 and g2.

Details and Options

The Gromov–Hausdorff distance between metric spaces (X1, d1) and (X2, d2) was defined in [1] as the infimum of the Hausdorff distances between their isometric embeddings into a common metric space.
For X1={1,…, n1} and X2={1,…, n2}, the Gromov–Hausdorff distance can be computed as , where Gn1, n2 is a bipartite graph between X1 and X2 such that every vertex has nonzero degree. Such graph represents a relation between X1 and X2, and its distortion is defined by taken over all pairs of edges {i1, j1}, {i2, j2} of Gn1, n2. Since the distortion is monotone, one can restrict to spanning forests with number of edges k ranging from max(n1, n2) to n1+ n2-1.
The computational complexity grows combinatorially with n1 + n2 (here feasible only up to 8) and cannot be approximated within any reasonable bound in polynomial time (see [2]). Nevertheless, faster approximate heuristic algorithms exist and can provide practical estimates for larger instances.
The Gromov–Hausdorff distance of graphs g1 and g2is taken with respect to their GraphDistanceMatrix.
The following options are supported:

Examples

Basic Examples (2) 

Gromov–Hausdorff distance of triangles in ℝ and ℝ2:

In[1]:=
ResourceFunction["GromovHausdorffDistance"][ DistanceMatrix[{1, Exp[1], Pi}], DistanceMatrix[{{0, 0}, {Pi, Exp[1]}, {1, 1}}]]
Out[1]=

Gromov–Hausdorff distance of the star graph S3 and the cycle graph C3:

In[2]:=
ResourceFunction["GromovHausdorffDistance"][StarGraph[3], CycleGraph[3]]
Out[2]=

Scope (1) 

By[3], the path graph Pn and the circle graph Cn satisfy for all m,n and for m>n. We can check this for small m and n:

In[3]:=
ParallelMap[ ResourceFunction["GromovHausdorffDistance"][PathGraph@Range[2], PathGraph@Range[#]] &, Range[2, 6]]
Out[3]=
In[4]:=
ParallelMap[ ResourceFunction["GromovHausdorffDistance"][CycleGraph[#], PathGraph@Range[2]] &, Range[2, 6]]
Out[4]=

Note that dGH(G1, G2) = 0 if and only if G1 and G2 are isomorphic.

Options (5) 

Relations (2) 

Taking into account only the "Minimal" possible relations with max(n1, n2) elements is often sufficient:

In[5]:=
ParallelMap[ ResourceFunction["GromovHausdorffDistance"][CycleGraph[3], CycleGraph[#], "Relations" -> "Minimal"] &, Range[2, 6]]
Out[5]=

Considered relations can be specified by their size:

In[6]:=
ResourceFunction["GromovHausdorffDistance"][CompleteGraph[20], CycleGraph[40], "Relations" -> 50, "MaxSteps" -> 50]
Out[6]=

Cutoff (1) 

Setting a "Cutoff" provides an upper bound on the Gromov–Hausdorff distance:

In[7]:=
ResourceFunction["GromovHausdorffDistance"][StarGraph[10], CycleGraph[20], "Cutoff" -> 5]
Out[7]=

MaxSteps (1) 

Computation stops after the maximal number of relations has been processed:

In[8]:=
ResourceFunction["GromovHausdorffDistance"][PathGraph@Range[20], PathGraph@Range[40], "MaxSteps" -> 1000]
Out[8]=

ComputeDistortions (1) 

Count how many relations yield each pair {dist,k}:

In[9]:=
ResourceFunction["GromovHausdorffDistance"][StarGraph[4], CycleGraph[3], "ComputeDistortions" -> True]
Out[9]=

Publisher

Pavel Hajek

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

  • 1.0.0 – 12 December 2025

Source Metadata

Related Resources

Author Notes

For complexity reasons, bipartite graphs are generated one‑by‑one, which is currently achieved by sequentially generating pairs of surjections for the start and end vertices. However, this produces all bipartite graphs. Further optimization will be achieved by implementing an algorithm that sequentially generates bipartite forests only.

License Information