This file is indexed.

/usr/lib/python2.7/dist-packages/igraph/layout.py is in python-igraph 0.7.1.post6-5.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
# vim:ts=4:sw=4:sts=4:et
# -*- coding: utf-8 -*-
"""
Layout-related code in the IGraph library.

This package contains the implementation of the L{Layout} object.
"""

from itertools import izip
from math import sin, cos, pi

from igraph.drawing.utils import BoundingBox
from igraph.statistics import RunningMean

__license__ = u"""\
Copyright (C) 2006-2012  Tamás Nepusz <ntamas@gmail.com>
Pázmány Péter sétány 1/a, 1117 Budapest, Hungary

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
02110-1301 USA
"""

class Layout(object):
    """Represents the layout of a graph.

    A layout is practically a list of coordinates in an n-dimensional
    space. This class is generic in the sense that it can store coordinates
    in any n-dimensional space.

    Layout objects are not associated directly with a graph. This is deliberate:
    there were times when I worked with almost identical copies of the same
    graph, the only difference was that they had different colors assigned to
    the vertices. It was particularly convenient for me to use the same layout
    for all of them, especially when I made figures for a paper. However,
    C{igraph} will of course refuse to draw a graph with a layout that has
    less coordinates than the node count of the graph.

    Layouts behave exactly like lists when they are accessed using the item
    index operator (C{[...]}). They can even be iterated through. Items
    returned by the index operator are only copies of the coordinates,
    but the stored coordinates can be modified by directly assigning to
    an index.

        >>> layout = Layout([(0, 1), (0, 2)])
        >>> coords = layout[1]
        >>> print coords
        [0, 2]
        >>> coords = (0, 3)
        >>> print layout[1]
        [0, 2]
        >>> layout[1] = coords
        >>> print layout[1]
        [0, 3]
    """
    
    def __init__(self, coords=None, dim=None):
        """Constructor.

        @param coords: the coordinates to be stored in the layout.
        @param dim: the number of dimensions. If C{None}, the number of
        dimensions is determined automatically from the length of the first
        item of the coordinate list. If there are no entries in the coordinate
        list, the default will be 2.  Generally, this should be given if the
        length of the coordinate list is zero, otherwise it should be left as
        is.
        """
        if coords:
            self._coords = [list(coord) for coord in coords]
        else:
            self._coords = []

        if dim is None:
            if len(self._coords) == 0:
                self._dim = 2
            else:
                self._dim = len(self._coords[0])
        else:
            self._dim = int(dim)
            for row in self._coords:
                if len(row) != self._dim:
                    raise ValueError("all items in the coordinate list "+
                                     "must have a length of %d" % self._dim)

    def __len__(self):
        return len(self._coords)

    def __getitem__(self, idx):
        return self._coords[idx]

    def __setitem__(self, idx, value):
        if len(value) != self._dim:
            raise ValueError("assigned item must have %d elements" % self._dim)
        self._coords[idx] = list(value)

    def __delitem__(self, idx):
        del self._coords[idx]

    def __copy__(self):
        return self.__class__(self.coords, self.dim)

    def __repr__(self):
        if not self.coords:
            vertex_count = "no vertices"
        elif len(self.coords) == 1:
            vertex_count = "1 vertex"
        else:
            vertex_count = "%d vertices" % len(self.coords)
        if self.dim == 1:
            dim_count = "1 dimension"
        else:
            dim_count = "%d dimensions" % self.dim
        return "<%s with %s and %s>" % (self.__class__.__name__,
                vertex_count, dim_count)

    @property
    def dim(self):
        """Returns the number of dimensions"""
        return self._dim

    @property
    def coords(self):
        """The coordinates as a list of lists"""
        return [row[:] for row in self._coords]

    def append(self, value):
        """Appends a new point to the layout"""
        if len(value) < self._dim:
            raise ValueError("appended item must have %d elements" % self._dim)
        self._coords.append([float(coord) for coord in value[0:self._dim]])

    def mirror(self, dim):
        """Mirrors the layout along the given dimension(s)

        @param dim: the list of dimensions or a single dimension
        """
        if isinstance(dim, int):
            dim = [dim]
        else:
            dim = [int(x) for x in dim]

        for current_dim in dim:
            for row in self._coords:
                row[current_dim] *= -1


    def rotate(self, angle, dim1=0, dim2=1, **kwds):
        """Rotates the layout by the given degrees on the plane defined by
        the given two dimensions.

        @param angle: the angle of the rotation, specified in degrees.
        @param dim1: the first axis of the plane of the rotation.
        @param dim2: the second axis of the plane of the rotation.
        @keyword origin: the origin of the rotation. If not specified, the
          origin will be the origin of the coordinate system.
        """

        origin = list(kwds.get("origin", [0.]*self._dim))
        if len(origin) != self._dim:
            raise ValueError("origin must have %d dimensions" % self._dim)

        radian = angle * pi / 180.
        cos_alpha, sin_alpha = cos(radian), sin(radian)
        
        for idx, row in enumerate(self._coords): 
            x, y = row[dim1] - origin[dim1], row[dim2] - origin[dim2]
            row[dim1] = cos_alpha*x - sin_alpha*y + origin[dim1]
            row[dim2] = sin_alpha*x + cos_alpha*y + origin[dim2]


    def scale(self, *args, **kwds):
        """Scales the layout.

        Scaling parameters can be provided either through the C{scale} keyword
        argument or through plain unnamed arguments. If a single integer or
        float is given, it is interpreted as a uniform multiplier to be applied
        on all dimensions. If it is a list or tuple, its length must be equal to
        the number of dimensions in the layout, and each element must be an
        integer or float describing the scaling coefficient in one of the
        dimensions.

        @keyword scale: scaling coefficients (integer, float, list or tuple)
        @keyword origin: the origin of scaling (this point will stay in place).
          Optional, defaults to the origin of the coordinate system being used.
        """
        origin = list(kwds.get("origin", [0.]*self._dim))
        if len(origin) != self._dim:
            raise ValueError("origin must have %d dimensions" % self._dim)

        scaling = kwds.get("scale") or args
        if isinstance(scaling, (int, float)):
            scaling = [scaling]
        if len(scaling) == 0:
            raise ValueError("scaling factor must be given")
        elif len(scaling) == 1:
            if type(scaling[0]) == int or type(scaling[0]) == float:
                scaling = scaling*self._dim
            else:
                scaling = scaling[0]
        if len(scaling) != self._dim:
            raise ValueError("scaling factor list must have %d elements" \
                    % self._dim)

        for idx, row in enumerate(self._coords):
            self._coords[idx] = [(row[d]-origin[d])*scaling[d]+origin[d] \
                                 for d in xrange(self._dim)]

    def translate(self, *args, **kwds):
        """Translates the layout.

        The translation vector can be provided either through the C{v} keyword
        argument or through plain unnamed arguments. If unnamed arguments are
        used, the vector can be supplied as a single list (or tuple) or just as
        a series of arguments. In all cases, the translation vector must have
        the same number of dimensions as the layout.

        @keyword v: the translation vector
        """
        v = kwds.get("v") or args
        if len(v) == 0:
            raise ValueError("translation vector must be given")
        elif len(v) == 1 and type(v[0]) != int and type(v[0]) != float:
            v = v[0]
        if len(v) != self._dim:
            raise ValueError("translation vector must have %d dimensions" \
                    % self._dim)

        for idx, row in enumerate(self._coords):
            self._coords[idx] = [row[d]+v[d] for d in xrange(self._dim)]


    def to_radial(self, min_angle = 100, max_angle = 80, \
        min_radius=0.0, max_radius=1.0):
        """Converts a planar layout to a radial one

        This method applies only to 2D layouts. The X coordinate of the
        layout is transformed to an angle, with min(x) corresponding to
        the parameter called I{min_angle} and max(y) corresponding to
        I{max_angle}. Angles are given in degrees, zero degree corresponds
        to the direction pointing upwards. The Y coordinate is
        interpreted as a radius, with min(y) belonging to the minimum and
        max(y) to the maximum radius given in the arguments.

        This is not a fully generic polar coordinate transformation, but
        it is fairly useful in creating radial tree layouts from ordinary
        top-down ones (that's why the Y coordinate belongs to the radius).
        It can also be used in conjunction with the Fruchterman-Reingold
        layout algorithm via its I{miny} and I{maxy} parameters (see
        L{Graph.layout_fruchterman_reingold}) to produce radial layouts
        where the radius belongs to some property of the vertices.

        @param min_angle: the angle corresponding to the minimum X value
        @param max_angle: the angle corresponding to the maximum X value
        @param min_radius: the radius corresponding to the minimum Y value
        @param max_radius: the radius corresponding to the maximum Y value
        """
        if self._dim != 2:
            raise TypeError("implemented only for 2D layouts")
        bbox = self.bounding_box()

        while min_angle > max_angle:
            max_angle += 360
        while min_angle > 360:
            min_angle -= 360
            max_angle -= 360
        while min_angle < 0:
            min_angle += 360
            max_angle += 360

        ratio_x = (max_angle - min_angle) / bbox.width
        ratio_x *= pi / 180.
        min_angle *= pi / 180.
        ratio_y = (max_radius - min_radius) / bbox.height
        for idx, (x, y) in enumerate(self._coords):
            alpha  = (x-bbox.left) * ratio_x + min_angle
            radius = (y-bbox.top) * ratio_y + min_radius
            self._coords[idx] = [cos(alpha)*radius, -sin(alpha)*radius]


    def transform(self, function, *args, **kwds):
        """Performs an arbitrary transformation on the layout

        Additional positional and keyword arguments are passed intact to
        the given function.

        @param function: a function which receives the coordinates as a
          tuple and returns the transformed tuple.
        """
        self._coords = [list(function(tuple(row), *args, **kwds)) \
            for row in self._coords]


    def centroid(self):
        """Returns the centroid of the layout.

        The centroid of the layout is the arithmetic mean of the points in
        the layout.
        
        @return: the centroid as a list of floats"""
        centroid = [RunningMean() for _ in xrange(self._dim)]
        for row in self._coords:
            for dim in xrange(self._dim):
                centroid[dim].add(row[dim])
        return [rm.mean for rm in centroid]

    def boundaries(self, border=0):
        """Returns the boundaries of the layout.

        The boundaries are the minimum and maximum coordinates along all
        dimensions.

        @param border: this value gets subtracted from the minimum bounds
          and gets added to the maximum bounds before returning the coordinates
          of the box. Defaults to zero.
        @return: the minimum and maximum coordinates along all dimensions,
          in a tuple containing two lists, one for the minimum coordinates,
          the other one for the maximum.
        @raises ValueError: if the layout contains no layout items
        """
        if not self._coords:
            raise ValueError("layout contains no layout items")

        mins, maxs = [], []
        for dim in xrange(self._dim):
            col = [row[dim] for row in self._coords]
            mins.append(min(col)-border)
            maxs.append(max(col)+border)
        return mins, maxs
        
    def bounding_box(self, border=0):
        """Returns the bounding box of the layout.

        The bounding box of the layout is the smallest box enclosing all the
        points in the layout.

        @param border: this value gets subtracted from the minimum bounds
          and gets added to the maximum bounds before returning the coordinates
          of the box. Defaults to zero.
        @return: the coordinates of the lower left and the upper right corner
          of the box. "Lower left" means the minimum coordinates and "upper right"
          means the maximum. These are encapsulated in a L{BoundingBox} object.
        """
        if self._dim != 2:
            raise ValueError("Layout.boundary_box() supports 2D layouts only")

        try:
            (x0, y0), (x1, y1) = self.boundaries(border)
            return BoundingBox(x0, y0, x1, y1)
        except ValueError:
            return BoundingBox(0, 0, 0, 0)


    def center(self, *args, **kwds):
        """Centers the layout around the given point.

        The point itself can be supplied as multiple unnamed arguments, as a
        simple unnamed list or as a keyword argument. This operation moves
        the centroid of the layout to the given point. If no point is supplied,
        defaults to the origin of the coordinate system.

        @keyword p: the point where the centroid of the layout will be after
          the operation."""
        center = kwds.get("p") or args
        if len(center) == 0:
            center = [0.] * self._dim
        elif len(center) == 1 and type(center[0]) != int \
            and type(center[0]) != float:
            center = center[0]
        if len(center) != self._dim:
            raise ValueError("the given point must have %d dimensions" \
                    % self._dim)
        centroid = self.centroid()
        vec = [center[d]-centroid[d] for d in xrange(self._dim)]
        self.translate(vec)


    def copy(self):
        """Creates an exact copy of the layout."""
        return self.__copy__()

    def fit_into(self, bbox, keep_aspect_ratio=True):
        """Fits the layout into the given bounding box.

        The layout will be modified in-place.

        @param bbox: the bounding box in which to fit the layout. If the
          dimension of the layout is d, it can either be a d-tuple (defining
          the sizes of the box), a 2d-tuple (defining the coordinates of the
          top left and the bottom right point of the box), or a L{BoundingBox}
          object (for 2D layouts only).
        @param keep_aspect_ratio: whether to keep the aspect ratio of the current
          layout. If C{False}, the layout will be rescaled to fit exactly into
          the bounding box. If C{True}, the original aspect ratio of the layout
          will be kept and it will be centered within the bounding box.
        """
        if isinstance(bbox, BoundingBox):
            if self._dim != 2:
                raise TypeError("bounding boxes work for 2D layouts only")
            corner, target_sizes = [bbox.left, bbox.top], [bbox.width, bbox.height]
        elif len(bbox) == self._dim:
            corner, target_sizes = [0.] * self._dim, list(bbox)
        elif len(bbox) == 2 * self._dim:
            corner, opposite_corner = list(bbox[0:self._dim]), list(bbox[self._dim:])
            for i in xrange(self._dim):
                if corner[i] > opposite_corner[i]:
                    corner[i], opposite_corner[i] = opposite_corner[i], corner[i]
            target_sizes = [max_val-min_val \
                    for min_val, max_val in izip(corner, opposite_corner)]

        try:
            mins, maxs = self.boundaries()
        except ValueError:
            mins, maxs = [0.0] * self._dim, [0.0] * self._dim
        sizes = [max_val - min_val for min_val, max_val in izip(mins, maxs)]

        for i, size in enumerate(sizes):
            if size == 0:
                sizes[i] = 2
                mins[i] -= 1
                maxs[i] += 1

        ratios = [float(target_size) / current_size \
                  for current_size, target_size in izip(sizes, target_sizes)]
        if keep_aspect_ratio:
            min_ratio = min(ratios)
            ratios = [min_ratio] * self._dim

        translations = []
        for i in xrange(self._dim):
            trans = (target_sizes[i] - ratios[i] * sizes[i]) / 2.
            trans -= mins[i] * ratios[i] - corner[i]
            translations.append(trans)

        self.scale(*ratios)
        self.translate(*translations)