networkx is_isomorphi c с учетом весов - PullRequest
Новая
       5

networkx is_isomorphi c с учетом весов

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)
    print("isomorphic? \t", str(isomorphic))
    return isomorphic


graph1 = np.array([[1, 0.5, 1.5],
                   [0, 1,   0],
                   [0, 0,   2]])

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

print(is_isomorphic(graph1,graph2))

Предположим, у меня есть два графика: graph1 с узлом 1, связанным с узлом 1 и 2, и graph2, где узел 2 связан с двумя узлами 1. Поэтому, если мы посмотрим на эти графики как на молекулы, эти два графика не изоморфны c. Теперь, когда я вызываю is_isomorphic(), это приводит к значению True, означающему, что эти два графика изоморфны c.

Как мне убедиться, что веса учитываются?

Спасибо!

Ответы [ 2 ]

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

Вы можете использовать iso.categorical_edge_match для определения функции сравнения, чтобы при проверке изоморфности обеих сетей c учитывались атрибуты ребра weight: 

G1 = nx.from_numpy_matrix(graph1)
G2 = nx.from_numpy_matrix(graph2)

Обратите внимание, что веса, в основном, просто атрибуты ребер: 

G1.edges(data=True)
# EdgeDataView([(0, 0, {'weight': 1.0}), (0, 1, {'weight': 0.5})...
G2.edges(data=True)
# EdgeDataView([(0, 0, {'weight': 1.0}), (0, 2, {'weight': 1.5})...

Итак, мы хотим определить функцию сравнения, в которой эти атрибуты сравниваются, когда iso.categorical_edge_match получает два ребра от G1 и G2: 

import networkx.algorithms.isomorphism as iso
em = iso.categorical_edge_match('weight', 'weight')

Теперь при использовании nx.is_isomorphic установите edge_match для функции сравнения em, определенной выше, с помощью iso.categorical_edge_match, чтобы она вызывалась для каждого сравниваемого ребра, чтобы проверить, их веса равны: 

nx.is_isomorphic(G1, G2, edge_match=em)
# False

Так как edge_match ожидает вызова, и мы хотим сравнивать только атрибуты, в этом случае мы также можем определить нашу собственную простую функцию сравнения так что атрибуты ребер также учитываются: 

nx.is_isomorphic(G1, G2, edge_match=lambda x,y: x['weight']==y['weight'])
# False
1 голос
/ 02 апреля 2020

В документации для nx.is_isomorphic, есть опция аргумента edge_match. Возвращает True или False в зависимости от того, хотите ли вы, чтобы края считались совпадающими:

Функция будет вызываться как edge_match (G1 [u1] [v1], G2 [u2 ] [v2]).

Вот пример: 

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