Networkx: как использовать аргумент node_match в optimize_graph_edit_distance? - PullRequest
Новая
       10

Networkx: как использовать аргумент node_match в optimize_graph_edit_distance?

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

Я пытаюсь сравнить два графика с помощью алгоритма optimize_graph_edit_distance в NetworkX: 

optimize_graph_edit_distance(G1, G2,
    node_match=None,
    node_subst_cost=None,
    edge_match=None,
    node_del_cost=None,
    edge_subst_cost=None,
    edge_del_cost=None,
    edge_ins_cost=None,
    upper_bound=None)

Я дал каждому узлу на обоих графиках заданное количество атрибутов в форме словаря и с помощью node_match Я могу указать, должны ли узлы N1 и N2 считаться равными во время сопоставления.

Функция node_match должна вызываться так: 

node_match(G1.nodes[n1], G2.nodes[n2])  >>n1 and n2 are node attribute dictionaries as input.

Моя проблема в том, что у меня более одного узла в каждом графике. Следовательно, как мне дать функции все остальные словари атрибутов для сравнения всех других узлов?

1 Ответ

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

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

import networkx as nx
G1 = nx.DiGraph()
G1.add_nodes_from([(0, {'label':'a'}), (1, {'label':'b'}),(2, {'label':'c'})])
G1.add_edges_from([(0,1),(0,2)])

G2 = nx.DiGraph()
G2.add_nodes_from([(3, {'label':'a'}), (4, {'label':'b'}),(5, {'label':'c'})])
G2.add_edges_from([(3,4),(3,5)])

print(G1.nodes())
print(G1.edges())

print(G2.nodes())
print(G2.edges())

for dist in nx.algorithms.similarity.optimize_graph_edit_distance(G1, G2, node_match=lambda a,b: a['label'] == b['label']):
    print(dist)

Здесь, даже если идентификаторы узлов на двух графиках различны, расстояние будет нулевым. Это потому, что мы определили функцию, которая сравнивает 2 узла, как lambda a,b: a['label'] == b['label'], что означает, что два узла считаются равными во время сопоставления, если они имеют одинаковое значение метки.

Аналогично, вы можете реализовать любую логику, какую пожелаете, без особой обработки каждой пары узлов в ваших графиках.

...