Попытка сгенерировать случайный граф, а затем сгенерировать еще один, пока он не изоморфен первому - PullRequest
Новая
       18

Попытка сгенерировать случайный граф, а затем сгенерировать еще один, пока он не изоморфен первому

0 голосов
/ 18 сентября 2018

Я новичок в python и пытаюсь написать программу, которая может принимать матрицу из 1 и 0 в качестве входных данных, создавать из нее граф, а затем продолжать генерировать другой случайный граф, пока он не найдет изоморфную пару.

Я продолжаю портить свою логику и продолжаю получать либо бесконечный цикл, либо цикл, который не выполняет то, что я хочу достичь. Любая помощь будет оценена.

Вот часть моей программы с вопросом 

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()

1 Ответ

0 голосов
/ 18 сентября 2018

Ваша логика программы действительно немного отключена. Вот версия, которая делает то, что я понимаю, вы хотите: 

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}
""")

Примеры прогонов: 

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}}}
...