Вычисление разницы между двумя графами «край мудрый» в сетиx

Question

Я хотел бы сравнить два графика с помощью networkx library. Я хочу попробовать hardcoded пример, содержащий 3 узла. Один из графиков ссылается, поэтому я хочу проверить, находится ли во втором ребра в одном и том же месте. Я думал о простом алгоритме, который вычитает контрольный граф из заданного, и если результат не пустой граф, тогда он возвращает false.

Мой код выглядит следующим образом, но он не работает:

import networkx as nx 
import matplotlib.pyplot as plt 


S=nx.DiGraph()#S-sample graph 

S.add_nodes_from([0,1,2]) 
S.add_edge(0,2) 
S.add_edge(1,2) 

nx.draw(S) 
#plt.savefig("S.png") 
#plt.show() 

R=nx.DiGraph()#R-reference graph 

R.add_nodes_from([0,1,2]) 
R.add_edge(1,2) 

nx.draw(R) 
#plt.savefig("R.png") 
#plt.show() 

def difference(S, R): 
    DIF=nx.create_empty_copy(R) 
    DIF.name="Difference of (%s and %s)"%(S.name, R.name) 
    if set(S)!=set(R): 
    raise nx.NetworkXError("Node sets of graphs is not equal") 

# if S.is_multipgraph(): 
# edges=S.edges_iter(keys=True) 
# else: 
    edges=S.edges_iter() 
    for e in edges: 
    if not R.has_edge(*e): 
     DIF.add_edge(*e) 
    return DIF 

D=difference(S, R) 
plt.show(D) 

Answer 1

Хотите вычислить график (DIF) с краями, которые находятся в вашей ссылки (R) график, но не в вашем графике ввода (S)? Или вы хотите вычислить граф с ребрами, которые отличаются между R и S? Я включил оба варианта, один из них прокомментирован.

import networkx as nx 

S = nx.DiGraph()#S-sample graph 
S.add_nodes_from([0, 1, 2]) 
S.add_edge(0, 2) 
S.add_edge(1, 2) 

R = nx.DiGraph()#R-reference graph 
R.add_nodes_from([0, 1, 2]) 
R.add_edge(1, 2) 


def difference(S, R): 
    DIF = nx.create_empty_copy(R) 
    DIF.name = "Difference of (%s and %s)" % (S.name, R.name) 
    if set(S) != set(R): 
     raise nx.NetworkXError("Node sets of graphs is not equal") 

    r_edges = set(R.edges_iter()) 
    s_edges = set(S.edges_iter()) 

    # I'm not sure what the goal is: the difference, or the edges that are in R but not in S 
    # In case it is the difference: 
    diff_edges = r_edges.symmetric_difference(s_edges) 

    # In case its the edges that are in R but not in S: 
    # diff_edges = r_edges - s_edges 

    DIF.add_edges_from(diff_edges) 

    return DIF 

print(difference(S, R).edges()) 

эта версия печатает [(0, 2)]

Как заметил @Joel, в неориентированных графах, нет никакой гарантии (по крайней мере: я не нашел его в источнике или документации), что порядок узлов будет последовательным. Если это проблема, вы можете сначала преобразовать кортежи в фризонсет, поэтому порядок не имеет значения. Вам нужно frozensets, а не наборы или списки, потому что это hashable (и что является обязательным требованием для членов набора)

set([frozenset(x) for x in S.edges()]) 

Answer 2

Простой способ написать это следующим образом (часть вашего разностного метода после raise nx.Networkx... линии

for edge in S.edges_iter(): 
     if not R.has_edge(edge[0],edge[1]): 
      DIF.add_edge(edge[0],edge[1]) 
    return DIF; 

И это график, который я имел для вашего примера:

Как упоминалось в @joel, я тестировал его для неориентированного графика, обменивая ребро [0] с краем [1], и он отлично работал.

Что касается вашего кода, я считаю, что ваша единственная проблема заключается в отображении графиков.

Первый Чтобы показать каждый график на отдельной фигуре, вы должны сделать plt.show() после каждой ничьей.

Второй В последней строке вы написали plt.show(D), которая не является правильным способом, вы должны использовать функцию отрисовки затем вызвать plt.show()

Наконец, посмотрите на drawing documentation, у вас есть другие функции отрисовки, где вы можно настроить нарисованные графики, например nx.draw_networkx_nodes узлы форма, цвет, размер ...