teamwork.math.KeyedMatrix

20 """A dictionary-based representation of a two-dimensional matrix 21 @cvar defaultValue: the default value to insert into any missing positions 22 @type defaultValue: C{float} 23 @ivar _array: The numeric representation of this matrix 24 @ivar _fresh: flag indicating whether there have been any changes to the array contents since the last update to the numeric array 25 @type _fresh: C{boolean} 26 @ivar _frozen: flag indicating whether the dimensions of this matrix are subject to change 27 @type _frozen: C{boolean} 28 @ivar _rowKeys: an ordered list of the indices of the rows of this matrix 29 @type _rowKeys: L{Key}[] 30 @ivar _rowOrder: a dictionary containing the row position of each key within the matrix 31 @type _rowOrder: L{dict}(L{Key}:C{int}) 32 @warning: Use the L{set} method to set individual values. Using built-in assignment calls (e.g., M[row][col] = 0.) will lead to inconsistencies. If you can think of a clever way to enforce this in code, please feel free to do so. 33 """ 34 defaultValue = 0. 35 dimension = 2

36 - def __init__(self,args={}):

37 dict.__init__(self) 38 self._fresh = False 39 self._frozen = False 40 self._rowOrder = {} 41 if len(args) > 0: 42 # Grab all the row keys 43 self._rowKeys = args.keys() 44 self._rowKeys.sort() 45 for index in range(len(args)): 46 # Set all the row indices 47 key = self._rowKeys[index] 48 self._rowOrder[key] = index 49 # Extract values 50 values = [] 51 for rowKey in self._rowKeys: 52 row = args[rowKey] 53 dict.__setitem__(self,rowKey,row) 54 rowValues = [] 55 for colKey in row.keys(): 56 try: 57 rowValues.append(args[rowKey][colKey]) 58 except KeyError: 59 rowValues.append(self.defaultValue) 60 values.append(rowValues) 61 self._array = array(values) 62 else: 63 self._rowKeys = [] 64 self._array = None

65

66 - def rowKeys(self):

67 """ 68 @return: ordered list of the keys to all rows in this matrix 69 @rtype: L{Key}[] 70 """ 71 return self._rowKeys

72

73 - def colKeys(self):

74 """ 75 @return: ordered list of the keys to all columns in this matrix 76 @rtype: L{Key}[] 77 """ 78 if len(self) == 0: 79 return [] 80 else: 81 return self.values()[0].keys()

82

83 - def colOrder(self,key):

84 """ 85 @return: the position of the given key within the columns of this matrix 86 @rtype: int 87 """ 88 if len(self) == 0: 89 raise ValueError,'No column %s in this matrix' % (str(key)) 90 else: 91 try: 92 return self.values()[0]._order[key] 93 except KeyError: 94 raise ValueError,'No column %s in this matrix' % (str(key))

95

96 - def set(self,row,col,value):

97 """Sets an individual value in this matrix 98 @param row,col: the keys for this value's position 99 @type row,col: L{Key} 100 @param value: the value to insert 101 @type value: C{float} 102 """ 103 self._fresh = False 104 ## self.addColumns([col]) 105 if not self._rowOrder.has_key(row): 106 self.addRows([row]) 107 self[row][col] = value

108

109 - def rowPosition(self,key):

110 """Finds the row position where this key should be inserted 111 @param key: the key to insert 112 @type key: L{Key} 113 @return: the index to insert at 114 @rtype: C{int} 115 @warning: does not check whether key is already present 116 """ 117 # Find the position for this key 118 for index in range(len(self._rowOrder)): 119 if key < self.rowKeys()[index]: 120 break 121 else: 122 index = len(self._rowOrder) 123 return index

124

125 - def addRows(self,keys,value=None):

