« back to all changes in this revision
Viewing changes to igraph/datatypes.py
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Package Import Robot
- Author(s): TANIGUCHI Takaki
- Date: 2012-03-17 17:23:55 UTC
- Revision ID: package-import@ubuntu.com-20120317172355-e9iki37igmxnlq38
Tags: upstream-0.5.4
Import upstream version 0.5.4
- files added:
- debian
- igraph
- igraph/app
- igraph/test
- python_igraph.egg-info
- scripts
- src
added
removed
igraph/datatypes.py
1
"""Additional auxiliary data types"""
2
3
class Matrix(object):
4
"""Simple matrix data type.
5
6
Of course there are much more advanced matrix data types for Python (for
7
instance, the C{ndarray} data type of Numeric Python) and this implementation
8
does not want to compete with them. The only role of this data type is to
9
provide a convenient interface for the matrices returned by the C{Graph}
10
object (for instance, allow indexing with tuples in the case of adjacency
11
matrices and so on).
12
"""
13
14
def __init__(self, data=None):
15
"""Initializes a matrix.
16
17
@param data: the elements of the matrix as a list of lists, or C{None} to
18
create a 0x0 matrix.
19
"""
20
self._data = []
21
self.data = data
22
23
def Fill(klass, value, *args):
24
"""Creates a matrix filled with the given value
25
26
@param value: the value to be used
27
@keyword shape: the shape of the matrix. Can be a single integer,
28
two integers or a tuple. If a single integer is
29
given here, the matrix is assumed to be square-shaped.
30
"""
31
if len(args) < 1: raise TypeError, "expected an integer or a tuple"
32
if len(args) == 1:
33
if hasattr(args[0], "__len__"):
34
h, w = map(int, args[0][0:2])
35
else:
36
h, w = int(args[0]), int(args[0])
37
else: h, w = map(int, args[0:2])
38
mtrx = [[value]*w for _ in xrange(h)]
39
return klass(mtrx)
40
Fill=classmethod(Fill)
41
42
def Zero(klass, *args):
43
"""Creates a matrix filled with zeros.
44
45
@keyword shape: the shape of the matrix. Can be a single integer,
46
two integers or a tuple. If a single integer is
47
given here, the matrix is assumed to be square-shaped.
48
"""
49
result = klass.Fill(0, *args)
50
return result
51
Zero=classmethod(Zero)
52
53
def Identity(klass, *args):
54
"""Creates an identity matrix.
55
56
@keyword shape: the shape of the matrix. Can be a single integer,
57
two integers or a tuple. If a single integer is
58
given here, the matrix is assumed to be square-shaped.
59
"""
60
result=klass.Fill(0, *args)
61
for i in xrange(min(*result.shape)): result._data[i][i] = 1
62
return result
63
Identity=classmethod(Identity)
64
65
def _set_data(self, data=None):
66
"""Sets the data stored in the matrix"""
67
if data is not None:
68
self._data = map(list, data)
69
self._nrow = len(data)
70
self._ncol = max(map(len, data))
71
for row in self._data:
72
if len(row) < self._ncol: row.extend([0]*(self._ncol-len(row)))
73
74
def _get_data(self):
75
"""Returns the data stored in the matrix as a list of lists"""
76
return [list(row) for row in self._data]
77
data = property(_get_data, _set_data, doc="Elements of the matrix as a list of lists")
78
79
def _get_shape(self):
80
"""Returns the shape of the matrix"""
81
return self._nrow, self._ncol
82
shape = property(_get_shape, doc="Shape of the matrix as a tuple")
83
84
def __getitem__(self, i):
85
"""Returns a single item, a row or a column of the matrix
86
87
@param i: if a single integer, returns the M{i}th row as a list. If a
88
slice, returns the corresponding rows as another L{Matrix} object. If
89
a 2-tuple, the first element of the tuple is used to select a row and
90
the second is used to select a column.
91
"""
92
if isinstance(i, int):
93
return list(self._data[i])
94
elif isinstance(i, slice):
95
return self.__class__(self._data[i])
96
elif isinstance(i, tuple):
97
try:
98
first = i[0]
99
except:
100
first = slice(None)
101
try:
102
second = i[1]
103
except:
104
second = slice(None)
105
if type(first) == slice and type(second) == slice:
106
return self.__class__([row[second] for row in self._data[first]])
107
elif type(first) == slice:
108
return [row[second] for row in self._data[first]]
109
else:
110
return self._data[first][second]
111
else:
112
raise IndexError, "invalid matrix index"
113
114
115
def __setitem__(self, i, value):
116
"""Sets a single item, a row or a column of the matrix
117
118
@param i: if a single integer, sets the M{i}th row as a list. If a
119
slice, sets the corresponding rows from another L{Matrix} object.
120
If a 2-tuple, the first element of the tuple is used to select a row
121
and the second is used to select a column.
122
@param value: the new value
123
"""
124
if isinstance(i, int):
125
# Setting a row
126
if len(value) != len(self._data[i]):
127
raise ValueError, "new value must have %d items" % len(self._data[i])
128
self._data[i] = list(value)
129
elif isinstance(i, slice):
130
# Setting multiple rows
131
if len(value) != len(self._data[i]):
132
raise ValueError, "new value must have %d items" % len(self._data[i])
133
for j in xrange(len(value)):
134
if len(value[j]) != len(self._data[0]):
135
raise ValueError, "rows of new value must have %d items" % len(self._data[0])
136
self._data[i] = list(map(list, value))
137
elif isinstance(i, tuple):
138
try:
139
first = i[0]
140
except:
141
first = slice(None)
142
try:
143
second = i[1]
144
except:
145
second = slice(None)
146
if type(first) == slice and type(second) == slice:
147
# Setting a submatrix
148
# TODO
149
raise NotImplementedError
150
elif type(first) == slice:
151
# Setting a submatrix
152
raise NotImplementedError
153
else:
154
# Setting a single element
155
self._data[first][second] = value
156
else:
157
raise IndexError, "invalid matrix index"
158
159
160
def __repr__(self):
161
return "Matrix([\n %s])" % ",\n ".join(["[%s]" % (", ".join(map(repr, row))) for row in self])
162
163
def __str__(self):
164
return "[%s]" % "\n ".join(["[%s]" % (", ".join(map(str, row))) for row in self])
165
166
def __iter__(self):
167
"""Support for iteration.
168
169
This is actually implemented as a generator, so there is no need for a
170
separate iterator class. The generator returns I{copies} of the rows in
171
the matrix as lists to avoid messing around with the internals. Feel
172
free to do anything with the copies, the changes won't be reflected in
173
the original matrix."""
174
for row in self._data: yield list(row)
175
176
def __plot__(self, context, bbox, palette, *args, **kwds):
177
"""Plots the matrix to the given Cairo context in the given box
178
179
Besides the usual self-explanatory plotting parameters (C{context},
180
C{bbox}, C{palette}), it accepts the following keyword arguments:
181
182
- C{style}: the style of the plot. C{boolean} is useful for plotting
183
matrices with boolean (C{True}/C{False} or 0/1) values: C{False}
184
will be shown with a white box and C{True} with a black box.
185
C{palette} uses the given palette to represent numbers by colors,
186
the minimum will be assigned to palette color index 0 and the maximum
187
will be assigned to the length of the palette. The default style is
188
C{boolean} (but it may change in the future). C{None} values in
189
the matrix are treated specially in both cases: nothing is drawn in
190
the cell corresponding to C{None}.
191
192
- C{square}: whether the cells of the matrix should be square or not.
193
Default is C{True}.
194
195
- C{grid_width}: line width of the grid shown on the matrix. If zero or
196
negative, the grid is turned off. The grid is also turned off if the size
197
of a cell is less than three times the given line width. Default is C{1}.
198
Fractional widths are also allowed.
199
200
- C{border_width}: line width of the border shown around the matrix.
201
If zero or negative, the border is turned off. Default is C{1}.
202
203
- C{row_names}: the names of the rows
204
205
- C{col_names}: the names of the columns.
206
207
- C{values}: values to be displayed in the cells. If C{None} or
208
C{False}, no values are displayed. If C{True}, the values come
209
from the matrix being plotted. If it is another matrix, the
210
values of that matrix are shown in the cells. In this case,
211
the shape of the value matrix must match the shape of the
212
matrix being plotted.
213
214
- C{value_format}: a format string or a callable that specifies how
215
the values should be plotted. If it is a callable, it must be a
216
function that expects a single value and returns a string.
217
Example: C{"%#.2f"} for floating-point numbers with always exactly
218
two digits after the decimal point. See the Python documentation of
219
the C{%} operator for details on the format string. If the format
220
string is not given, it defaults to the C{str} function.
221
222
If only the row names or the column names are given and the matrix
223
is square-shaped, the same names are used for both column and row
224
names.
225
"""
226
import colors
227
gw = float(kwds.get("grid_width", 1.))
228
border_width = float(kwds.get("border_width", 1.))
229
style = kwds.get("style", "boolean")
230
row_names = kwds.get("row_names", None)
231
col_names = kwds.get("col_names", row_names)
232
values = kwds.get("values", None)
233
value_format = kwds.get("value_format", str)
234
235
# Validations
236
if style not in ("boolean", "palette"): raise ValueError, "invalid style"
237
if row_names is None and col_names is not None: row_names=col_names
238
if row_names is not None:
239
row_names=list(row_names)[0:self._nrow]
240
if len(row_names) < self._nrow:
241
row_names.extend([""]*(self._nrow-len(row_names)))
242
if col_names is not None:
243
col_names=list(col_names)[0:self._ncol]
244
if len(col_names) < self._ncol:
245
col_names.extend([""]*(self._ncol-len(col_names)))
246
if values == False: values=None
247
if values == True: values=self
248
if isinstance(values, list): values=Matrix(list)
249
if values is not None and not isinstance(values, Matrix):
250
raise TypeError, "values must be None, False, True or a matrix"
251
if values is not None and values.shape != self.shape:
252
raise ValueError, "values must be a matrix of size %s" % str(self.shape)
253
254
_, _, font_height, _, _ = context.font_extents()
255
256
# Calculate text extents if needed
257
if row_names is not None or col_names is not None:
258
te = context.text_extents
259
space_width = te(" ")[4]
260
max_row_name_width = max([te(s)[4] for s in row_names])+space_width
261
max_col_name_width = max([te(s)[4] for s in col_names])+space_width
262
else:
263
max_row_name_width, max_col_name_width = 0, 0
264
265
# Calculate sizes
266
total_width = float(bbox.width)-max_row_name_width
267
total_height = float(bbox.height)-max_col_name_width
268
dx = total_width / self.shape[1]
269
dy = total_height / self.shape[0]
270
if kwds.get("square", True):
271
dx, dy = min(dx, dy), min(dx, dy)
272
total_width, total_height = dx*self.shape[1], dy*self.shape[0]
273
ox = bbox.left + (bbox.width - total_width - max_row_name_width) / 2.0
274
oy = bbox.top + (bbox.height - total_height - max_col_name_width) / 2.0
275
ox += max_row_name_width
276
oy += max_col_name_width
277
278
# Determine rescaling factors for the palette if needed
279
if style == "palette":
280
mi, ma = self.min(), self.max()
281
color_offset = mi
282
color_ratio = (len(palette)-1) / float(ma-mi)
283
284
# Validate grid width
285
if dx < 3*gw or dy < 3*gw: gw = 0.
286
if gw>0: context.set_line_width(gw)
287
288
# Draw row names (if any)
289
context.set_source_rgb(0., 0., 0.)
290
if row_names is not None:
291
x, y = ox, oy
292
for heading in row_names:
293
_, _, _, h, xa, _ = context.text_extents(heading)
294
context.move_to(x-xa-space_width, y + (dy+h)/2.)
295
context.show_text(heading)
296
y += dy
297
298
# Draw column names (if any)
299
if col_names is not None:
300
context.save()
301
context.translate(ox, oy)
302
context.rotate(-1.5707963285) # pi/2
303
x, y = 0., 0.
304
for heading in col_names:
305
_, _, _, h, _, _ = context.text_extents(heading)
306
context.move_to(x+space_width, y + (dx+h)/2.)
307
context.show_text(heading)
308
y += dx
309
context.restore()
310
311
# Draw matrix
312
x, y = ox, oy
313
for row in self:
314
for item in row:
315
if item is None:
316
x += dx
317
continue
318
if style == "boolean":
319
if item:
320
context.set_source_rgb(0., 0., 0.)
321
else:
322
context.set_source_rgb(1., 1., 1.)
323
elif style == "palette":
324
cidx = int((item-color_offset)*color_ratio)
325
if cidx < 0: cidx = 0
326
context.set_source_rgb(*palette.get(cidx))
327
context.rectangle(x, y, dx, dy)
328
if gw>0:
329
context.fill_preserve()
330
context.set_source_rgb(0.5, 0.5, 0.5)
331
context.stroke()
332
else:
333
context.fill()
334
x += dx
335
x, y = ox, y+dy
336
337
# Draw cell values
338
if values is not None:
339
x, y = ox, oy
340
context.set_source_rgb(0., 0., 0.)
341
for row in values.data:
342
if hasattr(value_format, "__call__"):
343
values = [value_format(item) for item in row]
344
else:
345
values = [value_format % item for item in row]
346
for item in values:
347
th, tw = context.text_extents(item)[3:5]
348
context.move_to(x+(dx-tw)/2., y+(dy+th)/2.)
349
context.show_text(item)
350
x += dx
351
x, y = ox, y+dy
352
353
# Draw borders
354
if border_width > 0:
355
context.set_line_width(border_width)
356
context.set_source_rgb(0., 0., 0.)
357
context.rectangle(ox, oy, dx*self.shape[1], dy*self.shape[0])
358
context.stroke()
359
360
361
def min(self, dim=None):
362
"""Returns the minimum of the matrix along the given dimension
363
364
@param dim: the dimension. 0 means determining the column minimums, 1 means
365
determining the row minimums. If C{None}, the global minimum is
366
returned.
367
"""
368
if dim == 1: return map(min, self._data)
369
if dim == 0: return map(min, [[row[idx] for row in self._data] for idx in xrange(self._ncol)])
370
return min(map(min, self._data))
371
372
def max(self, dim=None):
373
"""Returns the maximum of the matrix along the given dimension
374
375
@param dim: the dimension. 0 means determining the column maximums, 1 means
376
determining the row maximums. If C{None}, the global maximum is
377
returned.
378
"""
379
if dim == 1: return map(max, self._data)
380
if dim == 0: return map(max, [[row[idx] for row in self._data] for idx in xrange(self._ncol)])
381
return max(map(max, self._data))
382
383
384
class DyadCensus(tuple):
385
"""Dyad census of a graph.
386
387
This is a pretty simple class - basically it is a tuple, but it allows
388
the user to refer to its individual items by the names C{mutual} (or
389
C{mut}), C{asymmetric} (or C{asy} or C{asym} or C{asymm}) and C{null}.
390
391
Examples:
392
393
>>> g=Graph.Erdos_Renyi(100, 0.2, directed=True)
394
>>> dc=g.dyad_census()
395
>>> print dc.mutual
396
179
397
>>> print dc["asym"]
398
1609
399
>>> print tuple(dc), list(dc)
400
(179, 1609, 3162) [179, 1609, 3162]
401
>>> print dc.as_dict()
402
{"mutual": 179, "asymmetric": 1609, "null": 3162}
403
"""
404
_remap = {"mutual": 0, "mut": 0, "sym": 0, "symm": 0,
405
"asy": 1, "asym": 1, "asymm": 1, "asymmetric": 1, "null": 2}
406
407
def __getitem__(self, idx):
408
return tuple.__getitem__(self, self._remap.get(idx, idx))
409
410
def __getattr__(self, attr):
411
if attr in self._remap.keys():
412
return tuple.__getitem__(self, self._remap[attr])
413
raise AttributeError, "no such attribute: %s" % attr
414
415
def __repr__(self):
416
return "DyadCensus((%d, %d, %d))" % self
417
418
def __str__(self):
419
return "%d mutual, %d asymmetric, %d null dyads" % self
420
421
def as_dict(self):
422
"""Converts the dyad census to a dict using the known dyad names."""
423
return {"mutual": self[0], "asymmetric": self[1], "null": self[2]}
424
425
426
class TriadCensus(tuple):
427
"""Triad census of a graph.
428
429
This is a pretty simple class - basically it is a tuple, but it allows
430
the user to refer to its individual items by the following triad names:
431
432
- C{003} -- the empty graph
433
- C{012} -- a graph with a single directed edge (C{A --> B, C})
434
- C{102} -- a graph with a single mutual edge (C{A <-> B, C})
435
- C{021D} -- the binary out-tree (C{A <-- B --> C})
436
- C{021U} -- the binary in-tree (C{A --> B <-- C})
437
- C{021C} -- the directed line (C{A --> B --> C})
438
- C{111D} -- C{A <-> B <-- C}
439
- C{111U} -- C{A <-> B --> C}
440
- C{030T} -- C{A --> B <-- C, A --> C}
441
- C{030C} -- C{A <-- B <-- C, A --> C}
442
- C{201} -- C{A <-> B <-> C}
443
- C{120D} -- C{A <-- B --> C, A <-> C}
444
- C{120U} -- C{A --> B <-- C, A <-> C}
445
- C{120C} -- C{A --> B --> C, A <-> C}
446
- C{210C} -- C{A --> B <-> C, A <-> C}
447
- C{300} -- the complete graph (C{A <-> B <-> C, A <-> C})
448
449
Attribute and item accessors are provided. Due to the syntax of Python,
450
attribute names are not allowed to start with a number, therefore the
451
triad names must be prepended with a lowercase C{t} when accessing
452
them as attributes. This is not necessary with the item accessor syntax.
453
454
Examples:
455
456
>>> g=Graph.Erdos_Renyi(100, 0.2, directed=True)
457
>>> tc=g.triad_census()
458
>>> print tc.t003
459
39864
460
>>> print tc["030C"]
461
1206
462
"""
463
_remap = {"003": 0, "012": 1, "102": 2, "021D": 3, "021U": 4, "021C": 5, \
464
"111D": 6, "111U": 7, "030T": 8, "030C": 9, "201": 10, "120D": 11, \
465
"120U": 12, "120C": 13, "210": 14, "300": 15}
466
467
def __getitem__(self, idx):
468
if isinstance(idx, basestring): idx=idx.upper()
469
return tuple.__getitem__(self, self._remap.get(idx, idx))
470
471
def __getattr__(self, attr):
472
if isinstance(attr, basestring) and attr[0] == 't' \
473
and attr[1:].upper() in self._remap.keys():
474
return tuple.__getitem__(self, self._remap[attr[1:].upper()])
475
raise AttributeError, "no such attribute: %s" % attr
476
477
def __repr__(self):
478
return "TriadCensus((%s))" % ", ".join(map(str, self))
479
480
def __str__(self):
481
maxidx = len(self)
482
maxcount = max(self)
483
numwidth = len(str(maxcount))
484
captionwidth = max(map(len, self._remap.keys()))
485
colcount = 4
486
487
rowcount = maxidx / colcount
488
if rowcount * colcount < maxidx: rowcount += 1
489
490
invmap = dict((v,k) for k,v in self._remap.iteritems())
491
result, row, idx = [], [], 0
492
for rowidx in xrange(rowcount):
493
for colidx in xrange(colcount):
494
if idx >= maxidx: break
495
row.append("%-*s: %*d" % (captionwidth, invmap.get(idx, ""),
496
numwidth, self[idx]))
497
idx += 1
498
result.append(" | ".join(row))
499
row = []
500
501
return "\n".join(result)
502
503
504
class Cut(object):
505
"""A cut of a given graph.
506
507
This is a simple class used to represent cuts returned by
508
L{Graph.mincut}. It has the following attributes:
509
510
- C{graph} - the graph on which this cut is defined
511
512
- C{value} - the value (capacity) of the cut
513
514
- C{partition} - vertex IDs in the parts created
515
after removing edges in the cut
516
517
- C{cut} - edge IDs in the cut
518
519
- C{es} - an edge selector restricted to the edges
520
in the cut.
521
522
Attributes are not read only, but you should consider them
523
as being read only. Unexpected behaviour may occur if you
524
mess with them.
525
526
You can use indexing on this object to obtain L{VertexSeq}
527
objects of the partitions.
528
529
This class is usually not instantiated directly, everything
530
is taken care of by L{Graph.mincut}.
531
532
Examples:
533
534
>>> g = Graph.Ring(20)
535
>>> mc = g.mincut()
536
>>> print mc.value
537
2
538
>>> print min(map(len, mc))
539
1
540
>>> mc.es["color"] = ["red"] * len(mc.es)
541
"""
542
543
__slots__ = ["_graph", "_value", "_partition", "_cut"]
544
545
def __init__(self, graph, value, cut, partition, partition2):
546
"""Initializes the cut.
547
548
This should not be called directly, everything is
549
taken care of by L{Graph.mincut}.
550
"""
551
self._graph = graph
552
self._value = float(value)
553
self._partition = (partition, partition2)
554
self._cut = cut
555
556
def __repr__(self):
557
return "%s(%s,%s,%s,%s,%s)" % \
558
(self.__class__.__name__, repr(self._graph), \
559
self._value, repr(self._cut), \
560
repr(self._partition[0]), repr(self._partition[1]))
561
562
def __str__(self):
563
return "Graph cut (%d edges, %d vs %d vertices, value=%.4f)" % \
564
(len(self._cut), len(self._partition[0]), len(self._partition[1]), \
565
self._value)
566
567
def __len__(self): return 2
568
569
def __getitem__(self, idx):
570
if idx >= 2: raise IndexError, "a cut has only two partitions"
571
return self.graph.vs.select(self._partition[idx])
572
573
def _get_es(self): return self._graph.es.select(self.cut)
574
def _get_graph(self): return self._graph
575
def _get_partition(self): return self._partition
576
def _get_cut(self): return self._cut
577
def _get_value(self): return self._value
578
579
es = property(_get_es, doc="Returns an edge selector restricted to the cut")
580
graph = property(_get_graph, doc="The graph over which this cut is defined")
581
partition = property(_get_partition,
582
doc="Vertex IDs partitioned according to the cut")
583
cut = property(_get_cut, doc="Edge IDs in the cut")
584
value = property(_get_value, doc="Sum of edge capacities in the cut")
585
586
587
class UniqueIdGenerator(object):
588
"""A dictionary-like class that can be used to assign unique IDs to
589
names (say, vertex names).
590
591
Usage:
592
593
>>> gen = UniqueIdGenerator()
594
>>> gen["A"]
595
0
596
>>> gen["B"]
597
1
598
>>> gen["C"]
599
2
600
>>> gen["A"] # Retrieving already existing ID
601
0
602
>>> gen.add("D") # Synonym of gen["D"]
603
3
604
>>> len(gen) # Number of already used IDs
605
4
606
"""
607
608
def __init__(self, id_generator=None, initial=None):
609
"""Creates a new unique ID generator. `id_generator` specifies how do we
610
assign new IDs to elements that do not have an ID yet. If it is `None`,
611
elements will be assigned integer identifiers starting from 0. If it is
612
an integer, elements will be assigned identifiers starting from the given
613
integer. If it is an iterator or generator, its `next` method will be
614
called every time a new ID is needed."""
615
if id_generator is None: id_generator = 0
616
if isinstance(id_generator, int):
617
import itertools
618
self._generator = itertools.count(id_generator)
619
else:
620
self._generator = id_generator
621
self._ids = {}
622
if initial:
623
for value in initial:
624
self.add(value)
625
626
def __getitem__(self, item):
627
"""Retrieves the ID corresponding to `item`. Generates a new ID for `item`
628
if it is the first time we request an ID for it."""
629
try:
630
return self._ids[item]
631
except KeyError:
632
self._ids[item] = self._generator.next()
633
return self._ids[item]
634
635
def __len__(self):
636
""""Returns the number of items"""
637
return len(self._ids)
638
639
def reverse_dict(self):
640
"""Returns the reverse mapping, i.e., the one that maps from generated
641
IDs to their corresponding objects"""
642
return dict((v, k) for k, v in self._ids.iteritems())
643
644
def values(self):
645
"""Returns the values stored so far. If the generator generates items
646
according to the standard sorting order, the values returned will be
647
exactly in the order they were added. This holds for integer IDs for
648
instance (but for many other ID generators as well)."""
649
return sorted(self._ids.keys(), key = lambda x: self._ids[x])
650
651
add = __getitem__
652
653
Loggerhead is a web-based interface for Breezy
Version: 2.0.1