Изоморфизм графов с ограничениями на ребра с использованием networkx - PullRequest
Новая
       58

Изоморфизм графов с ограничениями на ребра с использованием networkx

1 голос
/ 25 сентября 2019

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

networkx.is_isomorphic(G1,G2, edge_match=some_callable)

, определив функцию some_callable().

Например, следующие графики являются изоморфными, поскольку вы можете перемаркировать узлы для получения друг от друга.

G1G2

А именно, relbel [2 <-> 3].

Но следующие графики не являются изоморфными.

G3G4

Невозможнополучить одно от другого, перемаркировав узлы.

Ответы [ 2 ]

2 голосов
/ 25 сентября 2019

Вот, пожалуйста.Это именно то, что делает опция edge_match.Я создам 3 графика, первые два изоморфны (хотя веса имеют разные имена - я установил функцию сравнения, чтобы учесть это).Третий не изоморфен.

import networkx as nx
G1 = nx.Graph()
G1.add_weighted_edges_from([(0,1,0), (0,2,1), (0,3,2)], weight = 'aardvark')
G2 = nx.Graph()
G2.add_weighted_edges_from([(0,1,0), (0,2,2), (0,3,1)], weight = 'baboon')
G3 = nx.Graph()
G3.add_weighted_edges_from([(0,1,0), (0,2,2), (0,3,2)], weight = 'baboon')

def comparison(D1, D2):    
    #for an edge u,v in first graph and x,y in second graph
    #this tests if the attribute 'aardvark' of edge u,v is the 
    #same as the attribute 'baboon' of edge x,y.

    return D1['aardvark'] == D2['baboon']

nx.is_isomorphic(G1, G2, edge_match = comparison)
> True
nx.is_isomorphic(G1, G3, edge_match = comparison)
> False
0 голосов
/ 25 сентября 2019

Здесь ответьте на проблему конкретно в вопросе, с теми же графиками.Обратите внимание, что я использую networkx.MultiGraph и рассмотрим некоторый «порядок» при размещении этих ребер. 

import networkx as nx

G1,G2,G3,G4=nx.MultiGraph(),nx.MultiGraph(),nx.MultiGraph(),nx.MultiGraph()

G1.add_weighted_edges_from([(0, 1, 0), (0, 2, 1), (0, 3, 2)], weight='ordering')
G2.add_weighted_edges_from([(0, 1, 0), (0, 3, 1), (0, 2, 2)], weight='ordering')                                                                            
G3.add_weighted_edges_from([(0, 1, 0), (0, 1, 1), (2, 3, 2)], weight='ordering')
G4.add_weighted_edges_from([(0, 1, 0), (2, 3, 1), (0, 1, 2)], weight='ordering')

def comparison(D1,D2):
    return D1[0]['ordering'] == D2[0]['ordering']

nx.is_isomorphic(G1,G2, edge_match=comparison)                                                                                          
>True

nx.is_isomorphic(G3,G4, edge_match=comparison)                                                                                          
>False
...