将networkx图输入到zss算法中(树编辑距离) [英] input networkx graph into zss algorithm (tree edit distance)

问题描述

我想计算2棵树之间的Zhang-shasha树编辑距离(zss库).但是，我的树是networkx图的形式(它们实际上代表DOM html树). zss 文档中的示例显示了如何手动创建树:

I want to compute the Zhang-Shasha tree-edit distance between 2 trees (zss library). However, my trees are in the form of networkx graphs (they actually represent DOM html trees). The example in the zss documentation shows how to create a tree by hand:

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对象，然后计算2棵树之间的编辑距离.

so I would like to convert tree objects of networkx class into a zss Node object, then compute the edit distance between 2 trees.

谢谢

(不要犹豫，告诉我您是否认为这是XY问题)

推荐答案

使用dfs_tree绝对可以提供帮助:

Using dfs_tree can definitely help:

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的根节点，但是知道我们有一棵有效的树，则可以通过调用以下命令获取源节点:

In case we don't know which node is G's root node, but know we have a valid tree, we can get the source node by calling:

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

由于根是唯一没有传入节点的节点，因此应该可以工作.

Since the root is the only node with no incoming nodes, that should work.

这篇关于将networkx图输入到zss算法中(树编辑距离)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！