I am trying to write a function that takes a dictionary representation of a directed graph, and returns a dictionary representation of its underlying undirected graph.

For example, if the following dictionary representation of the following graph is:

d = {1 : [4],

   2 : [3],

   3 : [1, 6],

   4 : [6],

   5 : [1],

   6 : [5]} 

graph1

The dictionary representation of its underlying simple graph is:

d = {1 : [3, 4, 5],

    2 : [3],

    3 : [1, 2, 6],

    4 : [1, 6]

    5 : [1, 6],

    6 : [3, 5] } 

graph2

I am new to programming, and am kind of stuck on how to go about solving any help would be appreciated.

CodePudding user response：

To make the graph undirected, you need to add each key as value if it is not already present:

for k,l in d.items():
    for e in l:
        if k not in d[e]:
            d[e].append(k)

output:

{1: [4, 3, 5],
 2: [3],
 3: [1, 6, 2],
 4: [6, 1],
 5: [1, 6],
 6: [5, 3, 4]}