Function Repository Resource:

ParametricManifoldToGraph

Generate the graph associated with a parametric description of a manifold

Contributed by: Samuele Mongodi

ResourceFunction["ParametricManifoldToGraph"][{f₁,f₂,…},{x₁,x₂,…},ℛ,n]

generates a graph with approximately n pseudorandom points in the region ℛ, drawn from the distribution given by the volume density of the manifold parametrized by {f₁,f₂,…} as {x₁,x₂,…} vary in ℛ, where two vertices are joined by an edge if their distance in ℛ is less than a certain threshold depending on n and ℛ.

ResourceFunction["ParametricManifoldToGraph"][{f₁,f₂,…},{x₁,a₁,b₁},{x₂,a₂,b₂},…,n]

generates a graph with approximately n pseudorandom points in the region defined by the set of inequalities a_j<=x_j<=b_j,j=1,…, drawn from the distribution given by the volume density of the manifold parametrized by {f₁,f₂,…} as {x₁,x₂,…} vary between the given bounds, where two vertices are joined by an edge if their distance in the coordinates x₁,x₂, … is less than a certain threshold depending on n and a_j,b_j,j=1,….

Details and Options

ResourceFunction["ParametricManifoldToGraph"] can take as input any parametrization from a region ℛ in the variables {x₁,x₂,…} via the functions {f₁,f₂,…}, as long as the latter are expressions whose derivatives can be symbolically computed.

If the functions {f₁,f₂,…} do not give an injective parametrization of (a piece of) an embedded manifold, the vertices of the resulting graph might not be evenly distributed with respect to the parametrized object.

The actual number of points produced by the function as graph vertices will be roughly (but not exactly) equal to n.

If called without options, ResourceFunction["ParametricManifoldToGraph"] will generate a graph in ℛ according to the volume density of the parametrized manifold described by {f₁,f₂,…}, where two vertices are connected by an edge if and only if their distance in ℛ is less than a threshold depending on the number of input variables and the measure of the region.

The following options can be given:

"Neighbors"

"Epsilon"

neighborhood construction method

"Distance"

"Parameters"

distance function to be used to implement the neighborhood construction method

"VertexCoordinatesSpace"

Automatic

space for the coordinates of the vertices

"MaxConnectedComponent"

False

behavior in case of a disconnected graph

"RemoveIsolatedVertices"

False

behavior in case of isolated vertices

Method

Automatic

method for the random vertex sampling

The "Neighbors" option can be set to

"Epsilon"

two points are connected if their distance is less than an automatically computed threshold

"KNN"

each point is connected to its k closest neighbors, with k being exponential in the dimension of the space where the distance is measured

{"Epsilon",ϵ}

two points are connected if their distance is less than ϵ

{"KNN",k}

each point is connected to its k closest neighbors

The "Distance" option can be set to "Parameters", where distances are measured in ℛ, or to "Embedding", where distances are measured in the target space of the parametrization.

The option "VertexCoordinatesSpace" sets the VertexCoordinates option in NearestNeighborGraph as follows:

Automatic

coordinates assigned depending on the "Distance" option

None

no coordinates in the resulting graph

"Source"

coordinates take values in the source of the parametrization, i.e. ℛ

"Target"

coordinates take values in the target space of the parametrization

If the option "MaxConnectedComponent" is set to True, the function will return only (one of the) largest connected component(s) of the resulting graph.

If the option "RemoveIsolatedVertices" is set to True, the function will return the graph with all the isolated vertices removed.

The options "MaxConnectedComponent" and "RemoveIsolatedVertices", if set to True, will, in general, remove points, thus worsening the approximation of the manifold obtained by the resulting graph; in both cases, the function will return a pair consisting of the resulting graph and the ratio between the number of vertices in the output and the number of generated random points.

ResourceFunction["ParametricManifoldToGraph"] takes the same Method settings as InhomogeneousPoissonPointProcess.

Examples

Basic Examples (4)

Generate a graph from the volume density of a (piece of a) paraboloid parametrized on a disc of radius 1, with roughly 1000 points, where edges connect points that are sufficiently close:

In[1]:=

