python - 将networkx图输入zss算法(树编辑距离)
问题描述
我想计算两棵树(zss
库)之间的 Zhang-Shasha 树编辑距离。但是,我的树是networkx
图形的形式(它们实际上代表 DOM html 树)。zss文档中的示例显示了如何手动创建树:
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 类的树对象转换为zss
Node 对象,然后计算两棵树之间的编辑距离。
谢谢
(如果您认为这是 XY 问题,请随时告诉我)
解决方案
使用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)
由于根是唯一没有传入节点的节点,因此应该可以。
推荐阅读
- php - phpmyadmin 4.9.4:我无法使用编辑、删除和删除。'未选择数据库'
- amazon-dynamodb - 通过 UI 导出 Dynamo DB
- android - 错误:查询返回的列没有字段
- angular - 如何在 IntelliJ 的项目概述中定义 Angular / Typescript 的生产范围
- javascript - TypeError:无法读取未定义的属性“参数”(Reactjs 路由器)
- r - 如何将“导出->另存为图像”单击过程集成到脚本中?
- python - 如何在读取 csv 文件后将列转换为数字以删除逗号?
- visual-studio - 展示 30 天评估试用版的 Visual Studio 社区
- mysql - 选择加入两个表,然后在mysql选择查询中按最新上传时间(uplaod_time列)排序
- sql - 可以为跳过的月份创建行的 SQL 查询