1
$\begingroup$

Trying to match a Query subgraph to a Target graph, where:

Query:

enter image description here

and Target:

enter image description here

As I understand matching in this case should return tuples of matching nodes:

(1,1)
(2,2)
(3,3)

where first number is a node in Query and second is node in Target

Yet with the following code I get another result:

import networkx as nx
import networkx.algorithms.isomorphism as iso

# Target graph
target = nx.Graph()
target.add_edge(1, 2)
target.add_edge(1, 3)
target.add_edge(1, 5)
target.add_edge(2, 3)
target.add_edge(3, 4)
target.add_edge(4, 5)

# Add attributes to target nodes
target.nodes[1]['cat'] = 1
target.nodes[2]['cat'] = 2
target.nodes[3]['cat'] = 3
target.nodes[4]['cat'] = 4
target.nodes[5]['cat'] = 5

# Query graph
query = nx.Graph()
query.add_edge(1, 2)
query.add_edge(1, 3)
query.add_edge(2, 3)

# Add attributes to query graph
query.nodes[1]['cat'] = 1
query.nodes[2]['cat'] = 2
query.nodes[3]['cat'] = 3

# GraphMatcher is supposed to call this function when matching nodes
def node_match(q_node_dict, t_node_dict): # This is never called!
    #print("q_node_dict: {} t_node_dict: {}".format(q_node_dict, t_node_dict))
    return q_node_dict['cat'] == t_node_dict['cat']

# Matcher
GM = iso.GraphMatcher(query, target, node_match=node_match)

# This should print matching nodes?
for x in GM.candidate_pairs_iter():
    print(x)

# What this should print?
for x in GM.subgraph_isomorphisms_iter():
    print(x)

Instead code in GM.candidate_pairs_iter() returns:

(1,1)
(2,1)
(3,1)

As if all nodes in Query match to a single node '1' in the Target. Why?

Iterator GM.subgraph_isomorphisms_iter() is empty. What should it iterate?

In hope to facilitate subgraph matching I have added attributes to Query and Target. Nodes 1,2,3 in Query and Target have the same values and should match, but it looks like they don't.

According to NetworkX documentation node_match parameter of GraphMatcher constructor is a "callable function that returns True iff node n1 in G1 and n2 in G2 should be considered equal during the isomorphism test. The function will be called like:

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

and this function is never called in my case!

What am I missing? Thanks!

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.