绘制 Diestel-Leader 个图形的球
Plotting balls of the Diestel-Leader graphs
(对不起，如果问题涉及太多数学，那是数学编程的祸根！)
我的目标是在 Diestel-Leader 图中可视化有限半径球 DL(p, q)。 Here 是 W. Woess 的一篇文章，其中描述了带图片 构造（从第 3 页开始）。然而，我会在这里用较少的数学来表达这个想法。
它是由两棵无限树Tp和Tq[=构成的205=]，各自的化合价为p+1和q+1。我们考虑高度函数 h:Tp→Z和h':Tq→Z，意味着每个顶点x 高度 k 恰好有一个 parent 顶点高度 k-1 且恰好 [=73=]p (resp. q) children with height k+1.
现在，DL(p,q)的顶点集定义为是 {(x,y)∈Tp×Tq : h(x)+h '(y)=0}，以及两个顶点(x,y)和(x',y') 在DL(p中相邻,q) 当且仅当 x 和 x' 在 T 中相邻p和y和y'在T中相邻q.
原来DL(p,q)是不是一棵树！半径大于 4 的球总是有 non-contractible 个环。
我正在修复任意元素 o∈Tp 和 o'∈Tq的高度为零，我愿意绘制[=的sub-graph 73=]DL(p,q) 由距离为 (o,o')至多是某个半径R（即半径为R[=200=的球]).这意味着我必须在 Tp[= 中找到最多 R 到 o 的所有元素205=]，距离最多R到o'在T q，然后以某种方式得到一对这样的顶点之间的邻接关系。
另外，我主要关注p=2和q=3的情况，即DL (2,3)。但是，一般情况下的算法将非常受欢迎！
到目前为止，我首先尝试找到 Tp 中元素的表示。我尝试在我链接的文章中实现 (2.1) Tree and sequences. 段中给出的表示，但即使那样似乎也注定失败。然后，我想在高度 -R 处取一个顶点，并表示它的所有 children 直到一代 R （即是，我会有 2R+1 代顶点）。为了表示顶点的 child，这对应于用从 0 到 p-1 的整数标记所有向下的边。我先用了一个dec2base转换算法：
def dec2base(x,b):
if(x==0): return "0"
digits = []
while(x>0):
x,r = divmod(x,b)
digits.append(str(r))
return "".join(reversed(digits))
然后，我简单地遍历了所有可能的列表，并将所有顶点存储在一个列表中：
def Tree(p,R):
vertices = []
for h in range(2*R+1):
for k in range(p**h):
vertices.append((dec2base(k,p),h-R))
return vertices
此 returns 形式为 ("1201",-1) 的元素列表，其中字符串是从高度为 -R 的顶点开始的路径，整数是高度。的顶点。但是，有两个问题：
我生成的顶点太多了这个方法生成的顶点最多相距2R+1到原点，但它们可能比 R.
更远
这不会生成邻接关系。 在 this 博客文章中介绍的结构中，我们需要提供邻接关系，但我考虑使用这种方法，生成邻接函数（输入两个顶点并告诉您它们是否相邻）比生成所有此类值的列表（即 更容易例如邻接矩阵）。
考虑到这一点，我发现绘制 Diestel-Leader 图表更加困难...我对此一窍不通，自从我上次操纵 [=325= 以来已经很多年了] 结构。
谁能帮帮我吗？
P.S。 : 我以 python 为例，但我并没有限制自己使用任何特定的语言，特别是如果允许更容易实现的话！
更新
我想我想出了一个简单的方法来表示树的元素 Tp 也考虑了高度函数。图片胜于文字，这里是:
我圈出了原点顶点o∈Tp。在我的图片中，我取了 p=3 和 R=3。我从 x 距离 R 的（唯一）顶点开始 o 并且其高度是 h(x)=-R。我将其标记为 ""，并在表示顶点的字符串末尾附加一个 "0"、一个 "1" 或一个 "2" 以表示其 children .
由长度为 L 的字符串表示的顶点 x 的高度由关系 h(x)=L-R。这在尝试生成 DL(p,q) 时可能很方便。 但是，问题是我无法通过这种方法在树中实现生成半径为 R 的球的算法...我尝试了递归算法, 但我没有看到要传递什么作为参数...
现在，我已经成功地实现了递归以在 Tp[ 中生成半径为 R 的球！这是它的外观（与 hand-drawn 图片完全相同）：
我的代码如下：
import networkx as nx
import matplotlib.pyplot as plt
def T(p,R):
T = GraphVisualization()
def addChildren(vertex,gen):
if(gen>0):
for k in range(p):
T.addEdge(vertex,vertex+str(k))
addChildren(vertex+str(k),gen-1)
o = R*str(p-1)
addChildren(o,R)
for k in range(1,R+1):
addChildren(o[:(R-k)],R-k)
T.addEdge("0",str(p-1))
T.visualize()
请注意，这 非常 远非最佳，因为我多次生成多个边。但我不介意代码是否未优化，我只是希望它能够可视化球！
事实证明我已经非常接近完成了！它归结为为 Diestel-Leader 图编写边集的定义：
E[DL(p,q)]={(e1,e2)∈E[Tp]×E[Tq] : h(i( e1))+h'(i( e2))=h(t(e1))+h'(t(e2))=0}
和i(e)表示边的初始顶点e和t(e) 终端边缘。因此，我简单地遍历了两棵树的所有边缘并检查了该条件：
def height(v,R):
if(v=="0"): return -R
return len(v)-R
def DL(p,q,R):
Tp = T(p,R)
Tq = T(q,R)
G = GraphVisualization()
for e1 in Tp.visual:
for e2 in Tq.visual:
ie1, te1 = e1[1], e1[0]
ie2, te2 = e2[0], e2[1]
if(height(ie1,R)+height(ie2,R)==0 and height(te1,R)+height(te2,R)==0):
G.addEdge(ie1+","+ie2,te1+","+te2)
G.visualize()
Diestel-Leader 图 G 中的顶点由 "XXX,YYY" 形式的字符串表示，其中 "XXX" 是表示 T[ 中顶点的字符串=59=]p 和 "YYY" 是表示 Tq 中的顶点的字符串.
这是DL(2,3)中半径为2的球的图片（以"11,22"为中心）：
(对不起，如果问题涉及太多数学，那是数学编程的祸根！)
我的目标是在 Diestel-Leader 图中可视化有限半径球 DL(p, q)。 Here 是 W. Woess 的一篇文章，其中描述了带图片 构造（从第 3 页开始）。然而，我会在这里用较少的数学来表达这个想法。
它是由两棵无限树Tp和Tq[=构成的205=]，各自的化合价为p+1和q+1。我们考虑高度函数 h:Tp→Z和h':Tq→Z，意味着每个顶点x 高度 k 恰好有一个 parent 顶点高度 k-1 且恰好 [=73=]p (resp. q) children with height k+1.
现在，DL(p,q)的顶点集定义为是 {(x,y)∈Tp×Tq : h(x)+h '(y)=0}，以及两个顶点(x,y)和(x',y') 在DL(p中相邻,q) 当且仅当 x 和 x' 在 T 中相邻p和y和y'在T中相邻q.
原来DL(p,q)是不是一棵树！半径大于 4 的球总是有 non-contractible 个环。
我正在修复任意元素 o∈Tp 和 o'∈Tq的高度为零，我愿意绘制[=的sub-graph 73=]DL(p,q) 由距离为 (o,o')至多是某个半径R（即半径为R[=200=的球]).这意味着我必须在 Tp[= 中找到最多 R 到 o 的所有元素205=]，距离最多R到o'在T q，然后以某种方式得到一对这样的顶点之间的邻接关系。
另外，我主要关注p=2和q=3的情况，即DL (2,3)。但是，一般情况下的算法将非常受欢迎！
到目前为止，我首先尝试找到 Tp 中元素的表示。我尝试在我链接的文章中实现 (2.1) Tree and sequences. 段中给出的表示，但即使那样似乎也注定失败。然后，我想在高度 -R 处取一个顶点，并表示它的所有 children 直到一代 R （即是，我会有 2R+1 代顶点）。为了表示顶点的 child，这对应于用从 0 到 p-1 的整数标记所有向下的边。我先用了一个dec2base转换算法：
def dec2base(x,b):
if(x==0): return "0"
digits = []
while(x>0):
x,r = divmod(x,b)
digits.append(str(r))
return "".join(reversed(digits))
然后，我简单地遍历了所有可能的列表，并将所有顶点存储在一个列表中：
def Tree(p,R):
vertices = []
for h in range(2*R+1):
for k in range(p**h):
vertices.append((dec2base(k,p),h-R))
return vertices
此 returns 形式为 ("1201",-1) 的元素列表，其中字符串是从高度为 -R 的顶点开始的路径，整数是高度。的顶点。但是，有两个问题：
我生成的顶点太多了这个方法生成的顶点最多相距2R+1到原点，但它们可能比 R.
更远这不会生成邻接关系。 在 this 博客文章中介绍的结构中，我们需要提供邻接关系，但我考虑使用这种方法，生成邻接函数（输入两个顶点并告诉您它们是否相邻）比生成所有此类值的列表（即 更容易例如邻接矩阵）。
考虑到这一点，我发现绘制 Diestel-Leader 图表更加困难...我对此一窍不通，自从我上次操纵 [=325= 以来已经很多年了] 结构。
谁能帮帮我吗？
P.S。 : 我以 python 为例，但我并没有限制自己使用任何特定的语言，特别是如果允许更容易实现的话！
更新
我想我想出了一个简单的方法来表示树的元素 Tp 也考虑了高度函数。图片胜于文字，这里是:
我圈出了原点顶点o∈Tp。在我的图片中，我取了 p=3 和 R=3。我从 x 距离 R 的（唯一）顶点开始 o 并且其高度是 h(x)=-R。我将其标记为 ""，并在表示顶点的字符串末尾附加一个 "0"、一个 "1" 或一个 "2" 以表示其 children .
由长度为 L 的字符串表示的顶点 x 的高度由关系 h(x)=L-R。这在尝试生成 DL(p,q) 时可能很方便。 但是，问题是我无法通过这种方法在树中实现生成半径为 R 的球的算法...我尝试了递归算法, 但我没有看到要传递什么作为参数...
现在，我已经成功地实现了递归以在 Tp[ 中生成半径为 R 的球！这是它的外观（与 hand-drawn 图片完全相同）：
我的代码如下：
import networkx as nx
import matplotlib.pyplot as plt
def T(p,R):
T = GraphVisualization()
def addChildren(vertex,gen):
if(gen>0):
for k in range(p):
T.addEdge(vertex,vertex+str(k))
addChildren(vertex+str(k),gen-1)
o = R*str(p-1)
addChildren(o,R)
for k in range(1,R+1):
addChildren(o[:(R-k)],R-k)
T.addEdge("0",str(p-1))
T.visualize()
请注意，这 非常 远非最佳，因为我多次生成多个边。但我不介意代码是否未优化，我只是希望它能够可视化球！
事实证明我已经非常接近完成了！它归结为为 Diestel-Leader 图编写边集的定义：
E[DL(p,q)]={(e1,e2)∈E[Tp]×E[Tq] : h(i( e1))+h'(i( e2))=h(t(e1))+h'(t(e2))=0}
和i(e)表示边的初始顶点e和t(e) 终端边缘。因此，我简单地遍历了两棵树的所有边缘并检查了该条件：
def height(v,R):
if(v=="0"): return -R
return len(v)-R
def DL(p,q,R):
Tp = T(p,R)
Tq = T(q,R)
G = GraphVisualization()
for e1 in Tp.visual:
for e2 in Tq.visual:
ie1, te1 = e1[1], e1[0]
ie2, te2 = e2[0], e2[1]
if(height(ie1,R)+height(ie2,R)==0 and height(te1,R)+height(te2,R)==0):
G.addEdge(ie1+","+ie2,te1+","+te2)
G.visualize()
Diestel-Leader 图 G 中的顶点由 "XXX,YYY" 形式的字符串表示，其中 "XXX" 是表示 T[ 中顶点的字符串=59=]p 和 "YYY" 是表示 Tq 中的顶点的字符串.
这是DL(2,3)中半径为2的球的图片（以"11,22"为中心）：