图同构

此笔记本展示了 Weisfeiler-Lehman 同构测试。

[1]:

from IPython.display import SVG
import numpy as np
from sknetwork.data import house
from sknetwork.topology import color_weisfeiler_lehman, are_isomorphic
from sknetwork.visualization import visualize_graph

图标记

[2]:

graph = house(metadata=True)
adjacency = graph.adjacency
position = graph.position

[3]:

labels = color_weisfeiler_lehman(adjacency)

[4]:

image = visualize_graph(adjacency, position, labels=labels)
SVG(image)

[4]:

../../_images/tutorials_topology_isomorphism_6_0.svg

[5]:

# first iteration
labels = color_weisfeiler_lehman(adjacency, max_iter=1)

[6]:

image = visualize_graph(adjacency, position, labels=labels)
SVG(image)

[6]:

../../_images/tutorials_topology_isomorphism_8_0.svg

Weisfeiler-Lehman 测试

[7]:

adjacency1 = house()

n = adjacency1.indptr.shape[0] - 1
reorder = list(range(n))
np.random.shuffle(reorder)
adjacency2 = adjacency1[reorder][:, reorder]

are_isomorphic(adjacency1, adjacency2)

[7]:

True