How to separate a list into dictionary based on first and second values

Question

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 :)

No, they don't have to be. They're just used as a way to tell which edges neighbour each other. — Johnathan Scott, Mar 01 '17 at 20:06
If the order doesn't matter, this is easiest using `set`s instead of `list`s in the dict. — Peter DeGlopper, Mar 01 '17 at 20:08

TemporalWolf · Accepted Answer · 2017-03-01T20:17:19.767

2

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)

edited Mar 01 '17 at 20:17

answered Mar 01 '17 at 20:11

TemporalWolf

7,727
1
30
50

Thank you! absolutely the right thing I was looking for :) – Johnathan Scott Mar 01 '17 at 20:11
This is not exactly wrong but I rarely see EAFP applied to dict membership. `defaultdict` is the idiomatic way to solve this, or `setdefault` on versions of python too early to have `defaultdict`. – Peter DeGlopper Mar 01 '17 at 20:13
@PeterDeGlopper I added that option, as it is faster in all cases. I tend to not import defaultdict unless I need the extra speed, but YMMV. – TemporalWolf Mar 01 '17 at 20:19

score 1 · Answer 2 · answered Mar 01 '17 at 20:08

1

>>> l = [('A','B'),('A','C'),('A','D'),('B','C'),('C','D')]
>>> 
>>> d = {}
>>> for i in l:
...     temp = d.get(i[0], [])
...     temp.append(i[1])
...     d[i[0]] = temp

answered Mar 01 '17 at 20:08

Mayank

5,411
1
16
16

This is close to right, but does't create the reciprocal relationships - OP's example shows `'B': ['A', 'C']` despite not having an explicit `('B', 'A')` tuple because there is a `('A', 'B')` tuple. Also, I would use `collections.defaultdict(list)` - or better `defaultdict(set)` given that order does not matter. – Peter DeGlopper Mar 01 '17 at 20:10

score 1 · Answer 3 · answered Mar 01 '17 at 20:10

1

Why not create a list, and add every element to it?

neighbours = {}
myList = [('A','B'),('A','C'),('A','D'),('B','C'),('C','D')]
for i in myList:
    if i[0] not in neighbours:
        neighbours[i[0]]= list()
    neighbours[i[0]].append(i[1])

print(neighbours)

Edit: resuls in:

{'B': ['C'], 'A': ['B', 'C', 'D'], 'C': ['D']}

answered Mar 01 '17 at 20:10

rmeertens

4,383
3
17
42

This is a good start for me, but what I'm really after is having each Key show its neighbour as a key e.g. `{'A': ['B','C','D'], 'B': ['A','C'], 'C': ['A','B','D'], 'D': ['A','C']}` – Johnathan Scott Mar 01 '17 at 20:12

How to separate a list into dictionary based on first and second values

3 Answers3