检查子图尊重节点标签

Question

我有两个图G和s，每个图的节点上都有离散的标签。我想要检验S是否是G的子图在某种意义上，是否存在一个内射映射，将S中的节点映射到G，使得边和节点标签都保持不变。

到目前为止，我已经看到了VF2算法在Networkx (https://networkx.org/documentation/stable/reference/algorithms/isomorphism.vf2.html)，但该方法似乎不支持节点标签的保存。

Answer 1

检查S中的每个节点和边在g中是否存在

import networkx as nx

def is_subgraph(S, G):
if set(list(S.nodes)).issubset(list(G.nodes)) and 
set(list(S.edges)).issubset(list(G.edges)):
return True
return False

if __name__ == '__main__':
pass
S = nx.complete_graph(5)
G = nx.complete_graph(10)
H = nx.erdos_renyi_graph(100, 0.1)
print(is_subgraph(S, G))
# True
print(is_subgraph(S, H))
# False