CoCalc -- Graph Isomorphism.ipynb

Project: MAT 2540

Views: ⁶⁵

Visibility: Unlisted (only visible to those who know the link)

Image: ubuntu2004

Kernel: Python 3 (Anaconda 2020)

In [1]:

import networkx as nx

In [2]:

G1 = nx.Graph()

In [3]:

G1.add_nodes_from('abcdefgh')

In [4]:

s1 = ['ab','bc','cd','da','dh','bf','ef','fg','gh','he']

In [5]:

for s in s1:
    G1.add_edge(s[0],s[1])

In [6]:

nx.draw(G1,with_labels=True)

In [7]:

G2 = nx.Graph()

In [8]:

G2.add_nodes_from('stuvwxyz')

In [9]:

s2 = ['st','tu','uv','vs','vz','zw','wx','xy','yz','ws']

In [10]:

for s in s2:
    G2.add_edge(s[0],s[1])

In [11]:

nx.draw(G2,with_labels=True)

In [12]:

nx.faster_could_be_isomorphic(G1,G2)

True

In [13]:

nx.fast_could_be_isomorphic(G1,G2)

True

In [14]:

nx.could_be_isomorphic(G1,G2)

True

In [15]:

nx.is_isomorphic(G1,G2)

False

In [16]:

for path in nx.all_simple_paths(G1,'a','a'):
    print(path)

In [0]: