Trying to generate a random graph, and then generate another one until it is isomorphic with the first one

Question

I am new to python and am trying to write a program that can take a matrix of 1's and 0's as an input, create a graph from it, then keep generating another random graph until it find an isomorphic pair.

I keep messing up my logic and keep getting either an infinite loop or a loop that doesn't accomplish what I want accomplished. Any help would be appreciated.

Here's the part of my program with the issue

i = 0
for i in range(counterP):
    g4 = numpy.reshape(numpy.random.random_integers(0, 1, size=matrix_sizeP), (vertex_countP, vertex_countP))
    g5 = numpy.reshape(numpy.random.random_integers(0, 1, size=matrix_sizeP), (vertex_countP, vertex_countP))
    G4 = nx.Graph(g4)
    G5 = nx.Graph(g5)
    G4G5 = iso.GraphMatcher(G4,G5)
    isomP = G4G5.is_isomorphic()

    if isomP is True:
        ed = nx.number_of_edges(G4)
        print("Iteration", i, ":", ed, "edges")
        print(G4G5.mapping)
        i = i + 1
    else:
        g5 = numpy.reshape(numpy.random.random_integers(0, 1, size=matrix_sizeP), (vertex_countP, vertex_countP))
        G5 = nx.Graph(g5)
        isomP = G4G5.is_isomorphic()

Answer 1

Your program logic is indeed slightly off. Here is a version which does what I understand you want:

import numpy as np
import networkx as nx
from networkx.algorithms.isomorphism import GraphMatcher

def brute_force_find_iso_pair(shape, maxiter, template=None):
    def make_random_graph():
        return nx.Graph(np.random.random_integers(0, 1, shape))
    G4 = make_random_graph() if template is None else template
    def check_iso(G5):
        return GraphMatcher(G4, G5).is_isomorphic()
    for n in range(maxiter):
        G5 = make_random_graph()
        if check_iso(G5):
            break
    else:
        G5 = None
    return G4, G5, n + 1

# example
G4, G5, n = brute_force_find_iso_pair((4, 4), 50)
print(f"""After {n} iterations:
template: {G4.adj}
match:    {G5 and G5.adj}
""")

Sample runs:

After 43 iterations:
template: {0: {1: {'weight': 1}, 3: {'weight': 1}, 2: {'weight': 1}}, 1: {0: {'weight': 1}, 1: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}}, 2: {1: {'weight': 1}, 0: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}}, 3: {0: {'weight': 1}, 1: {'weight': 1}, 2: {'weight': 1}}}
match:    {0: {2: {'weight': 1}, 1: {'weight': 1}, 3: {'weight': 1}}, 1: {0: {'weight': 1}, 3: {'weight': 1}, 2: {'weight': 1}}, 2: {0: {'weight': 1}, 1: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}}, 3: {1: {'weight': 1}, 0: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}}}

After 50 iterations:
template: {0: {1: {'weight': 1}, 2: {'weight': 1}}, 1: {0: {'weight': 1}, 3: {'weight': 1}, 2: {'weight': 1}}, 2: {0: {'weight': 1}, 1: {'weight': 1}, 3: {'weight': 1}}, 3: {1: {'weight': 1}, 2: {'weight': 1}}}
match:    None

After 25 iterations:
template: {0: {1: {'weight': 1}, 3: {'weight': 1}, 2: {'weight': 1}}, 1: {0: {'weight': 1}, 2: {'weight': 1}}, 2: {1: {'weight': 1}, 0: {'weight': 1}, 2: {'weight': 1}}, 3: {0: {'weight': 1}}}
match:    {0: {1: {'weight': 1}}, 1: {0: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}}, 2: {1: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}}, 3: {1: {'weight': 1}, 2: {'weight': 1}}}

After 2 iterations:
template: {0: {0: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}}, 1: {2: {'weight': 1}, 3: {'weight': 1}}, 2: {0: {'weight': 1}, 1: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}}, 3: {0: {'weight': 1}, 1: {'weight': 1}, 2: {'weight': 1}}}
match:    {0: {2: {'weight': 1}, 3: {'weight': 1}}, 1: {1: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}}, 2: {0: {'weight': 1}, 1: {'weight': 1}, 3: {'weight': 1}}, 3: {0: {'weight': 1}, 1: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}}}

After 32 iterations:
template: {0: {2: {'weight': 1}, 3: {'weight': 1}}, 1: {2: {'weight': 1}, 3: {'weight': 1}}, 2: {1: {'weight': 1}, 0: {'weight': 1}, 3: {'weight': 1}}, 3: {1: {'weight': 1}, 2: {'weight': 1}, 0: {'weight': 1}}}
match:    {0: {1: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}}, 1: {0: {'weight': 1}, 2: {'weight': 1}}, 2: {0: {'weight': 1}, 1: {'weight': 1}, 3: {'weight': 1}}, 3: {0: {'weight': 1}, 2: {'weight': 1}}}