Finding difference between two graphs-CodePudding

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)

CodePudding user response：

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': []}