126 """Adds a new row slot to this matrix 127 @param keys: the (sorted) keys for the new slots to insert 128 @type keys: L{Key}[] 129 @param value: the row to insert (defaults to a row of L{defaultValue}) 130 @type value: C{float} 131 @warning: assumes that this row does not already exist 132 """ 133 if self._frozen: 134 raise UserWarning,'You are modifying a frozen matrix' 135 self._fresh = False 136 # Initialize values and find out which keys are missing 137 newKeys = [] 138 newValues = {} 139 for key in keys: 140 if not self.has_key(key): 141 newKeys.append(key) 142 if value is None: 143 newValues[key] = KeyedVector() 144 elif isinstance(value,KeyedVector): 145 if len(keys) > 1: 146 newValues[key] = copy.copy(value) 147 else: 148 newValues[key] = value 149 elif isinstance(value,dict): 150 try: 151 newValues[key] = value[key] 152 except KeyError: 153 newValues[key] = KeyedVector() 154 else: 155 # Can't really put anything else in here 156 newValues[key] = KeyedVector() 157 # Nothing to do if there are no missing rows 158 if len(newKeys) == 0: 159 return 160 # OK, let's build ourselves a new matrix 161 finalOrder = {} # The key order for the resulting matrix 162 finalKeys = [] # The ordered key list for the resulting matrix 163 finalArray = [] # The ordered value list for the resulting matrix 164 oldIndex = 0 # The pointer to the next old key to copy 165 newIndex = 0 # The pointer to the next new key to insert 166 # Insert all the new keys 167 while newIndex < len(newKeys): 168 # Insert all the old keys that come before this new key 169 newKey = newKeys[newIndex] 170 while oldIndex < len(self._rowKeys) and \ 171 self._rowKeys[oldIndex] < newKey: 172 # Copy an old key 173 key = self._rowKeys[oldIndex] 174 finalOrder[key] = len(finalKeys) 175 finalKeys.append(key) 176 oldIndex += 1 177 # Copy the new key 178 finalOrder[newKey] = len(finalKeys) 179 finalKeys.append(newKey) 180 dict.__setitem__(self,newKey,newValues[newKey]) 181 newIndex += 1 182 while oldIndex < len(self._rowKeys): 183 # Copy an old key 184 key = self._rowKeys[oldIndex] 185 finalOrder[key] = len(finalKeys) 186 finalKeys.append(key) 187 oldIndex += 1 188 # Set the final results 189 self._rowOrder = finalOrder 190 self._rowKeys = finalKeys

191

192 - def isIdentity(self):

193 """ 194 @return: C{True} iff this matrix is an identity matrix 195 @rtype: boolean 196 """ 197 for key in self.rowKeys(): 198 row = self[key] 199 if not isinstance(row,UnchangedRow) or row.sourceKey != key: 200 break 201 else: 202 return True 203 return False

204

205 - def addColumns(self,keys,value=None):

206 """Adds new column slots to this matrix 207 @param keys: the (sorted) keys for the new slots to insert 208 @type keys: L{Key}[] 209 @param value: the column to insert (defaults to a row of L{defaultValue}) 210 @type value: C{float} 211 """ 212 if self._frozen: 213 raise UserWarning,'You are modifying a frozen matrix' 214 self._fresh = False 215 if value is None: 216 value = self.defaultValue 217 for row in self.values(): 218 row.addColumns(keys,value)

219

220 - def getArray(self):

221 """ 222 @return: the numeric array representation of this matrix 223 @rtype: C{array} 224 """ 225 if not self._fresh: 226 rowValues = map(lambda k:self[k].getArray(),self.rowKeys()) 227 self._array = array(rowValues) 228 self._fresh = True 229 return self._array

230

231 - def __setitem__(self,key,value):

232 """@type key: L{Key} instance 233 @type value: C{KeyedVector}""" 234 assert(isinstance(value,KeyedVector)) 235 # Add any new keys from this new row 236 self.addColumns(value.keys()) 237 # Add any missing keys in this new row 238 value.addColumns(self.colKeys(),self.defaultValue) 239 if self._rowOrder.has_key(key): 240 self._fresh = False 241 matrix = self.getArray() 242 matrix[self._rowOrder[key]] = value.getArray() 243 dict.__setitem__(self,key,value) 244 else: 245 self.addRows([key],value)

246

247 - def __delitem__(self,key):

248 if self._frozen: 249 raise UserWarning,'You are modifying a frozen matrix' 250 self._fresh = False 251 index = self._rowOrder[key] 252 del self._rowOrder[key] 253 for other in self._rowKeys[index+1:]: 254 self._rowOrder[other] -= 1 255 self._rowKeys.remove(key) 256 dict.__delitem__(self,key)

257 258

259 - def deleteColumn(self,key):

260 """Removes the specified column from the matrix 261 @param key: the index for the column to remove 262 @type key: L{Key} 263 """ 264 if self._frozen: 265 raise UserWarning,'You are modifying a frozen matrix' 266 self._fresh = False 267 for row in self.values(): 268 del row[key]

269

270 - def fill(self,keys,value=None):

271 """Fills in any missing rows and columns with a default value 272 @param keys: the new slots that should be filled 273 @type keys: list of L{Key} instances 274 @param value: the default value (default is L{defaultValue}) 275 @note: does not overwrite existing values, but does fill in values for missing existing keys 276 """ 277 self.addRows(keys,value) 278 self.addColumns(keys,value)

279

280 - def freeze(self):

281 """Locks in the dimensions and keys of this matrix""" 282 self._frozen = True 283 for row in self.values(): 284 row.freeze()

285

286 - def unfreeze(self):

