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

# 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)