使用networkx对边缘进行约束的图同构

Question

我想定义我自己的两个图的同构。我想检查两个图是否同构，因为每条边都有一些属性——基本上是放置每条边的顺序。我想知道是否可以使用以下方法：

networkx.is_isomorphic(G1,G2, edge_match=some_callable)

以某种方式通过定义函数some_callable()。

例如，下图是同构的，因为您可以重新标记节点以从另一个节点获取一个。

即，重新标记 [2<->3]。

但是，下面的图不是同构的。

没有办法通过重新标记节点来从另一个获得一个。

Answer 1

干得好。这正是该edge_match选项的用途。我将创建 3 个图，前两个是同构的（即使权重有不同的名称 --- 我已经设置了比较函数来说明这一点）。第三个不是同构的。import networkx as nxG1 = nx.Graph()G1.add_weighted_edges_from([(0,1,0), (0,2,1), (0,3,2)], weight = 'aardvark')G2 = nx.Graph()G2.add_weighted_edges_from([(0,1,0), (0,2,2), (0,3,1)], weight = 'baboon')G3 = nx.Graph()G3.add_weighted_edges_from([(0,1,0), (0,2,2), (0,3,2)], weight = 'baboon')def comparison(D1, D2):&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; #for an edge u,v in first graph and x,y in second graph&nbsp; &nbsp; #this tests if the attribute 'aardvark' of edge u,v is the&nbsp;&nbsp; &nbsp; #same as the attribute 'baboon' of edge x,y.&nbsp; &nbsp; return D1['aardvark'] == D2['baboon']nx.is_isomorphic(G1, G2, edge_match = comparison)> Truenx.is_isomorphic(G1, G3, edge_match = comparison)> False

Answer 2

此处使用完全相同的图表专门回答问题中的问题。请注意，我正在使用 networkx.MultiGraph 并在放置这些边时考虑一些“排序”。import networkx as nxG1,G2,G3,G4=nx.MultiGraph(),nx.MultiGraph(),nx.MultiGraph(),nx.MultiGraph()G1.add_weighted_edges_from([(0, 1, 0), (0, 2, 1), (0, 3, 2)], weight='ordering')G2.add_weighted_edges_from([(0, 1, 0), (0, 3, 1), (0, 2, 2)], weight='ordering')&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;G3.add_weighted_edges_from([(0, 1, 0), (0, 1, 1), (2, 3, 2)], weight='ordering')G4.add_weighted_edges_from([(0, 1, 0), (2, 3, 1), (0, 1, 2)], weight='ordering')def comparison(D1,D2):&nbsp; &nbsp; return D1[0]['ordering'] == D2[0]['ordering']nx.is_isomorphic(G1,G2, edge_match=comparison)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;>Truenx.is_isomorphic(G3,G4, edge_match=comparison)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;>False