Python: TypeError: Unhashable Type: List

Question

I have a code that basically tests which circles in a random distribution of circles in a box touch - touching circles are added to a dictionary as clusters. I keep getting a TypeError when I run this code:

leftedge = 0
rightedge = 1
result = []
color = {}
parent = {}
clusters = {}
number = 0

def bfs(vertices, neighbours, source) :

    global number
    number +=1
    clusters[number] = set()
    color[source] = 'g'
    q = []

    q.append(source)

    while q != [] :
        v = q.pop(0)


        for v2 in neighbours[v] :
            if color[v2] == 'w' :
                 color[v2] = 'g'
                 parent[v2] = v
                 q.append(v2)
            color[v] = 'b'
            clusters[number].add(v)


def createclusters(vertices, neighbours) :

    for v in vertices :
        color[v] = 'w'
        parent[v] = -1

    while 'w' in color.values() :
            for v in color.keys() :
                if color[v] == 'w' :
                    bfs(vertices, neighbours, v)


def overlap(c1,c2,r) :
    if ((c1[0]-c2[0])**2 +(c1[0]-c2[0])**2)**0.5 > 2*radius :
         return 0
    return 1

def findclusters(array, radius) :
    d={}

    for c1 in array :
        d[c1]=[]
        for c2 in array :
            if overlap(c1, c2, radius) :
            d[c1].append(c2)

    createclusters(array,d)

    for cluster in clusters.values() :
        l = [i[0] for i in cluster]
        left = right = False

        x = max(l) 
        if x + radius > rightedge :
            right = True
        x = min(l)
        if x - radius < leftedge :
            left = True

        result.append((cluster,left,right))



import numpy.random as nr

array = nr.uniform(size=(10,2)).tolist
radius = 0.1

findclusters(array, radius)

print(clusters)

print(result)

When I try and run it, I get this error:

TypeError                                 Traceback (most recent call last)
/Users/annikamonari/<ipython-input-316-be6c65f2ce89> in <module>()
----> 1 findclusters(array,0.1)

/Users/annikamonari/<ipython-input-309-32f214b46080> in findclusters(array, radius)
      2     d={}
      3     for c1 in array:
----> 4         d[c1]=[]
      5         for c2 in array:
      6             if overlap(c1,c2,radius):

TypeError: unhashable type: 'list'

For the life of me, can't figure out why. Can anyone figure it out?

Thank you!

Answer 1

As the program expects array to be a list of 2d hashable types (2d tuples), its best if you convert array to that form, before calling any function on it.

temp = nr.uniform(size=(10,2)).tolist()

array = [tuple(i) for i in temp]

This should create the input in the required format.

Answer 2

First, you probably need to call .tolist() rather than leaving off the parens.

---

Also, array is a 2-dimensional array, which means that when you do...

for c1 in array:
    d[c1]=[]

...c1 is a list. Lists, being mutable, are not a hashable type (because if they were, the hash could change at any time based on the contents changing, and hash-based data structures aren't designed to handle that) and thus can't be used as a dictionary key.

If you intended to use a sequence of values as a dictionary key, you need to make them non-mutable (and thus hashable) first. The easiest way to do this is by converting to a tuple:

for c1 in array:
    d[tuple(c1)]=[]

However, from reading your code, it seems more like you might be wanting to just iterate over the indices of the first array, which means you probably want something like...

for index, values in enumerate(array):
    d[index] = []
    for c2 in values:
        # ...

or similar.

Answer 3

You don't actually call the tolist method in your code, you just pass the function itself.

Add the () to call it:

array = nr.uniform(size=(10,2)).tolist()

Notice that c2 in your code is a list of two numbers, it's not a single number.