$ResourceFunction[ "ParametricManifoldToGraph"][{x, y, x^2 + 2 y^2}, {x, y} \[Element] Disk[{0., 0.}, 1], 10^3, "Neighbors" -> "Epsilon"]$

Out[1]=

Generate a graph with the same parameters with vertices on the paraboloid:

In[2]:=

$ResourceFunction[ "ParametricManifoldToGraph"][{x, y, x^2 + 2 y^2}, {x, y} \[Element] Disk[{0., 0.}, 1], 10^3, "Neighbors" -> "Epsilon", "VertexCoordinatesSpace" -> "Target"]$

Out[2]=

Generate a graph with vertices in ℛ=[-π,π]×[-π/2,π/2], uniformly distributed with respect to the volume density of a torus embedded in , using the k-nearest neighbors method with k=6 and using the Euclidean distance in the rectangle ℛ:

In[3]:=

$graph1 = ResourceFunction[ "ParametricManifoldToGraph"][{Cos[y] (2 + Cos[x]), Sin[y] (2 + Cos[x]), Sin[x]}, {x, -Pi, Pi}, {y, -Pi/2, Pi/2}, 10^3, "Neighbors" -> {"KNN", 6}]$

Out[3]=

Compute the minimal, average and maximal length of an edge:

In[4]:=

Out[4]=

Construct the same graph with vertices in the same region, but taking the distances in , between the images of the points:

In[5]:=

$graph2 = ResourceFunction[ "ParametricManifoldToGraph"][{Cos[y] (2 + Cos[x]), Sin[y] (2 + Cos[x]), Sin[x]}, {x, -Pi, Pi}, {y, -Pi/2, Pi/2}, 10^3, "Neighbors" -> {"KNN", 6}, "Distance" -> "Embedding", "VertexCoordinatesSpace" -> "Source"]$

Out[5]=

The minimal, average and maximal length of an edge in the region as opposed to minimal, average and maximal length of an edge in the target space (where the nearest neighbors algorithm was applied):

In[6]:=

