ввод графа networkx в алгоритм zss (расстояние редактирования дерева) - PullRequest
Новая
       30

ввод графа networkx в алгоритм zss (расстояние редактирования дерева)

0 голосов
/ 18 января 2019

Я хочу вычислить расстояние редактирования дерева Чжан-Шаша между двумя деревьями (zss библиотека). Однако мои деревья представлены в виде networkx графиков (они на самом деле представляют собой HTML-деревья DOM). Пример в документации 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)

1 Ответ

0 голосов
/ 20 января 2019

Использование 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)

Поскольку корень является единственным узлом без входящих узлов, он должен работать.

...