Nik.Birur Nik.Birur - 1 year ago 86
Python Question

Adding a sorted tuple to a dictionary as a key

I am very new to Python and i am trying my best to learn Python. I have been trying to implement a community detection algorithm that i came across and i would really appreciate if i could get help from anyone here.

I have a defaultdict(list), my input, which looks like :

input = [('B', ['D']), ('D', ['E']), ('F', ['E']), ('G', ['D', 'F'])]

Here, 'B', 'D', 'E' etc represent nodes in a tree. The key in the dictionary represents children nodes and the value represents parent nodes. So in the above input, 'B' is a child of 'D', 'D' is a child of 'E' etc.

I am trying to create a dictionary with tuples(in sorted order) as keys and int as values. The expected output is:

output = [(('A', 'B'), 1.0), (('B', 'C'), 1.0), (('B', 'D'), 3.0), (('D', 'E'), 4.5), (('D', 'G'), 0.5), (('E', 'F'), 1.5), (('F', 'G'), 0.5)]

In the above output, the key is a tuple which represents an edge in the input. For ex : ('A' , 'B') represents an edge between A and B and the int value is something that i calculate.

I would love to know know how this can be done.

I have tried the following:


edges = []
for node,parents in input.items():
for p in sorted(parents):
tup = (node,p)
tup = sorted(tup)
/*output of the above line: [['E', 'F'], ['D', 'E'], ['A', 'B'], ['B', 'C'], ['B', 'D'], ['D', 'G'], ['F', 'G']]*/

And then i thought i will pull values from this list to a dict. Obviously, i got a dict with key of type List and further the items in list were not sorted.


edges = {}

for node,parents in node2parents.items():
for p in sorted(parents):
t = (node,p)
t = sorted(t)
edges[t] = 0

On executing the above, i got a TypeError: unhashable type: 'list'

I have tried few other ways, but none proved to be successful. It would be great if someone could help me learn how i could do this.

PS : I would have posted evidences of more "failed" efforts of mine, but i dint want to waste your time by making you go through all the stupid ways i have been trying to accomplish my goals. Also, i googled and tried if i could find an answer to my question. Though there were countless possible solutions, i still failed to implement the logic successfully. I am honestly trying to learn Python and it would be great if you could push me in the right direction.

Answer Source

sorted returns a new sorted list, regardless of the input's type. If you want the result to be a sorted tuple, just wrap the sorted call in the tuple constructor:

t = tuple(sorted(t))

For Python built-in types, only immutable types (e.g. int, str, or tuples and frozensets containing only other immutable types) are suitable for use as keys in dicts and values in set/frozensets, which is why preserving the tuple type is important; list is mutable, and to avoid a sticky situation where a mutable object like a list is added to a dict, then changed (so suddenly the hash and equality comparisons for it don't correspond to where it was bucketed), rendering it unfindable and violating the dict assumptions, they prohibit using mutable built-in types completely.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download