NetworkX: Subgraph Isomorphism by edge and node attributes

Question

Suppose I have 2 graphs A and B and I want to know if A is a subgraph of B. The nodes contain attributes, say, 'size' and 'material'.

When I run:

GM = networkx.algorithms.isomorphism.GraphMatcher(B,A)
print networkx.algorithms.isomorphism.subgraph_is_isomorphic()

This only matches graph by edges only and not by edges and attribute.

Any clue on how check attributes?

Also, suppose B contains 2 connected graphs of A.

When I run:

GM.mapping

This will output only 1 of the subgraphs of A. Any idea on how to output every subgraph?

Beating

Answer 1

I've solved this by using:

print GM = iso.GraphMatcher(B,A,node_match=iso.categorical_node_match(['material', 'size'],['metal',1]))

What I didn't know before is that ['metal',1] is just a default and not a hard match.

Beating

Can you explain the "default" value? I'm not sure how it will be used in the function. – Horatia

@jim-raynor If a node in the graph does not have a value for the attribute (i.e. the attribute isn't assigned), then the "default" value given above is taken as the default for such nodes. You could pass None if you are uncomfortable assuming attributes for nodes that shouldn't have them. – Taryn

And yes the syntax is a bit confusing/(not-straightforward). Even I thought it was some kind of hard match but couldn't wrap my head around why someone would want that. Eventually, I did find the explanation after little digging. – Taryn

Answer 2

You can iterate over all possible subgraphs in the following way

GM = networkx.algorithms.isomorphism.GraphMatcher(B,A)
for subgraph in GM.subgraph_isomorphisms_iter():
    print subgraph

subgraph in this example is a dictionary that maps nodes of B to nodes of A.

For the question of attribute matching, drum's suggestion has worked for me. Additional attribute matching actually speeds up things significantly for large graphs.

Crane