Finding difference between two graphs

Question

I'm solving a sub-problem of mine using a graph data structure. I have implemented it using dictionaries with vertex as keys and edges as a list of nodes. Example:

graph1 = {'1': ['3'],'2': [],'3': ['1', '7'],'7':['3']}

I want to compare two graphs i.e., the above graph with:

graph2 = {'1': ['3'],'2': ['3'],'3': ['1', '2'],'7':[]}

The above two graphs are different in terms of edges.

I want the difference information of these two graphs like:

graph1-graph2 = {'2':[],'3':['1','7'],'7':['3']}
graph2-graph1 = {'2':['3'],'3':['1','2'],'7':[]}

In short, I'm looking for a symmetric difference between graph1 and graph2.

I tried getting set difference as suggested in this link. But since the values are lists, I'm getting the error TypeError: unhashable type: 'list'. I understand that this is because the set is immutable and the list is a mutable data structure. And the type conversion is generating an error.

I also tried using dataframe difference like given in the this link, I'm getting the same Type error as the above.

Is there a simple way of getting the solution? Any help is appreciated. Thanks in advance :)

PS: I want to keep my graph implementation simple. Hence, I'm not using any advanced libraries like networkx.

Edit 1: Please note, I wanted the results that somewhat resembles the results of symmetric difference of a set and not exactly the symmetric difference.

Using the results, I want to understand which all nodes are different in both the graphs. The results should contain the nodes whose edge list is different in both the graphs. Like:

'2' : [] (graph1)
'2' : ['3'] (graph2)

and

'3' : ['1','7'] (graph1)
'3' : ['1','2'] (graph2)

Why does `2` occur in the first difference, but `1` doesn't? — user2390182, Oct 18 '21 at 07:30
@DaniMesejo -I also want information about the nodes that have different edges. In graph1, '3' is connected to '1' and '7' while in graph2 it is connected to '1' and '2'. I wanted to highlight this. — Suneha K S, Oct 18 '21 at 07:32
@j1-lee - Right, I wanted symmetric difference-kind of results — Suneha K S, Oct 18 '21 at 07:33
@user2390182 - '1' has the same edge list in both the graphs i.e., it is connected to '3' in both the graphs. I want only the nodes that have different connections in both graphs. — Suneha K S, Oct 18 '21 at 07:35
So the actual expected result should be the nodes 2 and 3 with the symmetric difference of each list right? for instance something like [7, 2] for node 3? — Dani Mesejo, Oct 18 '21 at 07:46
@DaniMesejo - I wanted the entire edge list. I also want the edge that is common along with the new ones. — Suneha K S, Oct 18 '21 at 07:49

score 1 · Accepted Answer · answered Oct 18 '21 at 07:34

You could use the following:

NB. this assumes the dictionaries have the same keys (if not, please make the desired output explicit

graph1_2 = {}
graph2_1 = {}

for key in graph1:
    s1 = set(graph1[key])
    s2 = set(graph2[key])
    if s1 == s2:
        continue
    else:
        graph1_2[key] = graph1[key]
        graph2_1[key] = graph2[key]

output:

>>> graph1_2
{'2': [], '3': ['1', '7'], '7': ['3']}

>>> graph2_1
{'2': ['3'], '3': ['1', '2'], '7': []}

Finding difference between two graphs

1 Answers1