1

I want to compare two smaller directed python-igraph graphs, including all attributes and their values on edges or nodes and direction of edges. Is there any such function in the python-igraph package?

I saw G1.isomorphic(G2) and related, but they don't seem to work with attributes, nor with directionality of edges

Example:

import igraph as ig
G1=ig.Graph(directed=True)
G2=ig.Graph(directed=True)
G1.add_vertices(2)
G2.add_vertices(2)
G1.vs[0]['gaga'] = 'gugu'
G2.vs[0]['gaga'] = 'gogo'
G1.add_edge(0,1)
G2.add_edge(1,0)

print G1.isomorphic_vf2(G2)
>>>True
sal
  • 1,199
  • 1
  • 13
  • 31

1 Answers1

1

You can pass custom comparing functions to the method isomorphic_vf2 with the node_compat_fn and edge_compat_fn arguments. From the docs:

node_compat_fn - a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node.

and

edge_compat_fn - a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node.

Example:

import igraph as ig
G1=ig.Graph(directed=True)
G2=ig.Graph(directed=True)
G1.add_vertices(2)
G2.add_vertices(2)
G1.vs[0]['gaga'] = 'gugu'
G2.vs[0]['gaga'] = 'gogo'
G1.add_edge(0,1)
G2.add_edge(1,0)

print G1.isomorphic_vf2(G2)

def cmp_nodes(g1, g2, i1, i2):
    return g1.vs[i1]['gaga'] == g2.vs[i2]['gaga']

print G1.isomorphic_vf2(G2, node_compat_fn=cmp_nodes)

Here is the included unit-test of this exact feature.

Aske Doerge
  • 1,331
  • 10
  • 17
  • Yes I read that. It says I can compare one node pair and/or edge pair of each graph. Fact is I need to compare all nodes and all edges of the two graphs. – sal Dec 09 '15 at 23:16
  • I added an example which hopefully explains it better. The compare function is called with graph1 and graph2, and the indices of *some* pair of vertices. This function is called many times for many different pairs of vertices until the algorithm is finished. It exists to allow you to compare attributes on your nodes. You can create a similar function for edges if needed. – Aske Doerge Dec 09 '15 at 23:43
  • ok, that seems to return the results I was looking for. Would you mind explaining how the function ```cmp_nodes``` can be called as argument in the ```isomorphic_vf2``` function and on top of that , also without its own arguments? – sal Dec 10 '15 at 09:52
  • 1
    Of course. With the notation `node_compat_fn=cmp_nodes` we pass a handle to the function `cmp_nodes`, and bind it to the argument `node_compat_fn`. This means that inside `isomorphic_vf2` the `cmp_nodes` function can be called by writing `node_compat_fn(g1, g2, v1, v2)`. It is up to the programmer/code to ensure that the function is then called correctly. There is a minimal example here: http://stackoverflow.com/questions/706721/how-do-i-pass-a-method-as-a-parameter-in-python – Aske Doerge Dec 10 '15 at 22:51
  • Should the example be the following? `return g1.vs['gaga'][i1] == g2.vs['gaga'][i2]` i.e. with the index *after* the attribute name, since its a dictionary of lists. – afaulconbridge Mar 23 '20 at 20:05
  • @afaulconbridge The unittests still do it this way, so I assume it's still valid: https://github.com/igraph/python-igraph/blob/316fa6b3b42e348561b8b199338422841aceeb3c/tests/test_isomorphism.py#L6 – Aske Doerge Nov 19 '20 at 16:10