CODEWITHSUNDEEP
pythongraphnetworkx
Kristian Siebenrock
Kristian Siebenrock

Reputation: 31

Networkx: how to use node_match argument in optimize_graph_edit_distance?

I'm trying to compare two graphs with the help of the optimize_graph_edit_distance algorithm on 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)

I gave each node on both graphs a set amount of attributes in the form of a dictionary and with the help of node_match I can specify if nodes N1 and N2 should be considered equal during matching.

The function node_match should be called like so:

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

My problem is that I have more than one node in each graph. Therefore, how do I give the function all other attribute dictionaries to compare all other nodes?

Upvotes: 3

Views: 2040

Answers (1)

zohar.kom
zohar.kom

Reputation: 1845

node_match is a function that returns True if node n1 in G1 and n2 in G2 should be considered equal during matching. For example:

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)

Here, even though the node identifiers in the two graphs are different, the distance will be zero. That's because we defined the function that compares 2 nodes as lambda a,b: a['label'] == b['label'], meaning that two nodes are considered equal during matching if they have the same 'label' value.

Similarly, you can implement any logic you wish to without specifically treating every pair of nodes in your graphs.

Upvotes: 2

Related Questions