как различаются guish эквивалентных графов в сетиx - PullRequest
Новая
       11

как различаются guish эквивалентных графов в сетиx

1 голос
/ 02 апреля 2020

У меня вопрос по поводу эквивалентности графа.

Предположим, что: 

import networkx as nx
import numpy as np

def is_isomorphic(graph1, graph2):
    G1 = nx.from_numpy_matrix(graph1)
    G2 = nx.from_numpy_matrix(graph2)
    isomorphic = nx.is_isomorphic(G1,G2, edge_match=lambda x, y: x==y)
    return isomorphic


graph1 = np.array([[1, 1, 0],
                   [0, 2, 1],
                   [0, 0, 3]])
graph2 = np.array([[1, 0, 1],
                   [0, 2, 1],
                   [0, 0, 3]])

graph3 = np.array([[1, 0, 1],
                   [0, 1, 1],
                   [0, 0, 2]])
graph4 = np.array([[1, 1, 1],
                   [0, 1, 0],
                   [0, 0, 2]])

print(is_isomorphic(graph1,graph2))
# should return True
print(is_isomorphic(graph3,graph4))
# should return False

Первый is_isomorphic(graph1,graph2) должен возвращать значение True, поскольку метки вершин для меня - всего лишь фиктивные переменные. В первом случае вершина 2 связана с 2 разными вершинами; во втором случае вершина 3 связана с 2 разными вершинами.

Второй is_isomorphic(graph3,graph4) должен возвращать значение False, поскольку в graph3 вершина 2 связана с теми же двумя вершинами; и в graph4 вершина 1 связана с двумя различными типами вершин.

Есть ли способ решения этой проблемы с помощью pythoni c? Пакет networkx может быть сгенерирован, если это ускоряет вычисления, поскольку меня интересуют только матрицы смежности. Примечание: эта проблема должна быть масштабируемой и для больших матриц смежности.

1 Ответ

0 голосов
/ 02 апреля 2020

Следующие примеры подходят для ваших приведенных примеров (и, как мы надеемся, обычно делают то, что вы хотите): 

import networkx as nx
import numpy as np


def is_isomorphic(graph1, graph2):
    G1 = nx.from_numpy_matrix(graph1)
    G2 = nx.from_numpy_matrix(graph2)

    # remove selfloops (created by the calls above)
    # and add "shadow nodes" for the node types
    for node in list(G1.nodes):
        G1.remove_edge(node, node)
        G1.add_edge(node, "type" + str(graph1[node, node]))
    for node in list(G2.nodes):
        G2.remove_edge(node, node)
        G2.add_edge(node, "type" + str(graph2[node, node]))

    isomorphic = nx.is_isomorphic(G1, G2, edge_match=lambda x, y: x == y,
                                  )
    return isomorphic


graph1 = np.array([[1, 1, 0],
                   [0, 2, 1],
                   [0, 0, 3]])
graph2 = np.array([[1, 0, 1],
                   [0, 2, 1],
                   [0, 0, 3]])

graph3 = np.array([[1, 0, 1],
                   [0, 1, 1],
                   [0, 0, 2]])
graph4 = np.array([[1, 1, 1],
                   [0, 1, 0],
                   [0, 0, 2]])

print(is_isomorphic(graph1, graph2))
# True
print(is_isomorphic(graph3, graph4))
# False
...