Through[{Min, Mean, Max}[
Norm[AnnotationValue[{graph2, #[[1]]}, VertexCoordinates] - AnnotationValue[{graph2, #[[2]]}, VertexCoordinates]] & /@ EdgeList[graph2]]]

Out[6]=

In[7]:=

Out[7]=

The same graph with vertices in :

In[8]:=

$graph3 = ResourceFunction[ "ParametricManifoldToGraph"][{Cos[y] (2 + Cos[x]), Sin[y] (2 + Cos[x]), Sin[x]}, {x, -Pi, Pi}, {y, -Pi/2, Pi/2}, 10^3, "Neighbors" -> {"KNN", 6}, "Distance" -> "Embedding"]$

Out[8]=

Construct a graph associated with a piece of the pseudosphere, parametrized on [-2,2]×[0,2π], by connecting points with the ϵ-neighbors algorithm with respect to the embedding distance in , with no vertex coordinates:

In[9]:=

$pseudosphere = ResourceFunction[ "ParametricManifoldToGraph"][{Sech[u] Cos[v], Sech[u] Sin[v], u - Tanh[u]}, {u, -2, 2}, {v, 0, 2 Pi}, 10^4, "Neighbors" -> {"Epsilon", 0.06}, "Distance" -> "Embedding", "VertexCoordinatesSpace" -> None]$

Out[9]=

Using GraphPlot or GraphPlot3D with different values for GraphLayout will produce different visualizations of the result:

In[10]:=

Out[10]=

In[11]:=

$pseudosphere3 = ResourceFunction[ "ParametricManifoldToGraph"][{Sech[u] Cos[v], Sech[u] Sin[v], u - Tanh[u]}, {u, -2, 2}, {v, 0, 2 Pi}, 10^4, "Neighbors" -> {"Epsilon", 0.045}, "Distance" -> "Embedding", "VertexCoordinatesSpace" -> None, "MaxConnectedComponent" -> True]$

Out[11]=

In[12]:=

Out[12]=

Scope (5)

The graph construction is not limited to surfaces in three-dimensional space:

In[13]:=

$flatTorus = ResourceFunction[ "ParametricManifoldToGraph"][{Cos[u] + 2, Sin[u], Cos[v] + 2, Sin[v]}, {u, -Pi, Pi}, {v, -Pi, Pi}, 5 10^3, "Neighbors" -> {"Epsilon", 0.2}, "Distance" -> "Embedding"]$

Out[13]=

In[14]:=

Out[14]=

However, plotting the result might lead to unwanted behaviours, as the vertices are given as points of a four-dimensional space:

In[15]:=

Out[15]=

In this case the embedding is obtained simply by discarding the fourth coordinate of each vertex:

In[16]:=

Out[16]=

Using the option None for the "VertexCoordinatesSpace" option will produce a result where no VertexCoordinates specification is given, so GraphPlot3D will automatically find an embedding:

In[17]:=

$flatTorus2 = ResourceFunction[ "ParametricManifoldToGraph"][{Cos[u] + 2, Sin[u], Cos[v] + 2, Sin[v]}, {u, -Pi, Pi}, {v, -Pi, Pi}, 5 10^3, "Neighbors" -> {"Epsilon", 0.2}, "Distance" -> "Embedding", "VertexCoordinatesSpace" -> None]$

Out[17]=

In[18]:=

Out[18]=

One could also use an explicit setting for GraphLayout:

In[19]:=

Out[19]=

Options (11)

Distance (4)

The construction of the edges is based on the distances between the vertices. The option "Distance" specifies if it has to be computed in the parameter space, i.e. the region ℛ, or in the embedding space . When the Jacobian matrix of the parametrization {f₁,f₂,…} presents huge variations in the eigenvalues or when "distant" points in ℛ end up being "close" in , the results of the two options can be quite different. The "Embedding" setting gives results which follow more closely the geometry of the manifold.

Build a graph given by a parametrization of a slice of a sphere over a disk:

In[20]:=

$slice1 = ResourceFunction[ "ParametricManifoldToGraph"][{Cos[x] Sin[(1 + y) Pi/2], Sin[x] Sin[(1 + y) Pi/2], Cos[(1 + y) Pi/2]}, {x, y}, Disk[{0., 0.}, 0.9], 10^3, "Neighbors" -> {"Epsilon", 0.12}]$

Out[20]=

Build the same graph, but with the distance computed in the embedding space (keeping the VertexCoordinates values in the disk to obtain a comparable graphic representation):

In[21]:=

$slice2 = ResourceFunction[ "ParametricManifoldToGraph"][{Cos[x] Sin[(1 + y) Pi/2], Sin[x] Sin[(1 + y) Pi/2], Cos[(1 + y) Pi/2]}, {x, y}, Disk[{0., 0.}, 0.9], 10^3, "Neighbors" -> {"Epsilon", 0.12}, "Distance" -> "Embedding", "VertexCoordinatesSpace" -> "Source"]$

Out[21]=

Compare the length of the edges of the planar plot of the result with the distribution of the ratio of the smallest eigenvalue to the largest eigenvalue of the matrix (where the Jacobian matrix of the parametrization), where it can be seen how the points with lower ratio correspond to points in which longer edges are located:

In[22]:=

$eigv = With[{jac = {D[{Cos[x] Sin[(1 + y) Pi/2], Sin[x] Sin[(1 + y) Pi/2], Cos[(1 + y) Pi/2]}, x], D[{Cos[x] Sin[(1 + y) Pi/2], Sin[x] Sin[(1 + y) Pi/2], Cos[(1 + y) Pi/2]}, y]} . {D[{Cos[x] Sin[(1 + y) Pi/2], Sin[x] Sin[(1 + y) Pi/2], Cos[(1 + y) Pi/2]}, x], D[{Cos[x] Sin[(1 + y) Pi/2], Sin[x] Sin[(1 + y) Pi/2], Cos[(1 + y) Pi/2]}, y]}\[Transpose]}, {AnnotationValue[{slice2, #}, VertexCoordinates], Eigenvalues [ jac /. Thread[{x, y} -> AnnotationValue[{slice2, #}, VertexCoordinates]]]} & /@ VertexList[slice2]];$

In[23]:=

ListPlot[Style[#[[1]], ColorData["DarkRainbow"][1 - Min[#[[2]]]/Max[#[[2]]]], PointSize[Medium]] & /@ eigv, AspectRatio -> 1, PlotLegends -> BarLegend[{ColorData[{"DarkRainbow", "Reverse"}], {0, 1}}]]

Out[23]=

By letting the GraphPlot3D function decide how to represent the two graphs, one can see what difference the choice of the distance function makes on the graph structure (with the original manifold depicted below the graphs):

In[24]:=

$GraphicsColumn[{GraphicsRow[ GraphPlot3D@ ResourceFunction[ "ParametricManifoldToGraph"][{Cos[x] Sin[(1 + y) Pi/2], Sin[x] Sin[(1 + y) Pi/2], Cos[(1 + y) Pi/2]}, {x, y}, Disk[{0., 0.}, 0.9], 10^3, "Neighbors" -> {"Epsilon", 0.1}, "Distance" -> #, "VertexCoordinatesSpace" -> None] & /@ {"Parameters", "Embedding"}, ImageSize -> 800], ParametricPlot3D[{Cos[x] Sin[(1 + y) Pi/2], Sin[x] Sin[(1 + y) Pi/2], Cos[(1 + y) Pi/2]}, {x, y} \[Element] Disk[{0., 0.}, 0.9], PlotTheme -> "Business", Boxed -> False, Axes -> False]}, ImageSize -> 900]$

Out[24]=

MaxConnectedComponent (1)

If the "MaxConnectedComponent" option is set to True, the function will return the largest connected component of the resulting graph (or one of them, if there are many) together with the ratio between the number of vertices of such connected component and the total number of generated random points:

In[25]:=

$ResourceFunction[ "ParametricManifoldToGraph"][{x^2, y^3, x y}, {x, 0, 1}, {y, 0, 1}, 10^3, "Neighbors" -> {"Epsilon", 0.03}, "MaxConnectedComponent" -> True]$

Out[25]=

As we can see, depending on the other options, the set of vertices of the result can be significantly smaller than the initial set of random points.

Neighbors (2)

Specify the method used to define the neighbors of a vertex. The default value is "Epsilon"; i.e. every point is connected to those which are closer than a given threshold:

In[26]:=

$mygraph = ResourceFunction[ "ParametricManifoldToGraph"][{x, x y, 2 y^2}, {x, 0, 1}, {y, 0, 1}, 10^2]$

Out[26]=

The threshold is computed in terms of the number of points and the measure of the parameters region; however, it can be specified in the form "Neighbors"→{"Epsilon",ϵ}:

In[27]:=

$Manipulate[ ResourceFunction[ "ParametricManifoldToGraph"][{x, x y, 2 y^2}, {x, 0, 1}, {y, 0, 1}, 10^2, "Neighbors" -> {"Epsilon", \[Epsilon]}], {\[Epsilon], 0.05, 0.5, 0.05}, SaveDefinitions -> True]$

Out[27]=

The value "KNN" means that every point is connected with its k nearest neighbors, with no bounds on the distance, where k depends on the dimension of the region where the distance is computed:

In[28]:=

$mygraph2 = ResourceFunction[ "ParametricManifoldToGraph"][{x, x y, 2 y^2}, {x, 0, 1}, {y, 0, 1}, 10^2, Neighbors -> "KNN"]$

Out[28]=

As before, k can be specified as "Neighbors"→{"KNN",k}:

In[29]:=

$mygraphs = ResourceFunction[ "ParametricManifoldToGraph"][{x, x y, 2 y^2}, {x, 0, 1}, {y, 0, 1}, 10^2, "Neighbors" -> {"KNN", #}] & /@ {2, 6, 8, 12};$

In[30]:=

Out[30]=

RemoveIsolatedVertices (1)

If the "RemoveIsolatedVertices" option is set to True, the function will delete from the resulting graph all the isolated vertices and return the result together with the ratio between its number of vertices and the total number of generated random points:

In[31]:=

$ResourceFunction[ "ParametricManifoldToGraph"][{x^2, y^3, x y}, {x, 0, 1}, {y, 0, 1}, 10^3, Neighbors -> {"Epsilon", 0.01}, "RemoveIsolatedVertices" -> True]$

Out[31]=

In[32]:=

Out[32]=

When "MaxConnectedComponent" is set to True, the option "RemoveIsolatedVertices" is ignored.

VertexCoordinatesSpace (3)

The option "VertexCoordinatesSpace" is set to Automatic by default, where the first two or three components of the coordinates are used. Depending on the "Distance" option, the vertices will have the coordinates of the points in the parameters space or the coordinates of the points in the embedding space:

In[33]:=

$GraphPlot@ ResourceFunction[ "ParametricManifoldToGraph"][{x^2, y x, y^2 z, z x, z^2 y x}, {x, y, z} \[Element] Ball[], 10^3, Neighbors -> {"Epsilon", 0.3}]$

Out[33]=

In[34]:=

$graph5dim = ResourceFunction[ "ParametricManifoldToGraph"][{x^2, y x, y^2 z, z x, z^2 y x}, {x, y, z}, Ball[], 10^3, Neighbors -> {"Epsilon", 0.09}, "Distance" -> "Embedding"];$

In[35]:=

Out[35]=

In[36]:=

Out[36]=

The value None will produce a graph without any specification for VertexCoordinates, therefore allowing one to specify an effective GraphLayout setting:

In[37]:=

$(planegraph = ResourceFunction[ "ParametricManifoldToGraph"][{x, y - x^2, x + y^2}, {x, y} \[Element] Disk[], 20]) // InputForm$

Out[37]=

In[38]:=

$(abstractgraph = ResourceFunction[ "ParametricManifoldToGraph"][{x, y - x^2, x + y^2}, {x, y} \[Element] Disk[], 20, "VertexCoordinatesSpace" -> None]) // InputForm$

Out[38]=

In[39]:=

Out[39]=

In[40]:=

Out[40]=

The values "Source" and "Target" will give VertexCoordinates respectively in the source (parameters) region ℛ and in the target (embedding) space of the parametrization , independently of the value given for the "Distance" option:

In[41]:=

$GraphPlot[ ResourceFunction[ "ParametricManifoldToGraph"][{x^2 + y^2, (x^2 - 1.1)/(y^2 + 1), x + y}, {x, y} \[Element] ImplicitRegion[1 < x^2 + y^2 < 1.5, {x, y}], 10^3, "Neighbors" -> {"Epsilon", 0.1}, "VertexCoordinatesSpace" -> "Target"], VertexSize -> Small]$

Out[41]=

In[42]:=

Out[42]=

Applications (2)

Produce increasingly finer graphs from a given manifold with the nearest neighbors method:

In[43]:=

$finergraphs = ResourceFunction[ "ParametricManifoldToGraph"][{u, v, Sqrt[1 - u^2 + v^2]}, {u, -0.9, 0.9}, {v, -1, 1}, #, "Neighbors" -> {"KNN", 7}] & /@ {10^3, 5 10^3, 10^4, 5 10^4, 10^5, 5 10^5, 10^6}; // AbsoluteTiming$

Out[43]=

Obtain some basic information about these graphs:

In[44]:=

datafg = Association[
VertexCount[#] -> <|"num. edges" -> EdgeCount[#], "connected" -> ConnectedGraphQ[#], "avg. edge length" -> Mean[Norm[#[[1]] - #[[2]]] & /@ EdgeList[#]]|> & /@ finergraphs] // Dataset

Out[44]=

Compute, for each graph, the number of vertices that lie at distance 10 from the point closer to (0,0) over the total number of vertices:

In[45]:=

volumeratios = N@With[{startvertex = Nearest[VertexList[#], {0., 0.}]}, Length@VertexComponent[#, startvertex, 10]/VertexCount[#]] & /@ finergraphs

Out[45]=

Estimate the radii of these "balls" using the average edge length:

In[46]:=

Out[46]=

Plot the volume ratios against the estimated radii and try to find a fit:

In[47]:=

$ListPlot[{radii, volumeratios}\[Transpose]]$

Out[47]=

In[48]:=

$FindFit[{radii, volumeratios}\[Transpose], a x^2 + b x^4, {a, b}, x]$

Out[48]=

We now produce graphs from the same manifold, with the same size, but with a different parameter for the KNN algorithm and we repeat the previous computations:

In[49]:=

$finergraphs2 = ResourceFunction[ "ParametricManifoldToGraph"][{u, v, Sqrt[1 - u^2 + v^2]}, {u, -0.9, 0.9}, {v, -1, 1}, #, "Neighbors" -> {"KNN", 5}] & /@ {10^3, 5 10^3, 10^4, 5 10^4, 10^5, 5 10^5, 10^6}; // AbsoluteTiming$

Out[49]=

In[50]:=

datafg2 = Association[
VertexCount[#] -> <|"num. edges" -> EdgeCount[#], "connected" -> ConnectedGraphQ[#], "avg. edge length" -> Mean[Norm[#[[1]] - #[[2]]] & /@ EdgeList[#]]|> & /@ finergraphs2] // Dataset

Out[50]=

In[51]:=

volumeratios2 = N@With[{startvertex = Nearest[VertexList[#], {0., 0.}]}, Length@VertexComponent[#, startvertex, 10]/VertexCount[#]] & /@ finergraphs2

Out[51]=

In[52]:=

Out[52]=

In[53]:=

$ListPlot[{radii2, volumeratios2}\[Transpose]]$

Out[53]=

In[54]:=

$FindFit[{radii2, volumeratios2}\[Transpose], a x^2 + b x^4, {a, b}, x]$

Out[54]=

Neat Examples (3)

By varying ϵ, with the same parametrization and number of points, one can obtain graphs with an increasing number of edges and average vertex degree:

In[55]:=

$graphs = ResourceFunction[ "ParametricManifoldToGraph"][{x, y, 1 - x^2 + y^2}, {x, y}, Disk[], 10^4, Neighbors -> {"Epsilon", #}, "VertexCoordinatesSpace" -> None] & /@ Range[0.02, 0.11, 0.01]$

Out[55]=

In[56]:=

$Association@ MapIndexed[ StringJoin[{"\[Epsilon]=", ToString[#1]}] -> <| "num. vertices" -> VertexCount[graphs[[First[#2]]]], "num. edges" -> EdgeCount[graphs[[First[#2]]]], "connected" -> ConnectedGraphQ[graphs[[First[#2]]]], "avg degree" -> N@*Mean@VertexDegree[graphs[[First[#2]]]]|> &, Range[0.02, 0.11, 0.01]] // Dataset$

Out[56]=

For each graph, find the vertex closest to (0,0) and extract the neighborhood of that vertex (i.e. all the vertices connected to it):

In[57]:=

Partition[
GraphPlot /@ (nghbs = NeighborhoodGraph[#, Nearest[VertexList[#], {0., 0.}]] & /@ graphs), 5] // GraphicsGrid

Out[57]=

Plot the corresponding points on the manifold:

In[58]:=

$GraphicsGrid[ Partition[ MapIndexed[ ListPointPlot3D[{{#1, #2, 1 - #1^2 + #2^2} & @@@ VertexList[#1], {#1, #2, 1 - #1^2 + #2^2} & @@@ VertexList[nghbs[[First[#2]]]]}, PlotStyle -> {Directive[Blue, PointSize[Tiny]], Directive[Red, PointSize[Medium]]}, Axes -> False, Boxed -> False] &, graphs], 5], ImageSize -> 1000]$

Out[58]=

Publisher

Samuele Mongodi

Requirements

Wolfram Language 12.2 (December 2020) or above

Version History

1.0.0 – 09 August 2021

Related Resources

License Information

This work is licensed under a Creative Commons Attribution 4.0 International License

ParametricManifoldToGraph

Details and Options

Examples

Basic Examples (4)

Scope (5)

Options (11)

Distance (4)

MaxConnectedComponent (1)

Neighbors (2)

RemoveIsolatedVertices (1)

VertexCoordinatesSpace (3)

Applications (2)

Neat Examples (3)

Publisher

Requirements

Version History

Related Resources

Related Symbols

License Information