Computing the Difference between two graphs 'edge wise' in networkx

Question

I would like to compare two graphs using networkx library. I want to try on hardcoded example containing 3 nodes. One of the graphs is referenced so I want to check if in the second one the edges are in the same place. I was thinking about simple algorithm which will subtract reference graph from a given one and if the result is not an empty graph then it returns false.

My code is as follows but it is not working:

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

Do you want to compute a graph (DIF) with the edges that are in your reference (R) graph, but not in your input graph (S)? Or do you want to calculate a graph with the edges that are different between R and S? I included both options, one is commented out.

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

this version prints [(0, 2)]

As @Joel noticed, in undirected Graphs, there is no guaranty (at least: I did not find it in the source or the documentation) that the order of the nodes will be consistent. If that is an issue, you could convert the tuples into frozensets first, so the order does not matter. You need frozensets, and not sets or lists, because these are hashable (and that is a requirement for members of a set)

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

Answer 2

A simple way to write it is as follows (The part of your difference method after the raise nx.Networkx... line

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

And this is the graph I had for your example:

As mentioned by @joel I tested it for undirected graph by exchanging edge[0] with edge[1] and it worked fine.

As for your code I believe your only problem is in displaying the graphs.

First To show each graph in a separate figure you have to do plt.show() after each draw.

Second In the last line you wrote plt.show(D) which is not the right way, you have to use draw function then call plt.show()

Finally, have a look on the drawing documentation, you have other draw functions where you can customize the drawn graphs e.g. nx.draw_networkx_nodes nodes shape, color, size ...