如何使两个相同的 networkx 图具有相同的节点顺序

Question

我有两个具有相同拓扑结构的 networkx 图。他们的 weisfeiler_lehman_graph_hash 是一样的。 is_isomorphic returns 是的。但是这两个图的节点顺序不同。所以我的问题是如何重新排序它们的节点，以便它们可以具有相同的节点顺序。这是一个简单的例子：

>>> import networkx as nx
>>> import networkx.algorithms.graph_hashing as graph_hashing
>>> import networkx.algorithms.isomorphism as isomorph
>>> A = nx.Graph()
>>> B = nx.Graph()
>>> A.add_nodes_from([(4,{"elem":"N"}),(5,{"elem":"H"}),(6,{"elem":"C"})])
>>> A.add_edges_from([(5,6),(4,6)])
>>> B.add_nodes_from([(1,{"elem":"C"}),(2,{"elem":"N"}),(3,{"elem":"H"})])
>>> B.add_edges_from([(1,2),(1,3)])
>>> A.nodes.data()
NodeDataView({4: {'elem': 'N'}, 5: {'elem': 'H'}, 6: {'elem': 'C'}})
>>> B.nodes.data()
NodeDataView({1: {'elem': 'C'}, 2: {'elem': 'N'}, 3: {'elem': 'H'}}) 
#B have different node label and order from A
>>> isomorph.is_isomorphic(A,B)
True
>>> graph_hashing.weisfeiler_lehman_graph_hash(A,node_attr='elem')
'41951f5f6a37cdb32e7de9b6429fa0e9'
>>> graph_hashing.weisfeiler_lehman_graph_hash(B,node_attr='elem')
'41951f5f6a37cdb32e7de9b6429fa0e9'  
#B have same graph hash and is isomorphic to A

我想要的是一些函数 reorder_node_by()

>>> A.nodes.data()
NodeDataView({4: {'elem': 'N'}, 5: {'elem': 'H'}, 6: {'elem': 'C'}})
>>> B.nodes.data()
NodeDataView({1: {'elem': 'C'}, 2: {'elem': 'N'}, 3: {'elem': 'H'}}) 
>>> B.reorder_node_by(A)
>>> B.nodes.data()
NodeDataView({1: {'elem': 'N'}, 2: {'elem': 'H'}, 3: {'elem': 'C'}})

Answer 1

is_isomorphic中使用的VF2算法有一个扩展接口，你可以从它的documentation:

中获取

from networkx.algorithms import isomorphism
GM = isomorphism.GraphMatcher(B, A)
GM.is_isomorphic()
# True
GM.mapping
# {2: 4, 1: 6, 3: 5}

然后你需要结合relabel_nodes:

B = nx.relabel_nodes(B, GM.mapping, copy=False)

如何使两个相同的 networkx 图具有相同的节点顺序

How to make two same networkx graph have same node order

networkx

python-3.x