python-igraph manual

For using igraph from Python

   Home       Trees       Indices       Help   
Package igraph :: Module datatypes
[hide private]

Source Code for Module igraph.datatypes

  1  # vim:ts=4:sw=4:sts=4:et 
  2  # -*- coding: utf-8 -*- 
  3  """Additional auxiliary data types""" 
  4   
  5  from itertools import islice 
  6   
  7  __license__ = """\ 
  8  Copyright (C) 2006-2012  Tamás Nepusz <ntamas@gmail.com> 
  9  Pázmány Péter sétány 1/a, 1117 Budapest, Hungary 
 10   
 11  This program is free software; you can redistribute it and/or modify 
 12  it under the terms of the GNU General Public License as published by 
 13  the Free Software Foundation; either version 2 of the License, or 
 14  (at your option) any later version. 
 15   
 16  This program is distributed in the hope that it will be useful, 
 17  but WITHOUT ANY WARRANTY; without even the implied warranty of 
 18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
 19  GNU General Public License for more details. 
 20   
 21  You should have received a copy of the GNU General Public License 
 22  along with this program; if not, write to the Free Software 
 23  Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA  
 24  02110-1301 USA 
 25  """ 
26 27 -class Matrix(object):
28 """Simple matrix data type. 29 30 Of course there are much more advanced matrix data types for Python (for 31 instance, the C{ndarray} data type of Numeric Python) and this implementation 32 does not want to compete with them. The only role of this data type is to 33 provide a convenient interface for the matrices returned by the C{Graph} 34 object (for instance, allow indexing with tuples in the case of adjacency 35 matrices and so on). 36 """ 37
38 - def __init__(self, data=None):
39 """Initializes a matrix. 40 41 @param data: the elements of the matrix as a list of lists, or C{None} to 42 create a 0x0 matrix. 43 """ 44 self._nrow, self._ncol, self._data = 0, 0, [] 45 self.data = data 46 47 # pylint: disable-msg=C0103 48 @classmethod
49 - def Fill(cls, value, *args):
50 """Creates a matrix filled with the given value 51 52 @param value: the value to be used 53 @keyword shape: the shape of the matrix. Can be a single integer, 54 two integers or a tuple. If a single integer is 55 given here, the matrix is assumed to be square-shaped. 56 """ 57 if len(args) < 1: 58 raise TypeError("expected an integer or a tuple") 59 if len(args) == 1: 60 if hasattr(args[0], "__len__"): 61 height, width = int(args[0][0]), int(args[0][1]) 62 else: 63 height, width = int(args[0]), int(args[0]) 64 else: 65 height, width = int(args[0]), int(args[1]) 66 mtrx = [[value]*width for _ in xrange(height)] 67 return cls(mtrx) 68 69 # pylint: disable-msg=C0103 70 @classmethod
71 - def Zero(cls, *args):
72 """Creates a matrix filled with zeros. 73 74 @keyword shape: the shape of the matrix. Can be a single integer, 75 two integers or a tuple. If a single integer is 76 given here, the matrix is assumed to be square-shaped. 77 """ 78 result = cls.Fill(0, *args) 79 return result 80 81 # pylint: disable-msg=C0103 82 @classmethod
83 - def Identity(cls, *args):
84 """Creates an identity matrix. 85 86 @keyword shape: the shape of the matrix. Can be a single integer, 87 two integers or a tuple. If a single integer is 88 given here, the matrix is assumed to be square-shaped. 89 """ 90 # pylint: disable-msg=W0212 91 result = cls.Fill(0, *args) 92 for i in xrange(min(result.shape)): 93 result._data[i][i] = 1 94 return result 95
96 - def _set_data(self, data=None):
97 """Sets the data stored in the matrix""" 98 if data is not None: 99 self._data = [list(row) for row in data] 100 self._nrow = len(self._data) 101 if self._nrow > 0: 102 self._ncol = max(len(row) for row in self._data) 103 else: 104 self._ncol = 0 105 for row in self._data: 106 if len(row) < self._ncol: 107 row.extend([0]*(self._ncol-len(row))) 108
109 - def _get_data(self):
110 """Returns the data stored in the matrix as a list of lists""" 111 return [list(row) for row in self._data] 112 data = property(_get_data, _set_data) 113 114 @property
115 - def shape(self):
116 """Returns the shape of the matrix as a tuple""" 117 return self._nrow, self._ncol 118
119 - def __add__(self, other):
120 """Adds the given value to the matrix. 121 122 @param other: either a scalar or a matrix. Scalars will 123 be added to each element of the matrix. Matrices will 124 be added together elementwise. 125 @return: the result matrix 126 """ 127 if isinstance(other, Matrix): 128 if self.shape != other.shape: 129 raise ValueError("matrix shapes do not match") 130 return self.__class__([ 131 [a+b for a, b in izip(row_a, row_b)] 132 for row_a, row_b in izip(self, other) 133 ]) 134 else: 135 return self.__class__([ 136 [item+other for item in row] for row in self]) 137
138 - def __eq__(self, other):
139 """Checks whether a given matrix is equal to another one""" 140 return isinstance(other, Matrix) and \ 141 self._nrow == other._nrow and \ 142 self._ncol == other._ncol and \ 143 self._data == other._data 144
145 - def __getitem__(self, i):
146 """Returns a single item, a row or a column of the matrix 147 148 @param i: if a single integer, returns the M{i}th row as a list. If a 149 slice, returns the corresponding rows as another L{Matrix} object. If 150 a 2-tuple, the first element of the tuple is used to select a row and 151 the second is used to select a column. 152 """ 153 if isinstance(i, int): 154 return list(self._data[i]) 155 elif isinstance(i, slice): 156 return self.__class__(self._data[i]) 157 elif isinstance(i, tuple): 158 try: 159 first = i[0] 160 except IndexError: 161 first = slice(None) 162 try: 163 second = i[1] 164 except IndexError: 165 second = slice(None) 166 if type(first) == slice and type(second) == slice: 167 return self.__class__(row[second] for row in self._data[first]) 168 elif type(first) == slice: 169 return [row[second] for row in self._data[first]] 170 else: 171 return self._data[first][second] 172 else: 173 raise IndexError("invalid matrix index") 174
175 - def __hash__(self):
176 """Returns a hash value for a matrix.""" 177 return hash(self._nrow, self._ncol, self._data) 178
179 - def __iadd__(self, other):
180 """In-place addition of a matrix or scalar.""" 181 if isinstance(other, Matrix): 182 if self.shape != other.shape: 183 raise ValueError("matrix shapes do not match") 184 for row_a, row_b in izip(self._data, other): 185 for i in xrange(len(row_a)): 186 row_a[i] += row_b[i] 187 else: 188 for row in self._data: 189 for i in xrange(len(row)): 190 row[i] += other 191 return self 192
193 - def __isub__(self, other):
194 """In-place subtraction of a matrix or scalar.""" 195 if isinstance(other, Matrix): 196 if self.shape != other.shape: 197 raise ValueError("matrix shapes do not match") 198 for row_a, row_b in izip(self._data, other): 199 for i in xrange(len(row_a)): 200 row_a[i] -= row_b[i] 201 else: 202 for row in self._data: 203 for i in xrange(len(row)): 204 row[i] -= other 205 return self 206
207 - def __ne__(self, other):
208 """Checks whether a given matrix is not equal to another one""" 209 return not self == other 210
211 - def __setitem__(self, i, value):
212 """Sets a single item, a row or a column of the matrix 213 214 @param i: if a single integer, sets the M{i}th row as a list. If a 215 slice, sets the corresponding rows from another L{Matrix} object. 216 If a 2-tuple, the first element of the tuple is used to select a row 217 and the second is used to select a column. 218 @param value: the new value 219 """ 220 if isinstance(i, int): 221 # Setting a row 222 if len(value) != len(self._data[i]): 223 raise ValueError("new value must have %d items" % self._ncol) 224 self._data[i] = list(value) 225 elif isinstance(i, slice): 226 # Setting multiple rows 227 if len(value) != len(self._data[i]): 228 raise ValueError("new value must have %d items" % self._ncol) 229 if any(len(row) != self._ncol for row in value): 230 raise ValueError("rows of new value must have %d items" % \ 231 self._ncol) 232 self._data[i] = [list(row) for row in value] 233 elif isinstance(i, tuple): 234 try: 235 first = i[0] 236 except IndexError: 237 first = slice(None) 238 try: 239 second = i[1] 240 except IndexError: 241 second = slice(None) 242 if type(first) == slice and type(second) == slice: 243 # Setting a submatrix 244 # TODO 245 raise NotImplementedError 246 elif type(first) == slice: 247 # Setting a submatrix 248 raise NotImplementedError 249 else: 250 # Setting a single element 251 self._data[first][second] = value 252 else: 253 raise IndexError("invalid matrix index") 254
255 - def __sub__(self, other):
256 """Subtracts the given value from the matrix. 257 258 @param other: either a scalar or a matrix. Scalars will 259 be subtracted from each element of the matrix. Matrices will 260 be subtracted together elementwise. 261 @return: the result matrix 262 """ 263 if isinstance(other, Matrix): 264 if self.shape != other.shape: 265 raise ValueError("matrix shapes do not match") 266 return self.__class__([ 267 [a-b for a, b in izip(row_a, row_b)] 268 for row_a, row_b in izip(self, other) 269 ]) 270 else: 271 return self.__class__([ 272 [item-other for item in row] for row in self]) 273
274 - def __repr__(self):
275 class_name = self.__class__.__name__ 276 rows = ("[%s]" % ", ".join(repr(item) for item in row) for row in self) 277 return "%s([%s])" % (class_name, ", ".join(rows)) 278
279 - def __str__(self):
280 rows = ("[%s]" % ", ".join(repr(item) for item in row) for row in self) 281 return "[%s]" % "\n ".join(rows) 282
283 - def __iter__(self):
284 """Support for iteration. 285 286 This is actually implemented as a generator, so there is no need for a 287 separate iterator class. The generator returns I{copies} of the rows in 288 the matrix as lists to avoid messing around with the internals. Feel 289 free to do anything with the copies, the changes won't be reflected in 290 the original matrix.""" 291 return (list(row) for row in self._data) 292
293 - def __plot__(self, context, bbox, palette, **kwds):
294 """Plots the matrix to the given Cairo context in the given box 295 296 Besides the usual self-explanatory plotting parameters (C{context}, 297 C{bbox}, C{palette}), it accepts the following keyword arguments: 298 299 - C{style}: the style of the plot. C{boolean} is useful for plotting 300 matrices with boolean (C{True}/C{False} or 0/1) values: C{False} 301 will be shown with a white box and C{True} with a black box. 302 C{palette} uses the given palette to represent numbers by colors, 303 the minimum will be assigned to palette color index 0 and the maximum 304 will be assigned to the length of the palette. C{None} draws transparent 305 cell backgrounds only. The default style is C{boolean} (but it may 306 change in the future). C{None} values in the matrix are treated 307 specially in both cases: nothing is drawn in the cell corresponding 308 to C{None}. 309 310 - C{square}: whether the cells of the matrix should be square or not. 311 Default is C{True}. 312 313 - C{grid_width}: line width of the grid shown on the matrix. If zero or 314 negative, the grid is turned off. The grid is also turned off if the size 315 of a cell is less than three times the given line width. Default is C{1}. 316 Fractional widths are also allowed. 317 318 - C{border_width}: line width of the border drawn around the matrix. 319 If zero or negative, the border is turned off. Default is C{1}. 320 321 - C{row_names}: the names of the rows 322 323 - C{col_names}: the names of the columns. 324 325 - C{values}: values to be displayed in the cells. If C{None} or 326 C{False}, no values are displayed. If C{True}, the values come 327 from the matrix being plotted. If it is another matrix, the 328 values of that matrix are shown in the cells. In this case, 329 the shape of the value matrix must match the shape of the 330 matrix being plotted. 331 332 - C{value_format}: a format string or a callable that specifies how 333 the values should be plotted. If it is a callable, it must be a 334 function that expects a single value and returns a string. 335 Example: C{"%#.2f"} for floating-point numbers with always exactly 336 two digits after the decimal point. See the Python documentation of 337 the C{%} operator for details on the format string. If the format 338 string is not given, it defaults to the C{str} function. 339 340 If only the row names or the column names are given and the matrix 341 is square-shaped, the same names are used for both column and row 342 names. 343 """ 344 # pylint: disable-msg=W0142 345 # pylint: disable-msg=C0103 346 grid_width = float(kwds.get("grid_width", 1.)) 347 border_width = float(kwds.get("border_width", 1.)) 348 style = kwds.get("style", "boolean") 349 row_names = kwds.get("row_names") 350 col_names = kwds.get("col_names", row_names) 351 values = kwds.get("values") 352 value_format = kwds.get("value_format", str) 353 354 # Validations 355 if style not in ("boolean", "palette", "none", None): 356 raise ValueError("invalid style") 357 if style == "none": 358 style = None 359 if row_names is None and col_names is not None: 360 row_names = col_names 361 if row_names is not None: 362 row_names = [str(name) for name in islice(row_names, self._nrow)] 363 if len(row_names) < self._nrow: 364 row_names.extend([""]*(self._nrow-len(row_names))) 365 if col_names is not None: 366 col_names = [str(name) for name in islice(col_names, self._ncol)] 367 if len(col_names) < self._ncol: 368 col_names.extend([""]*(self._ncol-len(col_names))) 369 if values == False: 370 values = None 371 if values == True: 372 values = self 373 if isinstance(values, list): 374 values = Matrix(list) 375 if values is not None and not isinstance(values, Matrix): 376 raise TypeError("values must be None, False, True or a matrix") 377 if values is not None and values.shape != self.shape: 378 raise ValueError("values must be a matrix of size %s" % self.shape) 379 380 # Calculate text extents if needed 381 if row_names is not None or col_names is not None: 382 te = context.text_extents 383 space_width = te(" ")[4] 384 max_row_name_width = max([te(s)[4] for s in row_names])+space_width 385 max_col_name_width = max([te(s)[4] for s in col_names])+space_width 386 else: 387 max_row_name_width, max_col_name_width = 0, 0 388 389 # Calculate sizes 390 total_width = float(bbox.width)-max_row_name_width 391 total_height = float(bbox.height)-max_col_name_width 392 dx = total_width / self.shape[1] 393 dy = total_height / self.shape[0] 394 if kwds.get("square", True): 395 dx, dy = min(dx, dy), min(dx, dy) 396 total_width, total_height = dx*self.shape[1], dy*self.shape[0] 397 ox = bbox.left + (bbox.width - total_width - max_row_name_width) / 2.0 398 oy = bbox.top + (bbox.height - total_height - max_col_name_width) / 2.0 399 ox += max_row_name_width 400 oy += max_col_name_width 401 402 # Determine rescaling factors for the palette if needed 403 if style == "palette": 404 mi, ma = self.min(), self.max() 405 color_offset = mi 406 color_ratio = (len(palette)-1) / float(ma-mi) 407 408 # Validate grid width 409 if dx < 3*grid_width or dy < 3*grid_width: 410 grid_width = 0. 411 if grid_width > 0: 412 context.set_line_width(grid_width) 413 else: 414 # When the grid width is zero, we will still stroke the 415 # rectangles, but with the same color as the fill color 416 # of the cell - otherwise we would get thin white lines 417 # between the cells as a drawing artifact 418 context.set_line_width(1) 419 420 # Draw row names (if any) 421 context.set_source_rgb(0., 0., 0.) 422 if row_names is not None: 423 x, y = ox, oy 424 for heading in row_names: 425 _, _, _, h, xa, _ = context.text_extents(heading) 426 context.move_to(x-xa-space_width, y + (dy+h)/2.) 427 context.show_text(heading) 428 y += dy 429 430 # Draw column names (if any) 431 if col_names is not None: 432 context.save() 433 context.translate(ox, oy) 434 context.rotate(-1.5707963285) # pi/2 435 x, y = 0., 0. 436 for heading in col_names: 437 _, _, _, h, _, _ = context.text_extents(heading) 438 context.move_to(x+space_width, y + (dx+h)/2.) 439 context.show_text(heading) 440 y += dx 441 context.restore() 442 443 # Draw matrix 444 x, y = ox, oy 445 if style is None: 446 fill = lambda: None 447 else: 448 fill = context.fill_preserve 449 for row in self: 450 for item in row: 451 if item is None: 452 x += dx 453 continue 454 if style == "boolean": 455 if item: 456 context.set_source_rgb(0., 0., 0.) 457 else: 458 context.set_source_rgb(1., 1., 1.) 459 elif style == "palette": 460 cidx = int((item-color_offset)*color_ratio) 461 if cidx < 0: 462 cidx = 0 463 context.set_source_rgba(*palette.get(cidx)) 464 context.rectangle(x, y, dx, dy) 465 if grid_width > 0: 466 fill() 467 context.set_source_rgb(0.5, 0.5, 0.5) 468 context.stroke() 469 else: 470 fill() 471 context.stroke() 472 x += dx 473 x, y = ox, y+dy 474 475 # Draw cell values 476 if values is not None: 477 x, y = ox, oy 478 context.set_source_rgb(0., 0., 0.) 479 for row in values.data: 480 if hasattr(value_format, "__call__"): 481 values = [value_format(item) for item in row] 482 else: 483 values = [value_format % item for item in row] 484 for item in values: 485 th, tw = context.text_extents(item)[3:5] 486 context.move_to(x+(dx-tw)/2., y+(dy+th)/2.) 487 context.show_text(item) 488 x += dx 489 x, y = ox, y+dy 490 491 # Draw borders 492 if border_width > 0: 493 context.set_line_width(border_width) 494 context.set_source_rgb(0., 0., 0.) 495 context.rectangle(ox, oy, dx*self.shape[1], dy*self.shape[0]) 496 context.stroke() 497 498
499 - def min(self, dim=None):
500 """Returns the minimum of the matrix along the given dimension 501 502 @param dim: the dimension. 0 means determining the column minimums, 1 means 503 determining the row minimums. If C{None}, the global minimum is 504 returned. 505 """ 506 if dim == 1: 507 return [min(row) for row in self._data] 508 if dim == 0: 509 return [min(row[idx] for row in self._data) \ 510 for idx in xrange(self._ncol)] 511 return min(min(row) for row in self._data) 512
513 - def max(self, dim=None):
514 """Returns the maximum of the matrix along the given dimension 515 516 @param dim: the dimension. 0 means determining the column maximums, 1 means 517 determining the row maximums. If C{None}, the global maximum is 518 returned. 519 """ 520 if dim == 1: 521 return [max(row) for row in self._data] 522 if dim == 0: 523 return [max(row[idx] for row in self._data) \ 524 for idx in xrange(self._ncol)] 525 return max(max(row) for row in self._data)
526
527 528 -class DyadCensus(tuple):
529 """Dyad census of a graph. 530 531 This is a pretty simple class - basically it is a tuple, but it allows 532 the user to refer to its individual items by the names C{mutual} (or 533 C{mut}), C{asymmetric} (or C{asy} or C{asym} or C{asymm}) and C{null}. 534 535 Examples: 536 537 >>> from igraph import Graph 538 >>> g=Graph.Erdos_Renyi(100, 0.2, directed=True) 539 >>> dc=g.dyad_census() 540 >>> print dc.mutual #doctest:+SKIP 541 179 542 >>> print dc["asym"] #doctest:+SKIP 543 1609 544 >>> print tuple(dc), list(dc) #doctest:+SKIP 545 (179, 1609, 3162) [179, 1609, 3162] 546 >>> print sorted(dc.as_dict().items()) #doctest:+ELLIPSIS 547 [('asymmetric', ...), ('mutual', ...), ('null', ...)] 548 549 @undocumented: _remap 550 """ 551 _remap = {"mutual": 0, "mut": 0, "sym": 0, "symm": 0, 552 "asy": 1, "asym": 1, "asymm": 1, "asymmetric": 1, "null": 2} 553
554 - def __getitem__(self, idx):
555 return tuple.__getitem__(self, self._remap.get(idx, idx)) 556
557 - def __getattr__(self, attr):
558 if attr in self._remap: 559 return tuple.__getitem__(self, self._remap[attr]) 560 raise AttributeError("no such attribute: %s" % attr) 561
562 - def __repr__(self):
563 return "DyadCensus((%d, %d, %d))" % self 564
565 - def __str__(self):
566 return "%d mutual, %d asymmetric, %d null dyads" % self 567
568 - def as_dict(self):
569 """Converts the dyad census to a dict using the known dyad names.""" 570 return {"mutual": self[0], "asymmetric": self[1], "null": self[2]}
571
572 573 -class TriadCensus(tuple):
574 """Triad census of a graph. 575 576 This is a pretty simple class - basically it is a tuple, but it allows 577 the user to refer to its individual items by the following triad names: 578 579 - C{003} -- the empty graph 580 - C{012} -- a graph with a single directed edge (C{A --> B, C}) 581 - C{102} -- a graph with a single mutual edge (C{A <-> B, C}) 582 - C{021D} -- the binary out-tree (C{A <-- B --> C}) 583 - C{021U} -- the binary in-tree (C{A --> B <-- C}) 584 - C{021C} -- the directed line (C{A --> B --> C}) 585 - C{111D} -- C{A <-> B <-- C} 586 - C{111U} -- C{A <-> B --> C} 587 - C{030T} -- C{A --> B <-- C, A --> C} 588 - C{030C} -- C{A <-- B <-- C, A --> C} 589 - C{201} -- C{A <-> B <-> C} 590 - C{120D} -- C{A <-- B --> C, A <-> C} 591 - C{120U} -- C{A --> B <-- C, A <-> C} 592 - C{120C} -- C{A --> B --> C, A <-> C} 593 - C{210C} -- C{A --> B <-> C, A <-> C} 594 - C{300} -- the complete graph (C{A <-> B <-> C, A <-> C}) 595 596 Attribute and item accessors are provided. Due to the syntax of Python, 597 attribute names are not allowed to start with a number, therefore the 598 triad names must be prepended with a lowercase C{t} when accessing 599 them as attributes. This is not necessary with the item accessor syntax. 600 601 Examples: 602 603 >>> from igraph import Graph 604 >>> g=Graph.Erdos_Renyi(100, 0.2, directed=True) 605 >>> tc=g.triad_census() 606 >>> print tc.t003 #doctest:+SKIP 607 39864 608 >>> print tc["030C"] #doctest:+SKIP 609 1206 610 """ 611 _remap = {"003": 0, "012": 1, "102": 2, "021D": 3, "021U": 4, "021C": 5, \ 612 "111D": 6, "111U": 7, "030T": 8, "030C": 9, "201": 10, "120D": 11, \ 613 "120U": 12, "120C": 13, "210": 14, "300": 15} 614
615 - def __getitem__(self, idx):
616 if isinstance(idx, basestring): 617 idx = idx.upper() 618 return tuple.__getitem__(self, self._remap.get(idx, idx)) 619
620 - def __getattr__(self, attr):
621 if isinstance(attr, basestring) and attr[0] == 't' \ 622 and attr[1:].upper() in self._remap: 623 return tuple.__getitem__(self, self._remap[attr[1:].upper()]) 624 raise AttributeError("no such attribute: %s" % attr) 625
626 - def __repr__(self):
627 return "TriadCensus((%s))" % ", ".join(str(item) for item in self) 628
629 - def __str__(self):
630 maxidx = len(self) 631 maxcount = max(self) 632 numwidth = len(str(maxcount)) 633 captionwidth = max(len(key) for key in self._remap) 634 colcount = 4 635 636 rowcount = maxidx / colcount 637 if rowcount * colcount < maxidx: 638 rowcount += 1 639 640 invmap = dict((v, k) for k, v in self._remap.iteritems()) 641 result, row, idx = [], [], 0 642 for _ in xrange(rowcount): 643 for _ in xrange(colcount): 644 if idx >= maxidx: 645 break 646 row.append("%-*s: %*d" % (captionwidth, invmap.get(idx, ""), 647 numwidth, self[idx])) 648 idx += 1 649 result.append(" | ".join(row)) 650 row = [] 651 652 return "\n".join(result)
653
654 655 -class UniqueIdGenerator(object):
656 """A dictionary-like class that can be used to assign unique IDs to 657 names (say, vertex names). 658 659 Usage: 660 661 >>> gen = UniqueIdGenerator() 662 >>> gen["A"] 663 0 664 >>> gen["B"] 665 1 666 >>> gen["C"] 667 2 668 >>> gen["A"] # Retrieving already existing ID 669 0 670 >>> gen.add("D") # Synonym of gen["D"] 671 3 672 >>> len(gen) # Number of already used IDs 673 4 674 >>> "C" in gen 675 True 676 >>> "E" in gen 677 False 678 """ 679
680 - def __init__(self, id_generator=None, initial=None):
681 """Creates a new unique ID generator. `id_generator` specifies how do we 682 assign new IDs to elements that do not have an ID yet. If it is `None`, 683 elements will be assigned integer identifiers starting from 0. If it is 684 an integer, elements will be assigned identifiers starting from the given 685 integer. If it is an iterator or generator, its `next` method will be 686 called every time a new ID is needed.""" 687 if id_generator is None: 688 id_generator = 0 689 if isinstance(id_generator, int): 690 import itertools 691 self._generator = itertools.count(id_generator) 692 else: 693 self._generator = id_generator 694 self._ids = {} 695 if initial: 696 for value in initial: 697 self.add(value) 698
699 - def __contains__(self, item):
700 """Checks whether `item` already has an ID or not.""" 701 return item in self._ids 702
703 - def __getitem__(self, item):
704 """Retrieves the ID corresponding to `item`. Generates a new ID for 705 `item` if it is the first time we request an ID for it.""" 706 try: 707 return self._ids[item] 708 except KeyError: 709 self._ids[item] = self._generator.next() 710 return self._ids[item] 711
712 - def __setitem__(self, item, value):
713 """Overrides the ID for `item`.""" 714 self._ids[item] = value 715
716 - def __len__(self):
717 """"Returns the number of items""" 718 return len(self._ids) 719
720 - def reverse_dict(self):
721 """Returns the reverse mapping, i.e., the one that maps from generated 722 IDs to their corresponding objects""" 723 return dict((v, k) for k, v in self._ids.iteritems()) 724
725 - def values(self):
726 """Returns the values stored so far. If the generator generates items 727 according to the standard sorting order, the values returned will be 728 exactly in the order they were added. This holds for integer IDs for 729 instance (but for many other ID generators as well).""" 730 return sorted(self._ids.keys(), key = self._ids.__getitem__) 731 732 add = __getitem__ 733

   Home       Trees       Indices       Help