Как измерить расстояние редактирования графика с учетом имен узлов

Question

Я определил два Графа в Python, используя библиотеку networkx, и теперь я хочу измерить расстояние между этими двумя графами, учитывая «имена» узлов

Я создал два Графика, выглядящих абсолютно одинаково (деревографики)

G=nx.Graph()
G.add_edges_from([("A","B"),("A","C")])

H=nx.Graph()
H.add_edges_from([("X","Y"),("X","Z")])

res=nx.graph_edit_distance(G,H)
res2=nx.optimize_edit_paths(G,H)
res3=nx.optimal_edit_paths(G,H)

Я хочу, чтобы все узлы были заменены, потому что узлы не имеют одинакового имени, но я получаю результат для стоимости (изменения / расстояния) 0. Это означает, что функцияне учитывает имена узлов.

В документации предлагается использовать функцию "node_math", но я не знаю, как ее использовать.Это не похоже на функцию networkx.

Answer 1

Причина, по которой он дает ответ как 0, заключается в том, что он считает узлы равными. Если вы видите документацию, там упоминается, что

node_match (callable) - функция, которая возвращает True, если узел n1 в G1 и n2 в G2 следует считать равным во время сопоставления.

Функция будет вызываться как

node_match(G1.nodes[n1], G2.nodes[n2]).

То есть функция получит словари атрибутов узла для n1 и n2 в качестве входов.

Теперь, поскольку вы не объявили никаких атрибутов, тогда в этом случае

G.nodes['A'] will return {}

и

H.nodes['Z'] will return {}

Теперь, поскольку оба являются пустыми словарями, они будут считаться равными.

Вот модифицированная версия вашего кода, где я добавил атрибут метки для вашего узла.

import networkx as nx

G=nx.Graph()
G.add_nodes_from([("A", {'label':'a'}), ("B", {'label':'b'}),
                  ("C", {'label':'c'})])

G.add_edges_from([("A","B"),("A","C")])

H=nx.Graph()
H.add_nodes_from([("X", {'label':'x'}), ("Y", {'label':'y'}),
                  ("Z", {'label':'z'})])
H.add_edges_from([("X","Y"),("X","Z")])

# This is the function which checks for equality of labels
def return_eq(node1, node2):
    return node1['label']==node2['label']

print(nx.graph_edit_distance(G, H, node_match=return_eq))
# Output: 3