287 """Unlocks the dimensions and keys of this matrix""" 288 self._rowOrder = copy.copy(self._rowOrder) 289 self._rowKeys = copy.copy(self._rowKeys) 290 for row in self.values(): 291 row.unfreeze() 292 self._frozen = False

293

294 - def compose(self,other,op):

295 """Composes the two matrices together using the given operator 296 @param other: the other matrix to compose with 297 @type other: L{KeyedMatrix},float 298 @param op: the operator used to generate the new array values 299 @type op: C{lambda x,y:f(x,y)} where C{x} and C{y} are C{array} instances 300 @rtype: a new L{KeyedMatrix} instance""" 301 if isinstance(other,float): 302 return self.copyFromArray(op(self.getArray(),other)) 303 else: 304 return self.copyFromArray(op(self.getArray(),other.getArray()))

305

306 - def __add__(self,other):

307 return self.compose(other,lambda x,y:x+y)

308

309 - def __sub__(self,other):

310 return self + (-other)

311

312 - def __neg__(self):

313 result = self.__class__() 314 result._array = -(self.getArray()) 315 result._rowOrder = self._rowOrder 316 result._rowKeys = self._rowKeys 317 for key,row in self.items(): 318 dict.__setitem__(result,key,-row) 319 if self._frozen: 320 result.freeze() 321 else: 322 result.unfreeze() 323 return result

324

325 - def __mul__(self,other):

326 if isinstance(other,KeyedMatrix): 327 return self._multiplyByMatrix(other) 328 elif isinstance(other,KeyedVector): 329 return self._multiplyByVector(other) 330 else: 331 return self._multiplyByOther(other)

332

333 - def _multiplyByMatrix(self,other):

334 """Handles multiplication when multiplicand is two-dimensional 335 @type other: L{KeyedMatrix}""" 336 return self.copyFromArray(matrixmultiply(self.getArray(), 337 other.getArray()))

338

339 - def _multiplyByVector(self,other):

340 """Handles multiplication when multiplicand is one-dimensional 341 @type other: L{KeyedVector}""" 342 result = KeyedVector() 343 try: 344 result._array = matrixmultiply(self.getArray(),other.getArray()) 345 except ValueError,e: 346 raise UserWarning,'Your matrices are not aligned; perhaps use fill method to align' 347 result._order = self._rowOrder 348 result._orderedKeys = self._rowKeys 349 result._fresh = None 350 result._updateString() 351 if self._frozen: 352 result.freeze() 353 else: 354 result.unfreeze() 355 return result

356

357 - def _multiplyByOther(self,other):

358 """Handles multiplication when multiplicand is something unknown class (typically, C{float}) 359 """ 360 return self.copyFromArray(self.getArray() * other)

361

362 - def copyFromArray(self,matrix):

363 """Copies all aspects of this array (keys, etc.) except for the numerical value, which is taken fom the given matrix 364 @param matrix: the numerical value to use 365 @type matrix: array 366 @rtype: L{KeyedMatrix} 367 """ 368 result = KeyedMatrix() 369 result._array = matrix 370 result._rowKeys = self._rowKeys 371 result._rowOrder = self._rowOrder 372 for rowKey,oldRow in self.items(): 373 row = KeyedVector() 374 row._orderedKeys = oldRow._orderedKeys 375 row._order = oldRow._order 376 row._array = result._array[self._rowOrder[rowKey]] 377 dict.__setitem__(result,rowKey,row) 378 if self._frozen: 379 result.freeze() 380 else: 381 result.unfreeze() 382 return result

383

384 - def inverse(self):

385 from numpy.linalg.linalg import inv 386 return self.copyFromArray(inv(self.getArray()))

387

388 - def __hash__(self):

389 """@warning: This is not cached, so repeated hashing may be inefficient""" 390 return hash(str(self))

391

392 - def merge(self,other):

393 """Merges rows from the two matrices (if any row keys are common, then the new row is used) 394 @param other: the matrix to merge 395 @type other: L{KeyedMatrix} instance 396 @return: The new matrix 397 @rtype: L{KeyedMatrix} 398 """ 399 result = copy.copy(self) 400 result.addRows(other.rowKeys(),other) 401 return result

402

403 - def instantiate(self,table):

404 """Substitutes values for any abstract references, using the 405 given substitution table 406 @param table: dictionary of key-value pairs, where the value will be substituted for any appearance of the given key in a field of this L{Key} object 407 @type table: dictionary""" 408 # Figure out all of the new key/row pairs 409 newValues = {} 410 for key,value in self.items(): 411 row = value.instantiate(table) 412 newKey = key.instantiate(table) 413 if isinstance(newKey,list): 414 keyList = newKey 415 elif newKey == keyDelete: 416 keyList = [] 417 else: 418 keyList = [newKey] 419 for newKey in keyList: 420 try: 421 newValues[newKey] += row 422 except KeyError: 423 newValues[newKey] = row 424 return KeyedMatrix(newValues)

