Source code for toyplot.layout

# Copyright 2014, Sandia Corporation. Under the terms of Contract
# DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government retains certain
# rights in this software.

"""Provides layout algorithms.
"""


import time

import custom_inherit
import numpy

import toyplot.units

[docs]def region( xmin, xmax, ymin, ymax, bounds=None, rect=None, corner=None, grid=None, margin=None): """Specify a rectangular target region relative to a parent region. Parameters ---------- xmin: :class:`number<numbers.Number>`, required Minimum X boundary of the parent region, specified in CSS pixel units. xmax: :class:`number<numbers.Number>`, required Maximum X boundary of the parent region, specified in CSS pixel units. ymin: :class:`number<numbers.Number>`, required Minimum Y boundary of the parent region, specified in CSS pixel units. ymax: :class:`number<numbers.Number>`, required Maximum Y boundary of the parent region, specified in CSS pixel units. margin: :class:`number<numbers.Number>`, string, (:class:`number<numbers.Number>`, string) tuple, or tuple containing between one and four :class:`numbers<numbers.Number>`, strings, or (:class:`number<numbers.Number>`, string) tuples, optional Padding around the target region, specified in real-world units. Defaults to CSS pixel units. See :ref:`units` for details. Follows the same behavior as the CSS margin property. Returns ------- xmin, xmax, ymin, ymax: :class:`number<numbers.Number>` The boundaries of the target region, specified in CSS pixel units. """ if margin is None: margin = 0 if isinstance(margin, tuple): if len(margin) == 4: margin_top = toyplot.units.convert(margin[0], "px", default="px") margin_right = toyplot.units.convert(margin[1], "px", default="px") margin_bottom = toyplot.units.convert(margin[2], "px", default="px") margin_left = toyplot.units.convert(margin[3], "px", default="px") elif len(margin) == 3: margin_top = toyplot.units.convert(margin[0], "px", default="px") margin_left = margin_right = toyplot.units.convert(margin[1], "px", default="px") margin_bottom = toyplot.units.convert(margin[2], "px", default="px") elif len(margin) == 2: margin_top = margin_bottom = toyplot.units.convert(margin[0], "px", default="px") margin_left = margin_right = toyplot.units.convert(margin[1], "px", default="px") elif len(margin) == 1: margin_top = margin_bottom = margin_left = margin_right = toyplot.units.convert(margin[0], "px", default="px") else: margin_top = margin_bottom = margin_left = margin_right = toyplot.units.convert(margin, "px", default="px") def convert(vmin, vmax, value): value = toyplot.units.convert( value, "px", default="px", reference=vmax - vmin) if value < 0: return float(vmax + value) return float(vmin + value) # Specify explicit bounds for the region if bounds is not None: if isinstance(bounds, tuple) and len(bounds) == 4: return ( convert(xmin, xmax, bounds[0]), convert(xmin, xmax, bounds[1]), convert(ymin, ymax, bounds[2]), convert(ymin, ymax, bounds[3]), ) raise TypeError("bounds parameter must be an (xmin, xmax, ymin, ymax) tuple.") # pragma: no cover # Specify an explicit rectangle for the region if rect is not None: if isinstance(rect, tuple) and len(rect) == 4: x = convert(xmin, xmax, rect[0]) y = convert(ymin, ymax, rect[1]) width = toyplot.units.convert( rect[2], "px", default="px", reference=xmax - xmin) height = toyplot.units.convert( rect[3], "px", default="px", reference=ymax - ymin) return (x, x + width, y, y + height) raise ValueError("Unrecognized rect type") # pragma: no cover # Offset a rectangle from a corner if corner is not None: if isinstance(corner, tuple) and len(corner) == 4: position = corner[0] inset = toyplot.units.convert(corner[1], "px", default="px") width = toyplot.units.convert( corner[2], "px", default="px", reference=xmax - xmin) height = toyplot.units.convert( corner[3], "px", default="px", reference=ymax - ymin) else: raise ValueError("corner parameter must be a (corner, inset, width, height) tuple.") # pragma: no cover if position == "top": return ((xmin + xmax - width) / 2, (xmin + xmax + width) / 2, ymin + inset, ymin + inset + height) elif position == "top-right": return ( xmax - width - inset, xmax - inset, ymin + inset, ymin + inset + height) elif position == "right": return ( xmax - width - inset, xmax - inset, (ymin + ymax - height) / 2, (ymin + ymax + height) / 2) elif position == "bottom-right": return ( xmax - width - inset, xmax - inset, ymax - inset - height, ymax - inset) elif position == "bottom": return ((xmin + xmax - width) / 2, (xmin + xmax + width) / 2, ymax - inset - height, ymax - inset) elif position == "bottom-left": return ( xmin + inset, xmin + inset + width, ymax - inset - height, ymax - inset) elif position == "left": return ( xmin + inset, xmin + inset + width, (ymin + ymax - height) / 2, (ymin + ymax + height) / 2) elif position == "top-left": return ( xmin + inset, xmin + inset + width, ymin + inset, ymin + inset + height) else: raise ValueError("Unrecognized corner") # pragma: no cover # Choose a cell from an MxN grid, with optional column/row spanning. if grid is not None: # Cell n (in left-to-right, top-to-bottom order) of an M x N grid if len(grid) == 3: M, N, n = grid i = n // N j = n % N rowspan, colspan = (1, 1) elif len(grid) == 4: # Cell i,j of an M x N grid M, N, i, j = grid rowspan, colspan = (1, 1) # Cells [i, i+rowspan), [j, j+colspan) of an M x N grid elif len(grid) == 6: M, N, i, rowspan, j, colspan = grid cell_width = (xmax - xmin) / N cell_height = (ymax - ymin) / M return ( (j * cell_width) + margin_left, ((j + colspan) * cell_width) - margin_right, (i * cell_height) + margin_top, ((i + rowspan) * cell_height) - margin_bottom, ) # If nothing else fits, consume the entire region return (xmin + margin_left, xmax - margin_right, ymin + margin_top, ymax - margin_bottom)
[docs]class Graph(object): """Stores graph layout information. Typically used when sharing a layout among more than one graph. """ def __init__(self, vids, vcoordinates, edges, eshapes, ecoordinates): self._vids = vids self._vcoordinates = vcoordinates self._edges = edges self._eshapes = eshapes self._ecoordinates = ecoordinates @property def vcount(self): """Return the number of vertices :math:`V` in the graph.""" return len(self._vids) @property def vids(self): """Return :math:`V` graph vertex identifiers.""" return self._vids @property def vcoordinates(self): """Return graph vertex coordinates as a :math:`V \\times 2` matrix.""" return self._vcoordinates @property def ecount(self): """Return the number of edges :math:`E` in the graph.""" return len(self._edges) @property def eshapes(self): """Return a vector of :math:`E` string edge shapes.""" return self._eshapes @property def ecoordinates(self): """Return a matrix of edge coordinates. The number of coordinates is determined by the contents of the `eshapes` vector.""" return self._ecoordinates @property def edges(self): """Return the graph edges as a :math:`E \\times 2` matrix of source, target indices.""" return self._edges
[docs]def graph(a, b=None, c=None, olayout=None, layout=None, vcoordinates=None): """Compute a graph layout.""" stack = [c, b, a] # Identify the graph's edges. if isinstance(stack[-1], numpy.ndarray) and stack[-1].ndim == 2 and stack[-1].shape[1] == 2: edges = stack.pop() ecount = edges.shape[0] else: sources = toyplot.require.vector(stack.pop()) ecount = len(sources) targets = toyplot.require.vector(stack.pop(), ecount) edges = numpy.column_stack((sources, targets)) # Identify the vertex ids induced by the edges. vids, edges = numpy.unique(edges, return_inverse=True) edges = edges.reshape((ecount, 2), order="C") # If the caller supplied extra vertex ids, merge them in. if stack and stack[-1] is not None: extra_vids = toyplot.require.vector(stack.pop()) disconnected_vids = numpy.setdiff1d(extra_vids, vids) vids = numpy.append(vids, disconnected_vids) # Setup storage to receive vertex coordinates vcount = len(vids) ivcoordinates = numpy.ma.masked_all((vcount, 2)) # If the caller supplied the layout for an external graph, merge those coordinates in. if olayout is not None: olayout = toyplot.require.instance(olayout, (toyplot.mark.Graph, toyplot.layout.Graph)) oindices = numpy.in1d(olayout.vids, vids, assume_unique=True) iindices = numpy.in1d(vids, olayout.vids, assume_unique=True) ivcoordinates[iindices] = olayout.vcoordinates[oindices] # If the caller supplied extra vertex coordinates, merge them in. if vcoordinates is not None: external_vcoordinates = toyplot.require.scalar_matrix(vcoordinates, rows=vcount, columns=2) mask = numpy.ma.getmaskarray(external_vcoordinates) ivcoordinates = numpy.ma.where(mask, ivcoordinates, external_vcoordinates) # Apply the layout algorithm to whatever's left. start = time.time() if layout is None: # If there are unspecified coordinates, use a force-directed layout. if numpy.ma.is_masked(ivcoordinates): layout = toyplot.layout.FruchtermanReingold() else: # Otherwise, we can ignore the vertices and just create edges. layout = toyplot.layout.IgnoreVertices() vcoordinates, eshapes, ecoordinates = layout.graph(ivcoordinates, edges) toyplot.log.info("Graph layout time: %s ms", (time.time() - start) * 1000) if numpy.ma.is_masked(vcoordinates): raise RuntimeError("Graph layout cannot return masked vertex coordinates.") # pragma: no cover return Graph(vids, vcoordinates, edges, eshapes, ecoordinates)
def _add_at(target, target_indices, source): """Add source values to the target and handle duplicate indices correctly. With numpy, the expression `target[indices] += source` does not work intuitively if there are duplicate indices. This function handles this case as you would expect, by accumulating multiple values for a single target. """ if getattr(numpy.add, "at", None) is not None: numpy.add.at(target, target_indices, source) else: # Shim for numpy < 1.8 for source_index, target_index in enumerate(target_indices): # pragma: no cover target[target_index] += source[source_index] #def _floyd_warshall_shortest_path(vcount, edges): # """Compute the (directed) shortest paths between every pair of vertices in a graph, using the Floyd-Warshall algorithm. # # Floyd-Warshall is a good choice for computing paths between all pairs of # vertices in dense graphs. # # Note that this algorithm is directed, i.e. a path from i -> j doesn't imply # a path from j -> i. The results will contain numpy.inf for vertices that # have no path. # # Returns # ------- # shortest_paths: :math:`V \\times V matrix` # A matrix where element :math:`E_ij` contains the shortest path distance # between vertex :math:`i` and vertex :math:`j`. # """ # distance = numpy.empty((vcount, vcount)) # distance[...] = numpy.inf # distance[numpy.diag_indices_from(distance)] = 0 # distance[edges.T[0], edges.T[1]] = 1 # for k in numpy.arange(vcount): # for i in numpy.arange(vcount): # for j in numpy.arange(vcount): # if distance[i, j] > distance[i, k] + distance[k, j]: # distance[i, j] = distance[i, k] + distance[k, j] # # return distance def _adjacency_list(vcount, edges): """Return an adjacency list representation of a graph.""" targets = [[] for i in numpy.arange(vcount)] for source, target in edges: targets[source].append(target) return targets def _require_tree(children): """Return the root vertex and maximum depth of a tree. Parameters ---------- children: list of lists Adjacency list representation of a graph. Returns ------- root: integer Index of the root vertex. depth: integer Maximum depth of the tree. """ roots = numpy.setdiff1d(numpy.arange(len(children)), numpy.concatenate(children)) if len(roots) != 1: raise ValueError("Not a tree.") # pragma: no cover root = roots[0] depth = [] visited = numpy.zeros(len(children), dtype=bool) def mark_visited(vertex, vdepth=0): if visited[vertex]: raise ValueError("Not a tree.") # pragma: no cover depth.append(vdepth) visited[vertex] = True for child in children[vertex]: mark_visited(child, vdepth + 1) mark_visited(root) return root, max(depth)
[docs]class EdgeLayout(object, metaclass=custom_inherit.DocInheritMeta(style="numpy_napoleon")): """Abstract interface for algorithms that compute graph edge coordinates."""
[docs] def edges(self, vcoordinates, edges): """Return edge coordinates for a graph. Parameters ---------- vcoordinates : :math:`V \\times 2` matrix Contains the coordinates for every graph vertex, in vertex order. edges : :math:`E \\times 2` matrix Contains the integer vertex indices for every graph edge in edge order. The first and second matrix columns contain the source and target vertices respectively. Returns ------- eshapes : array of :math:`E` strings Contains a shape string for each edge, in edge order. The shape string contains drawing codes that define an arbitrary-complexity path for the edge, using a set of current coordinates and a turtle drawing model. The following codes are currently allowed: * `M` - change the current coordinates without drawing (requires one set of coordinates). * `L` - draw a straight line segment from the current coordinates (requires one set of coordinates). * `Q` - draw a quadratic Bezier curve from the current coordinates (requires two sets of coordinates). * `C` - draw a cubic Bezier curve from the current coordinates (requires three sets of coordinates). ecoordinates : matrix containing two columns Contains coordinates for each of the edge shape strings, in drawing-code order. """ raise NotImplementedError() # pragma: no cover
[docs]class StraightEdges(EdgeLayout): """Creates straight edges between graph vertices."""
[docs] def edges(self, vcoordinates, edges): loops = edges.T[0] == edges.T[1] if numpy.any(loops): toyplot.log.warning("Graph contains %s loop edges that will not be visible.", numpy.count_nonzero(loops)) eshapes = numpy.tile("ML", len(edges)) ecoordinates = numpy.empty((len(edges) * 2, 2)) ecoordinates[0::2] = vcoordinates[edges.T[0]] ecoordinates[1::2] = vcoordinates[edges.T[1]] return eshapes, ecoordinates
[docs]class CurvedEdges(EdgeLayout): """Creates curved edges between graph vertices. Parameters ---------- curvature : number Controls the curvature of each edge's arc, as a percentage of the distance between the edge's vertices. Use negative values to curve edges in the opposite direction. """ def __init__(self, curvature=0.15): self._curvature = curvature
[docs] def edges(self, vcoordinates, edges): loops = edges.T[0] == edges.T[1] if numpy.any(loops): toyplot.log.warning("Graph contains %s loop edges that will not be visible.", numpy.count_nonzero(loops)) eshapes = numpy.tile("MQ", len(edges)) ecoordinates = numpy.empty((len(edges) * 3, 2)) sources = vcoordinates[edges.T[0]] targets = vcoordinates[edges.T[1]] offsets = numpy.dot(targets - sources, [[0, 1], [-1, 0]]) * self._curvature midpoints = ((sources + targets) * 0.5) + offsets ecoordinates[0::3] = sources ecoordinates[1::3] = midpoints ecoordinates[2::3] = targets return eshapes, ecoordinates
[docs]class GraphLayout(object, metaclass=custom_inherit.DocInheritMeta(style="numpy_napoleon")): """Abstract interface for algorithms that compute coordinates for graph vertices and edges."""
[docs] def graph(self, vcoordinates, edges): """Compute vertex and edge coordinates for a graph. Parameters ---------- vcoordinates : :math:`V \\times 2` masked array Coordinates for every graph vertex, in vertex order. Where practical, only masked coordinates will have values assigned by the underlying algorithm. edges : :math:`E \\times 2` matrix Contains the integer vertex indices for every graph edge in edge order. The first and second matrix columns contain the source and target vertices respectively. Returns ------- vcoordinates : :math:`V \\times 2` matrix Contains coordinates for every graph vertex, in vertex order. eshapes : array of :math:`E` strings Contains a shape string for each edge, in edge order. The shape string contains drawing codes that define an arbitrary-complexity path for the edge, using a set of current coordinates and a turtle drawing model. The following codes are currently allowed: * `M` - change the current coordinates without drawing (requires one set of coordinates). * `L` - draw a straight line segment (requires one set of coordinates). * `Q` - draw a quadratic Bezier curve (requires two sets of coordinates). * `C` - draw a cubic Bezier curve (requires three sets of coordinates). ecoordinates : matrix containing two columns Contains coordinates for each of the edge shape strings, in drawing-code order. """ raise NotImplementedError() # pragma: no cover
[docs]class IgnoreVertices(GraphLayout): """Do-nothing graph layout for use when all vertices are already specified. Parameters ---------- edges: :class:`toyplot.layout.EdgeLayout` instance, optional The default will generate straight edges. """ def __init__(self, edges=None): if edges is None: edges = StraightEdges() self._edges = edges
[docs] def graph(self, vcoordinates, edges): eshapes, ecoordinates = self._edges.edges(vcoordinates, edges) return vcoordinates, eshapes, ecoordinates
[docs]class Random(GraphLayout): """Compute a random graph layout. Parameters ---------- edges: :class:`toyplot.layout.EdgeLayout` instance, optional The default will generate straight edges. seed: integer, optional Random seed used to generate vertex coordinates. """ def __init__(self, edges=None, seed=1234): if edges is None: edges = StraightEdges() self._edges = edges self._seed = seed
[docs] def graph(self, vcoordinates, edges): generator = numpy.random.RandomState(seed=self._seed) mask = numpy.ma.getmaskarray(vcoordinates) vcoordinates = numpy.ma.where(mask, generator.uniform(-1, 1, size=vcoordinates.shape), vcoordinates) eshapes, ecoordinates = self._edges.edges(vcoordinates, edges) return vcoordinates, eshapes, ecoordinates
[docs]class Eades(GraphLayout): """Compute a force directed graph layout using the 1984 algorithm of Eades. Parameters ---------- edges: :class:`toyplot.layout.EdgeLayout` instance, optional The default will generate straight edges. c1, c2, c3, c4: numbers, optional Constants defined in Eades' original paper. M: integer, optional Number of iterations to run the spring simulation. seed: integer, optional Random seed used to initialize vertex coordinates. """ def __init__(self, edges=None, c1=2, c2=1, c3=1, c4=0.1, M=100, seed=1234): if edges is None: edges = StraightEdges() self._edges = edges self._c1 = c1 self._c2 = c2 self._c3 = c3 self._c4 = c4 self._M = M self._seed = seed
[docs] def graph(self, vcoordinates, edges): generator = numpy.random.RandomState(seed=self._seed) # Initialize coordinates mask = numpy.ma.getmaskarray(vcoordinates) vcoordinates = numpy.ma.where(mask, generator.uniform(-1, 1, size=vcoordinates.shape), vcoordinates) # Repeatedly apply attract / repel forces to the vertices vertices = numpy.column_stack(numpy.triu_indices(n=len(vcoordinates), k=1)) for iteration in numpy.arange(self._M): offsets = numpy.zeros_like(vcoordinates) # Repel a = vcoordinates[vertices.T[0]] b = vcoordinates[vertices.T[1]] delta = a - b distance = numpy.linalg.norm(delta, axis=1)[:, None] delta /= distance force = self._c3 / numpy.square(distance) delta *= force _add_at(offsets, vertices.T[0], delta) _add_at(offsets, vertices.T[1], -delta) # Attract a = vcoordinates[edges.T[0]] b = vcoordinates[edges.T[1]] delta = b - a distance = numpy.linalg.norm(delta, axis=1)[:, None] delta /= distance force = self._c1 * numpy.log(distance / self._c2) delta *= force _add_at(offsets, edges.T[0], delta) _add_at(offsets, edges.T[1], -delta) # Sum offsets vcoordinates = numpy.ma.where(mask, vcoordinates + self._c4 * offsets, vcoordinates) eshapes, ecoordinates = self._edges.edges(vcoordinates, edges) return vcoordinates, eshapes, ecoordinates
[docs]class FruchtermanReingold(GraphLayout): """Compute a force directed graph layout using the 1991 algorithm of Fruchterman and Reingold. Parameters ---------- edges: :class:`toyplot.layout.EdgeLayout` instance, optional The default will generate straight edges. area, temperature: numbers, optional Constants defined in the original paper. M: integer, optional Number of iterations to run the spring simulation. seed: integer, optional Random seed used to initialize vertex coordinates. """ def __init__(self, edges=None, area=1, temperature=0.1, M=50, seed=1234): if edges is None: edges = StraightEdges() self._edges = edges self._area = area self._temperature = temperature self._M = M self._seed = seed
[docs] def graph(self, vcoordinates, edges): generator = numpy.random.RandomState(seed=self._seed) # Setup parameters k = numpy.sqrt(self._area / len(vcoordinates)) # Initialize coordinates mask = numpy.ma.getmaskarray(vcoordinates) vcoordinates = numpy.ma.where(mask, generator.uniform(-1, 1, size=vcoordinates.shape), vcoordinates) # Repeatedly apply attract / repel forces to the vertices vertices = numpy.column_stack(numpy.triu_indices(n=len(vcoordinates), k=1)) for temperature in numpy.linspace(self._temperature, 0, self._M, endpoint=False): offsets = numpy.zeros_like(vcoordinates) # Repel a = vcoordinates[vertices.T[0]] b = vcoordinates[vertices.T[1]] delta = a - b distance = numpy.linalg.norm(delta, axis=1)[:, None] delta /= distance force = numpy.square(k) / distance delta *= force _add_at(offsets, vertices.T[0], +delta) _add_at(offsets, vertices.T[1], -delta) # Attract a = vcoordinates[edges.T[0]] b = vcoordinates[edges.T[1]] delta = b - a distance = numpy.linalg.norm(delta, axis=1)[:, None] delta /= distance force = numpy.square(distance) / k delta *= force _add_at(offsets, edges.T[0], +delta) _add_at(offsets, edges.T[1], -delta) # Limit offsets to the temperature distance = numpy.linalg.norm(offsets, axis=1) offsets /= distance[:, None] offsets *= numpy.minimum(temperature, distance)[:, None] # Sum offsets vcoordinates = numpy.ma.where(mask, vcoordinates + offsets, vcoordinates) eshapes, ecoordinates = self._edges.edges(vcoordinates, edges) return vcoordinates, eshapes, ecoordinates
[docs]class Buchheim(GraphLayout): """Compute a tree layout using the 2002 algorithm of Buchheim, Junger, and Leipert. Note: this layout currently ignores preexisting vertex coordinates. """ def __init__(self, edges=None, basis=None): if edges is None: edges = StraightEdges() if basis is None: basis = [[1, 0], [0, -1]] self._edges = edges self._basis = numpy.array(basis)
[docs] def graph(self, vcoordinates, edges): # Convert the graph to an adjacency list children = _adjacency_list(len(vcoordinates), edges) # Ensure we actually have a tree root, depth = _require_tree(children) # Get rid of the mask, it complicates things. vcoordinates = numpy.array(vcoordinates) # Convert our flat adjacency list into a hierarchy, to make the implementation easier. class Vertex(object): def __init__(self, vertex, parent=None, number=0, depth=0): self.vertex = vertex self.parent = parent self.number = number self.depth = depth self.children = [Vertex(child, self, number, depth+1) for number, child in enumerate(children[vertex])] self.mod = 0 self.thread = None self.ancestor = self self.prelim = 0 self.change = 0 self.shift = 0 # We follow Appendix A of the original paper as closely as possible here. distance = 1 def FirstWalk(v): if not v.children: # v is a leaf v.prelim = 0 if v.number: # v has a left sibling v.prelim = v.parent.children[v.number-1].prelim + distance else: # v is not a leaf defaultAncestor = v.children[0] # leftmost child of v for w in v.children: FirstWalk(w) defaultAncestor = Apportion(w, defaultAncestor) ExecuteShifts(v) midpoint = 0.5 * (v.children[0].prelim + v.children[-1].prelim) if v.number: # v has a left sibling v.prelim = v.parent.children[v.number-1].prelim + distance v.mod = v.prelim - midpoint else: v.prelim = midpoint def Apportion(v, defaultAncestor): if v.number: # v has a left sibling vip = vop = v vim = v.parent.children[v.number-1] vom = vip.parent.children[0] sip = vip.mod sop = vop.mod sim = vim.mod som = vom.mod while NextRight(vim) and NextLeft(vip): vim = NextRight(vim) vip = NextLeft(vip) vom = NextLeft(vom) vop = NextRight(vop) vop.ancestor = v shift = (vim.prelim + sim) - (vip.prelim + sip) + distance if shift > 0: MoveSubtree(Ancestor(vim, v, defaultAncestor), v, shift) sip += shift sop += shift sim += vim.mod sip += vip.mod som += vom.mod sop += vop.mod if NextRight(vim) and not NextRight(vop): vop.thread = NextRight(vim) vop.mod += sim - sop if NextLeft(vip) and not NextLeft(vom): vom.thread = NextLeft(vip) vom.mod += sip - som defaultAncestor = v return defaultAncestor def NextLeft(v): if v.children: return v.children[0] else: return v.thread def NextRight(v): if v.children: return v.children[-1] else: return v.thread def MoveSubtree(wm, wp, shift): subtrees = wp.number - wm.number wp.change -= shift / subtrees wp.shift += shift wm.change += shift / subtrees wp.prelim += shift wp.mod += shift def ExecuteShifts(v): shift = 0 change = 0 for w in v.children: w.prelim += shift w.mod += shift change += w.change shift += w.shift + change def Ancestor(vim, v, defaultAncestor): if vim.ancestor in v.parent.children: return vim.ancestor else: return defaultAncestor def SecondWalk(v, m): vcoordinates[v.vertex][0] = v.prelim + m vcoordinates[v.vertex][1] = v.depth for w in v.children: SecondWalk(w, m + v.mod) r = Vertex(root) FirstWalk(r) SecondWalk(r, -r.prelim) vcoordinates = numpy.dot(vcoordinates, self._basis) eshapes, ecoordinates = self._edges.edges(vcoordinates, edges) return vcoordinates, eshapes, ecoordinates