You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The Tutte embedding is a graph-drawing technique to position vertices of a graph so that the outer face is a convex polygon and each interior vertex is at the mean of the positions of its adjacent vertices.
SageMath does not seem to have it built-in yet.
Proposed Solution
An implementation in sage can be found at tuttedraw due to Manfred Scheucher. Here is the core code for it.
from scipy.spatial import ConvexHull
from sys import argv
from ast import literal_eval
import xml.etree.ElementTree as ET
from scipy import optimize
def tutte_layout(G,outer_face,weights):
V = G.vertices()
pos = dict()
l = len(outer_face)
a0 = pi/l+pi/2
for i in range(l):
ai = a0+pi*2*i/l
pos[outer_face[i]] = (cos(ai),sin(ai))
n = len(V)
M = zero_matrix(RR,n,n)
b = zero_matrix(RR,n,2)
for i in range(n):
v = V[i]
if v in pos:
M[i,i] = 1
b[i,0] = pos[v][0]
b[i,1] = pos[v][1]
else:
nv = G.neighbors(v)
s = 0
for u in nv:
j = V.index(u)
wu = weights[u,v]
s += wu
M[i,j] = -wu
M[i,i] = s
sol = M.pseudoinverse()*b
return {V[i]:sol[i] for i in range(n)}
s = 'JsTB@_OBGN?'
G = Graph(s, sparse=True);
F = G.faces()
F = [tuple(e[0] for e in f) for f in F]
outer_face=F[0]
weights = dict()
for (u,v) in G.edges(labels=None):
weights[u,v] = weights[v,u] = 1
G.set_pos(tutte_layout(G,outer_face,weights))
G.plot(edge_thickness=2, vertex_size=150)
Problem Description
The Tutte embedding is a graph-drawing technique to position vertices of a graph so that the outer face is a convex polygon and each interior vertex is at the mean of the positions of its adjacent vertices.
SageMath does not seem to have it built-in yet.
Proposed Solution
An implementation in sage can be found at tuttedraw due to Manfred Scheucher. Here is the core code for it.
Alternatives Considered
Additional Information
No response
Is there an existing issue for this?
The text was updated successfully, but these errors were encountered: