将 networkx 图输入 zss 算法（树编辑距离）

Question

我想计算 2 棵树（zss 库）之间的 Zhang-Shasha 树编辑距离。但是，我的树是 networkx 图表的形式（它们实际上代表 DOM html 树）。 zss中的例子documentation展示了如何手工创建树：

from zss import *
A = (
    Node("f")
        .addkid(Node("a")
            .addkid(Node("h"))
            .addkid(Node("c")
                .addkid(Node("l"))))
        .addkid(Node("e"))
    )
zss.simple_distance(A, A) # [0.0]

这将是同一棵树：

import networkx as nx
G=nx.DiGraph()
G.add_edges_from([('f', 'a'), ('a', 'h'), ('a', 'c'), ('c', 'l'), ('f', 'e')])

所以我想将 networkx class 的树对象转换成 zss 节点对象，然后计算两棵树之间的编辑距离。

谢谢

（如果您认为这是 XY 问题，请随时告诉我）

Answer 1

使用dfs_tree绝对有帮助：

import zss
import networkx as nx

G=nx.DiGraph()
G.add_edges_from([('f', 'a'), ('a', 'h'), ('a', 'c'), ('c', 'l'), ('f', 'e')])
T = nx.dfs_tree(G, source='f')
nodes_dict = {}
for edge in T.edges():
    if edge[0] not in nodes_dict:
        nodes_dict[edge[0]] = zss.Node(edge[0])
    if edge[1] not in nodes_dict:
        nodes_dict[edge[1]] = zss.Node(edge[1])
    nodes_dict[edge[0]].addkid(nodes_dict[edge[1]])

print(zss.simple_distance(nodes_dict['f'], nodes_dict['f'])) # 0.0

如果我们不知道哪个节点是 G 的根节点，但知道我们有一个有效的树，我们可以通过调用获取源节点：

source = [n for (n, d) in G.in_degree() if d == 0][0]
T = nx.dfs_tree(G, source=source)

因为根是唯一没有传入节点的节点，所以应该可以。

将 networkx 图输入 zss 算法（树编辑距离）

input networkx graph into zss algorithm (tree edit distance)

python

tree

graph

distance

networkx