Module equivalence
[hide private]
[frames] | no frames]

Source Code for Module equivalence

  1  #todo: docstrings, comments 
  2   
  3  __all__ = ['Equivalence'] 
  4  __docformat__ = "restructuredtext en" 
  5  __author__ = 'George Sakkis <george.sakkis AT gmail DOT com>' 
  6   
  7  from collections import defaultdict 
  8   
  9   
10 -class Equivalence(object):
11 '''Representation of a general equivalence relation. 12 13 An `Equivalence` instance can be used to maintain a partition of objects 14 into equivalence sets. Two objects ``x`` and ``y`` are considered 15 equivalent either implicitly through a key function or explicitly. For the 16 implicit case, ``x`` and ``y`` are equivalent if ``key(x) == key(y)`` for 17 some provided function ``key`` (by default the identity function ``lambda x:x``). 18 For the explicit case, ``x`` and ``y`` are considered equivalent after a call 19 to `merge(x,y)`, regardless of their keys. 20 21 This class makes sure that the equivalence properties (reflexivity, symmetry, 22 transitivity) are maintained, provided that ``key(x)`` remains fixed for a 23 given object ``x`` (i.e. ``key`` is deterministic and does not depend on 24 mutable state of ``x``). 25 ''' 26
27 - def __init__(self, key=None):
28 '''Initialize a new equivalence relation. 29 30 :param key: A callable that takes a single argument and returns its 31 equivalence key (default: identity function). 32 ''' 33 self._keyfunc = key 34 # maps a member's key to its partition's key 35 self._key2pkey = {} 36 # invert mapping of self._key2pkey: 37 # maps a partition key to the set of its partition members' keys 38 self._pkey2keys = defaultdict(set) 39 # maps a partition key to the set of its members 40 self._pkey2members = defaultdict(set)
41
42 - def update(self, *objects):
43 '''Update this equivalence with the given objects.''' 44 for obj in objects: 45 self._pkey2members[self.partition_key(obj)].add(obj)
46
47 - def merge(self, *objects):
48 '''Merge all the given objects into the same equivalence set.''' 49 objects = iter(objects) 50 try: obj = objects.next() 51 except StopIteration: return 52 new_pkey = self.partition_key(obj) 53 partition_members = self._pkey2members[new_pkey] 54 partition_members.add(obj) 55 key2pkey = self._key2pkey 56 partition_keys = self._pkey2keys[new_pkey] 57 for obj in objects: 58 partition_members.add(obj) 59 old_pkey = self.partition_key(obj) 60 if old_pkey != new_pkey: 61 key2pkey[old_pkey] = new_pkey 62 partition_keys.add(old_pkey) 63 for key in self._pkey2keys.pop(old_pkey, ()): 64 key2pkey[key] = new_pkey 65 partition_keys.add(key) 66 partition_members.update(self._pkey2members.pop(old_pkey, ())) 67 if not partition_keys: # don't need to key empty sets 68 del self._pkey2members[new_pkey]
69
70 - def are_equivalent(self, *objects):
71 '''Checks whether all objects are equivalent. 72 73 An object doesn't have to be inserted first (through `update` or `merge`) 74 in order to appear as an argument. In this case, its ``key`` is used to 75 determine the partition it would belong if it was inserted. 76 77 :rtype: bool 78 ''' 79 if not objects: 80 raise ValueError('No objects given') 81 return len(set(self.partition_key(obj) for obj in objects)) == 1
82
83 - def partitions(self, objects=None):
84 '''Returns the partitioning of `objects` into equivalence groups. 85 86 :type objects: Iterable or None 87 :param objects: If not None, it must be an iterable of objects to be 88 partitioned. Otherwise, it defaults to the set of objects already 89 inserted in the equivalence (through `update` and `merge`). 90 91 :returns: A list of partitions, each partition being a list of objects. 92 :rtype: list of lists 93 ''' 94 if not objects: 95 objects = (obj for members in self._pkey2members.itervalues() 96 for obj in members) 97 key2partition = defaultdict(list) 98 for obj in objects: 99 key2partition[self.partition_key(obj)].append(obj) 100 return key2partition.values()
101
102 - def partition(self, obj):
103 '''Return the set of objects in the equivalence that are equivalent to 104 `obj`. 105 106 :rtype: set 107 ''' 108 return self._pkey2members.get(self.partition_key(obj)) or set()
109
110 - def partition_key(self, obj):
111 '''Return the key of the equivalence partition `obj` belongs to.''' 112 key = self._keyfunc(obj) if self._keyfunc else obj 113 return self._key2pkey.get(key,key)
114