彩色图同构？

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

彩色图同构？

Colored graph isomorphism?

networkx