isomorphism guide

[gilderdeegee-ship-it]

i have found the below a little helpful in weeding out graphs with the same degree set

def add_adjacency(G, add_itself):
for node in list(G.nodes): total = 0
for adj_node in list(G.adj[node]): total = total + G.degree[adj_node]
if add_itself: G.nodes[node]['adj_degree'] = total + G.degree(node)
else: G.nodes[node]['adj_degree'] = total

def extract_node_info(G): thislist = []
for data in G.nodes.data(): for dicto in data:
if isinstance(dicto, dict): # don't call it dict call it dicto thislist.append(dicto['adj_degree'])
`` return thislist

but is not effective in all cases

[rossbar]

If I'm reading correctly (the formatting is a little wonky), this looks like a form of generalized degree - i.e. degree-of-neighbors. Indeed, graphs that are isomorphic should have the same distribution of this property (or any other generalized degree - i.e. degree-of-neighbors'-neighbors, etc.) so this is a valid check for whether graphs could be isomorphic (i.e. if the check fails, then they're definitely not - but True doesn't guarantee that they are isomorphic).

Now - what would be interesting (to me at least) would be if you could find a pair of graphs where some form of generalized degree shows that graphs can't be isomorphic where checks of other properties (e.g. degree, triangle, clique, etc.) don't. More concretely: can you find a pair of graphs G, H such that nx.could_be_isomorphic(G, H, properties="dt") (or better yet, properties="dtc") is True, but the generalized degree check returns False. This could be a nice addition to the article if so!

Note that the article provides a recipe for such investigations in a brute-force manner, but perhaps you could come up with a cleverer way of finding/generating such examples :)