比较两个具有边和节点属性的小有向图

Question

我想比较两个较小的有向 python-igraph 图，包括边或节点上的所有属性及其值以及边的方向。 python-igraph 包中有这样的功能吗？

我看到了 G1.isomorphic(G2) 和相关内容，但它们似乎不适用于属性，也不适用于边的方向性

示例：

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

Answer 1

您可以使用 node_compat_fn 和 edge_compat_fn 参数将自定义比较函数传递给方法 isomorphic_vf2。来自 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.

和

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.

示例：

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.

比较两个具有边和节点属性的小有向图

Compare two small directed graphs with attributes on edges and nodes

python

diff

compare

igraph