I wasn't sure exactly how to word my question, so I'll go into more depth here.
What I'm trying to do is perform the Graph Coloring problem in Python using input of a list such as this:
[('A','B'),('A','C'),('A','D'),('B','C'),('C','D')]
This is meant to denote the "neighbors" of each edge of the graph, such that A is the neighbor of B C & D, B is the neighbor of C, and C is the neighbor of D
Now, what I'm trying to do is break these into keys in a dictionary like this:
neighbors = {}
neighbors['A'] = ['B', 'C', 'D']
neighbors['B'] = ['A', 'C']
neighbors['C'] = ['A', 'B', 'D']
neighbors['D'] = ['A', 'C']
The issue I'm having is breaking down the initial input into this multi value per key dictionary. So far I have this:
neighbours = {}
myList = [('A','B'),('A','C'),('A','D'),('B','C'),('C','D')]
for i in myList:
neighbours[i[0]] = (i[1])
print(neighbours)
This provides the output:
{'A': 'D', 'C': 'D', 'B': 'C'}
But I'd like to have it look like this:
{'A': ['B','C','D'], 'B': ['A','C'], 'C': ['A','B','D'], 'D': ['A','C']}
Any help is greatly appreciated! Thanks :)
The straight forward, EAFP approach:
adj = [('A','B'),('A','C'),('A','D'),('B','C'),('C','D')]
mat = {}
for (x, y) in adj:
try:
mat[x].append(y)
except KeyError:
mat[x] = [y]
try:
mat[y].append(x)
except KeyError:
mat[y] = [x]
>>> mat
{'A': ['B', 'C', 'D'], 'C': ['A', 'B', 'D'], 'B': ['A', 'C'], 'D': ['A', 'C']}
Or, if you prefer, the default dict:
from collections import defaultdict
default = defaultdict(list)
for (x, y) in adj:
default[x].append(y)
default[y].append(x)
>>> default
defaultdict(<type 'list'>, {'A': ['B', 'C', 'D'], 'C': ['A', 'B', 'D'], 'B': ['A', 'C'], 'D': ['A', 'C']})
Which is 10-20% faster, if you're interested in performance. (see this repl.it comparison)