Python, TypeError: unhashable type: 'list'

Question

i'm reciving the following error in my program: Traceback:

Traceback (most recent call last): File "C:\Python33\Archive\PythonGrafos\Alpha.py", line 126, in <module> menugrafos() File "C:\Python33\Archive\PythonGrafos\Alpha.py", line 97, in menugrafos zetta = Beta.caminhografo(grafo,va,vb) File "C:\Python33\Archive\PythonGrafos\Beta.py", line 129, in caminhografo if ([vo, a]) in vat == ([vo,vq]) in vat: TypeError: unhashable type: 'list' 

The program is meant to do an adjacency list which works fine and then proceed to search if there is a path between vertex va and vb. I used a dictionary of lists in collection/defaultdict so i can properly append adjacent vertex.

The problem is in the if clauses after the list is created at the end of the program. I can't find a way to properly use the if clauses with the dict to find if there is a valid path between vertex. Also grafo is a graph class.

Here is the code:

class graph:     v = 0     a = 0     node = []  class vertex:     ta = []     adj = {}  def caminhografo(grafo, va, vb):     vat = defaultdict(list)     i = 0     a = 0     z = 0     vo = int(va)     vq = int(vb)     vz = int(va)     vw = int(vb)     x = len(grafo.node)     if vz < vw:         for vz in range (vw+1):             a = 0             x = len(grafo.node)             for a in range (x):                 if [int(vz),int(a)] in grafo.node:                     vat[vz].append(a)                        if vz > vw:         while vz > vw:             a = 0             x = len(grafo.node)             for a in range (x):                 if[int(va),int(a)] in grafo.node:                     vat[vz].append(a)             vz = vz - 1     a = 0     x = len(grafo.node)     print(vat)     for a in range (x):        if ([vo, a]) in vat == ([vo,vq]) in vat:            print("""     ==============================================                Existe Caminho     ==============================================     """)            break        elif ([vo,a]) in vat:            vo = a        else:                       print("""     ==============================================              Não Existe Caminho     ==============================================         """)            break 

Thanks for any assistance.

Answer 1

The problem is that you can't use a list as the key in a dict, since dict keys need to be immutable. Use a tuple instead.

This is a list:

[x, y] 

This is a tuple:

(x, y) 

Note that in most cases, the ( and ) are optional, since , is what actually defines a tuple (as long as it's not surrounded by [] or {}, or used as a function argument).

You might find the section on tuples in the Python tutorial useful:

Though tuples may seem similar to lists, they are often used in different situations and for different purposes. Tuples are immutable, and usually contain an heterogeneous sequence of elements that are accessed via unpacking (see later in this section) or indexing (or even by attribute in the case of namedtuples). Lists are mutable, and their elements are usually homogeneous and are accessed by iterating over the list.

And in the section on dictionaries:

Unlike sequences, which are indexed by a range of numbers, dictionaries are indexed by keys, which can be any immutable type; strings and numbers can always be keys. Tuples can be used as keys if they contain only strings, numbers, or tuples; if a tuple contains any mutable object either directly or indirectly, it cannot be used as a key. You can’t use lists as keys, since lists can be modified in place using index assignments, slice assignments, or methods like append() and extend().

---

In case you're wondering what the error message means, it's complaining because there's no built-in hash function for lists (by design), and dictionaries are implemented as hash tables.