{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true, "pycharm": { "name": "#%% md\n" } }, "source": [ "# Graph isomorphism" ] }, { "cell_type": "markdown", "metadata": { "pycharm": { "name": "#%% md\n" } }, "source": [ "This notebook illustrates the Weisfeiler-Lehman test of isomorphism." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "pycharm": { "name": "#%%\n" } }, "outputs": [], "source": [ "from IPython.display import SVG\n", "import numpy as np\n", "from sknetwork.data import house\n", "from sknetwork.topology import color_weisfeiler_lehman, are_isomorphic\n", "from sknetwork.visualization import visualize_graph" ] }, { "cell_type": "markdown", "metadata": { "pycharm": { "name": "#%% md\n" } }, "source": [ "## Graph labeling" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "pycharm": { "name": "#%%\n" } }, "outputs": [], "source": [ "graph = house(metadata=True)\n", "adjacency = graph.adjacency\n", "position = graph.position" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "pycharm": { "name": "#%%\n" } }, "outputs": [], "source": [ "labels = color_weisfeiler_lehman(adjacency)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "pycharm": { "name": "#%%\n" } }, "outputs": [ { "data": { "text/plain": "", "image/svg+xml": "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n" }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "image = visualize_graph(adjacency, position, labels=labels)\n", "SVG(image)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "pycharm": { "name": "#%%\n" } }, "outputs": [], "source": [ "# first iteration\n", "labels = color_weisfeiler_lehman(adjacency, max_iter=1)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "pycharm": { "name": "#%%\n" } }, "outputs": [ { "data": { "text/plain": "", "image/svg+xml": "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n" }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "image = visualize_graph(adjacency, position, labels=labels)\n", "SVG(image)" ] }, { "cell_type": "markdown", "metadata": { "pycharm": { "name": "#%% md\n" } }, "source": [ "## Weisfeiler-Lehman test" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "pycharm": { "name": "#%%\n" } }, "outputs": [ { "data": { "text/plain": "True" }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "adjacency1 = house()\n", "\n", "n = adjacency1.indptr.shape[0] - 1\n", "reorder = list(range(n))\n", "np.random.shuffle(reorder)\n", "adjacency2 = adjacency1[reorder][:, reorder]\n", "\n", "are_isomorphic(adjacency1, adjacency2)\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.7" } }, "nbformat": 4, "nbformat_minor": 1 }