Hi @s99 , welcome to the QuEra forum!
You ask a great question and I believe I understand it in two parts:
- Are there tools to convert an arbitrary graph to a unit-disk graph (UDG)
- Can there be a unit-disk embedding of the UDG
I’ve relayed your first question to Jonathan Wurtz, one of algorithms expert here at QuEra and his answer was that determining if a graph is Unit Disk is a hard computational question and you are better of just trying to convert your graph in question to a Unit Disk Graph to see if it was one to begin with. The catch is this method can produce false negatives (a UDG does not map to a UDG) but no false positives (a non UDG maps to a UDG).
If your graph is “close” to a UDG you can consider forced directed optimization to nudge vertices in the graph to get UDG form.
If you have an arbitrary graph you are trying to turn into a UDG you can consider taking the the Gram matrix of your graph’s distance matrix and then using the eigendecomposition of the gram matrix to inform a projection onto positions.
This Python code snippet may be of use:
def eigen_layout(G,dimension = 2):
"""
Computes positions on a graph [ G ] based on the distance matrix.
The distance matrix is the shortest distance between any two nodes.
It does this via a projection of the Gram matrix down to a dimension [ dimension ].
If the dimension is equal to the size of the graph, then
the mapping is exact.
This is useful for graphs which actually have some underlying 2d structure,
because on long scales the distance does actually scale in a euclidian sense.
"""
N = len(G.nodes)
# Compute the distance matrix
D = zeros([N,N])
dd = dict(nx.algorithms.shortest_paths.generic.shortest_path_length(G))
for i in range(N):
for j in range(N):
D[i,j] = dd[i][j]
# Compute the Gram matrix https://math.stackexchange.com/questions/156161/finding-the-coordinates-of-points-from-distance-matrix
M = ((D[:,0:1]**2 + D[:,0:1].T**2) - D**2)/2
# Eigen-decomposition. Gram matrices are PSD and Hermetian.
eigees = linalg.eigh(M)
if eigees[0][0]<0:
max_dimension = sum(eigees[0]>0)-1
Warning('Graph is non-dimensional! Maximum dimension is {:0.0f}'.format(max_dimension))
# Positions are eigenvectors, weighted by the eigenvalue.
X = (eigees[1][:,-dimension::] * sqrt(eigees[0][-dimension::])).T
return {i:X[:,i] for i in range(X.shape[1])}
As for the second part of your question I might need some more clarification to answer it. Are you asking if a graph that is already UDG can work with the Blockade Radius or are you looking for the ability to convert an arbitrary graph and have an embedding as a UDG?