networkx - 彩色图同构？

Question

我有两张彩色图表。我想确定它们是否同构，条件是同构必须保留顶点颜色。 networkx 中是否有算法可以做到这一点？

这些图是无向且简单的。

Answer 1

检查documentation对于is_isomorphic。它需要一个可选参数nodes_match，它是一个测试两个节点上的某些条件的函数。它由node_match(G1.node[n1], G2.node[n2])调用。因此在这种情况下，您需要一个函数来测试颜色是否匹配。

import networkx as nx

def colors_match(n1_attrib,n2_attrib):
    '''returns False if either does not have a color or if the colors do not match'''
    try:
        return n1_attrib['color']==n2_attrib['color']
    except KeyError:
        return False

G=nx.Graph()
G.add_node(1, color='y')
G.add_node(2, color='b')
H=nx.Graph()
H.add_node('a', color='y')
H.add_node('b', color = 'b')
nx.is_isomorphic(G,H,node_match=colors_match)
>True
H.add_node('c', color='r')
nx.is_isomorphic(G,H,node_match=colors_match)
>False