425

426 - def instantiateKeys(self,table):

427 """Substitutes values for any abstract references, using the 428 given substitution table 429 @param table: dictionary of key-value pairs, where the value will be substituted for any appearance of the given key in a field of this L{Key} object 430 @type table: dictionary""" 431 # Figure out all of the new key/row pairs 432 newValues = {} 433 for key,value in self.items(): 434 value.instantiateKeys(table) 435 newKey = key.instantiate(table) 436 if isinstance(newKey,list): 437 keyList = newKey 438 elif newKey == keyDelete: 439 keyList = [] 440 else: 441 keyList = [newKey] 442 for newKey in keyList: 443 try: 444 newValues[newKey] += value 445 except KeyError: 446 newValues[newKey] = value 447 dict.__delitem__(self,key) 448 # Set up my new keys and values 449 self._rowOrder.clear() 450 self._rowKeys = newValues.keys() 451 self._rowKeys.sort() 452 for index in range(len(self._rowKeys)): 453 key = self._rowKeys[index] 454 dict.__setitem__(self,key,newValues[key]) 455 self._rowOrder[key] = index

456

457 - def __xml__(self):

458 """@return: An XML Document object representing this matrix""" 459 doc = Document() 460 root = doc.createElement('matrix') 461 doc.appendChild(root) 462 for key,value in self.items(): 463 node = doc.createElement('row') 464 root.appendChild(node) 465 node.appendChild(key.__xml__().documentElement) 466 node.appendChild(value.__xml__().documentElement) 467 return doc

468

469 - def parse(self,element):

470 """Extracts the distribution from the given XML element 471 @param element: The XML object specifying the distribution 472 @type element: Element 473 @warning: modifies object in place; erases any previous contents of this matrix 474 """ 475 self.clear() 476 if element.tagName != 'matrix': 477 raise UserWarning,'Expected matrix Element, but got %s instead' %\ 478 element.tagName 479 matrixType = str(element.getAttribute('type')) 480 try: 481 # Stored by label? 482 cls = dynamicsTypes[matrixType] 483 except KeyError: 484 # Stored by class name? 485 for cls in dynamicsTypes.values(): 486 if cls.__name__ == '%sMatrix' % (matrixType): 487 break 488 else: 489 # Stored in some incomprehensible manner? 490 cls = self.__class__ 491 if not isinstance(self,cls): 492 matrix = cls() 493 return matrix.parse(element) 494 else: 495 matrix = self 496 node = element.firstChild 497 while node: 498 if node.nodeType == node.ELEMENT_NODE: 499 for child in node.childNodes: 500 if child.nodeType != child.ELEMENT_NODE: 501 pass 502 elif child.tagName == 'vector': 503 row = KeyedVector() 504 row = row.parse(child) 505 elif child.tagName == 'key': 506 key = Key() 507 key = key.parse(child) 508 else: 509 msg = 'Unable to parse %s element of tag "%s"' % \ 510 (matrix.__class__.__name__,child.tagName) 511 raise NotImplementedError,msg 512 matrix[key] = row 513 node = node.nextSibling 514 return matrix

515

516 - def simpleText(self,numbers=True,all=False):

517 """ 518 @return: a more user-friendly string representation of this matrix 519 @rtype: C{str}""" 520 content = '{\n' 521 for key in self.rowKeys(): 522 row = self[key] 523 for other in row.keys(): 524 if all or \ 525 (other != key and abs(self[key][other]) > 0.) or \ 526 (other == key and self[key][other] != 1.): 527 content += '%s: %s\n' % (key.simpleText(), 528 row.simpleText(numbers=numbers, 529 all=all)) 530 break 531 content += '}' 532 return content

533

534 - def __copy__(self):

535 result = self.__class__() 536 result._fresh = False 537 result._rowOrder = copy.copy(self._rowOrder) 538 result._rowKeys = copy.copy(self._rowKeys) 539 for key,row in self.items(): 540 dict.__setitem__(result,key,row) 541 return result

542

543 - def __deepcopy__(self,memo):

544 result = self.__class__() 545 memo[id(self)] = result 546 result._fresh = False 547 result._rowOrder = self._rowOrder 548 result._rowKeys = self._rowKeys 549 if self._frozen: 550 result.freeze() 551 else: 552 result.unfreeze() 553 for key,row in self.items(): 554 dict.__setitem__(result,key,copy.deepcopy(row,memo)) 555 return result

Source Code for Module teamwork.math.KeyedMatrix