Python 中“Laakso 图”的实现

Question

我想利用 networkX Python 包实现“Laakso 图”，这是一个生成分形图案的递归图。

Laakso 图 $L_k$ 在正整数上递归定义。

$L_1$ 只是由一条边连接的两个节点。

然后，通过用标准 4 周期图的副本替换 $L_{i-1}$ 中每条边的一部分，从 $L_{i-1}$ 构建 $L_i$。（等效地，用 $L_2$ 的副本替换每个完整边缘）。这是 $L_2$ 和 $L_3$ 的图（尽管有有向边，我不关心）。

我没有太多编码经验（我是一名经过训练的数学家），老实说，我一直在使用 ChatGPT 的帮助来创建 Python 代码来实现不同类型的图表。

然而，这个图并不为人所知，并且递归的元素给正确实现带来了一些困难。

本质上，我希望能够调用一些由 $k$ 参数化的函数，该函数创建 $k$ 级别的 Laakso 图。

实现 $L_1$ 很简单，$L_2$ 也不难。但我不确定编写代码的最佳方法，以便下一级图始终获得正确数量的节点以及正确位置的边。

编辑：特别是，当您在下一个级别创建新节点时，我对重新标记节点感到困惑。例如，如果我们尝试用 L_2 的副本替换边 (1,2)，则需要添加 4 个新节点 3,4,5,6 和一些新边。但是带有这些标签的原始节点会发生什么情况呢？也许有一种方法可以通过新节点要替换的边来索引新节点，这样我们就可以以这样的方式插入新节点：如果边 (1,2) 是“边 1”，则替换边 1 的新节点是 1.1 、1.2、1.3、1.4。我已经觉得这变得太复杂了，但也许必须如此才能正确实现这一点。

编辑2：为清楚起见，另一个图。

Answer 1

我相信以下实施是有效的。我决定用对放置节点的边缘进行编码的字符串来标记节点。请参阅下面的脚本和生成的图像。

注意：受到 Paul 方法的启发，我稍微重构了代码，使所有内容都更具可读性。如果仅需要抽象图，则可以简单地删除对pos和 的引用pos_new以及用于查找和设置节点位置的块。

# script to get the Laakso graph L_k
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

k = 3
expansion_motif = [
    (0, 1),
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 4),
    (4, 5)
]
relative_positions = 0.25 * np.array([
    [ 0, 0],
    [ 0, 1],
    [-1, 2],
    [ 1, 2],
    [ 0, 3],
    [ 0, 4]
])

def get_next(G,pos):
    res = nx.Graph()
    pos_new = {}
    for a,b in G.edges:
        # generate node labels
        labels = [a] + [f"[{a}{b}]{i}" for i in range(4)] + [b]
        
        # add edges to graph
        for i,j in expansion_motif:
            res.add_edge(labels[i],labels[j])
        
        # find node positions
        start,end = pos[a],pos[b]
        dx,dy = end - start
        rot = np.array([[dy,-dx],[dx,dy]])
        points = start + relative_positions@rot
        
        # set node positions
        pos_new.update(zip(labels,points))
    return res,pos_new


G = nx.Graph()
G.add_edge('0','1')
pos = {'0':np.array([0,0]),'1':np.array([0,1])}

for j in range(k-1):
    G,pos = get_next(G,pos)

plt.figure(figsize = (10,10))
nx.draw(G, with_labels = True, node_color = 'orange',pos = pos)

结果图：

另外，这是 L_4 的图。它是通过针对 k = 4 运行上述脚本生成的，但将该nx.draw行替换为以下代码块：

for k,v in pos.items():
    a,b = v
    pos[k] = np.array([-b,a])
plt.figure(figsize = (10,10))
nx.draw(G, pos = pos, node_size = 10)
plt.gca().set_aspect('equal')

这是 L_6 的类似图，但用node_size = 0的是。