Menu
I am trying to find the union of set of sets. Specifically I want the union of the list of nodes for each key in the dictionary of networkx graphs called periodic_gs. I would like to use the reduce function as it seems reasonable to take the union of all periodic_gs[x].nodes() where x is a key of periodic_gs.
Here is my attempt:
reduce(lambda x,y: set(periodic_gs[x].nodes()).union(set(periodic_gs[y].nodes())), periodic_gs.keys(), {})
To me, this says take the union of the nodes across each graph in the dictionary. For some reason, python tells me: TypeError: unhashable type: 'dict' I do not see this TypeError, because periodic_gs.keys() is a list of the keys (they are strings but I do not see how this would matter), and when substituted in for the arguments to the lambda function will work.
What is causing the type error and how do I fix it?
619
In Python, to union two or more sets, you use the union() method: new_set = set.
Python's reduce() is a function that implements a mathematical technique called folding or reduction. reduce() is useful when you need to apply a function to an iterable and reduce it to a single cumulative value.
The most efficient way to join multiple sets (stored in a list of sets), use the Python one-liner set(). union(*list) that creates a new set object, calls the union() method on the new object, and unpacks all sets from the list of sets into the union() method's argument list.
Python offers a function called reduce() that allows you to reduce a list in a more concise way. The reduce() function applies the fn function of two arguments cumulatively to the items of the list, from left to right, to reduce the list into a single value.
You can use set.union like this:
>>> lis = [{1, 2, 3, 4}, {3, 4, 5}, {7, 3, 6}]
>>> set().union(*lis)
set([1, 2, 3, 4, 5, 6, 7])
It's possible to do this using reduce, but don't:
>>> reduce(set.union, lis)
set([1, 2, 3, 4, 5, 6, 7])
because this reduce takes quadratic time due to all the intermediate sets it builds and discards:
In [1]: from functools import reduce
In [2]: sets = [{x} for x in range(1000)]
In [3]: %timeit set().union(*sets)
40.9 µs ± 1.43 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [4]: %timeit reduce(set.union, sets)
4.09 ms ± 587 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
That's a 100x slowdown on this test case, and it can easily be even worse.
For your code, this should do it:
set().union(*(x.nodes() for x in periodic_gs.values()))
{} is an empty dictionary, not a set. Use set() to create an empty set.
However, I think you are misinterpreting how reduce() works here; x is the previous return value of the lambda, and y is the next value from the sequence. Because you return a set, x is always a set here, and you cannot use that as a key to periodic_gs.
If you want the union of all nodes in the graph, use itertools.chain.from_iterable() and set():
from itertools import chain
set(chain.from_iterable(periodic_gs[key].nodes() for key in periodic_gs))
This creates one set from each of the nodes() calls.
To use reduce() you'd have to take into account that the first argument is always a set:
reduce(lambda res, key: res.union(periodic_gs[key].nodes()), periodic_gs, set())
I am assuming here that periodic_gs is iterable (yielding keys) just like a regular dictionary; if not, use periodic_gs.keys().
A quick demo with a regular dictionary:
>>> example = {'foo': [1,2,3], 'bar': [3, 4, 1]}
>>> reduce(lambda res, key: res.union(example[key]), example, set())
set([1, 2, 3, 4])
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
