summaryrefslogtreecommitdiff
path: root/src/js/layout/mxCompactTreeLayout.js
diff options
context:
space:
mode:
Diffstat (limited to 'src/js/layout/mxCompactTreeLayout.js')
-rw-r--r--src/js/layout/mxCompactTreeLayout.js995
1 files changed, 0 insertions, 995 deletions
diff --git a/src/js/layout/mxCompactTreeLayout.js b/src/js/layout/mxCompactTreeLayout.js
deleted file mode 100644
index db6324c..0000000
--- a/src/js/layout/mxCompactTreeLayout.js
+++ /dev/null
@@ -1,995 +0,0 @@
-/**
- * $Id: mxCompactTreeLayout.js,v 1.57 2012-05-24 13:09:34 david Exp $
- * Copyright (c) 2006-2010, JGraph Ltd
- */
-/**
- * Class: mxCompactTreeLayout
- *
- * Extends <mxGraphLayout> to implement a compact tree (Moen) algorithm. This
- * layout is suitable for graphs that have no cycles (trees). Vertices that are
- * not connected to the tree will be ignored by this layout.
- *
- * Example:
- *
- * (code)
- * var layout = new mxCompactTreeLayout(graph);
- * layout.execute(graph.getDefaultParent());
- * (end)
- *
- * Constructor: mxCompactTreeLayout
- *
- * Constructs a new compact tree layout for the specified graph
- * and orientation.
- */
-function mxCompactTreeLayout(graph, horizontal, invert)
-{
- mxGraphLayout.call(this, graph);
- this.horizontal = (horizontal != null) ? horizontal : true;
- this.invert = (invert != null) ? invert : false;
-};
-
-/**
- * Extends mxGraphLayout.
- */
-mxCompactTreeLayout.prototype = new mxGraphLayout();
-mxCompactTreeLayout.prototype.constructor = mxCompactTreeLayout;
-
-/**
- * Variable: horizontal
- *
- * Specifies the orientation of the layout. Default is true.
- */
-mxCompactTreeLayout.prototype.horizontal = null;
-
-/**
- * Variable: invert
- *
- * Specifies if edge directions should be inverted. Default is false.
- */
-mxCompactTreeLayout.prototype.invert = null;
-
-/**
- * Variable: resizeParent
- *
- * If the parents should be resized to match the width/height of the
- * children. Default is true.
- */
-mxCompactTreeLayout.prototype.resizeParent = true;
-
-/**
- * Variable: groupPadding
- *
- * Padding added to resized parents
- */
-mxCompactTreeLayout.prototype.groupPadding = 10;
-
-/**
- * Variable: parentsChanged
- *
- * A set of the parents that need updating based on children
- * process as part of the layout
- */
-mxCompactTreeLayout.prototype.parentsChanged = null;
-
-/**
- * Variable: moveTree
- *
- * Specifies if the tree should be moved to the top, left corner
- * if it is inside a top-level layer. Default is false.
- */
-mxCompactTreeLayout.prototype.moveTree = false;
-
-/**
- * Variable: levelDistance
- *
- * Holds the levelDistance. Default is 10.
- */
-mxCompactTreeLayout.prototype.levelDistance = 10;
-
-/**
- * Variable: nodeDistance
- *
- * Holds the nodeDistance. Default is 20.
- */
-mxCompactTreeLayout.prototype.nodeDistance = 20;
-
-/**
- * Variable: resetEdges
- *
- * Specifies if all edge points of traversed edges should be removed.
- * Default is true.
- */
-mxCompactTreeLayout.prototype.resetEdges = true;
-
-/**
- * Variable: prefHozEdgeSep
- *
- * The preferred horizontal distance between edges exiting a vertex
- */
-mxCompactTreeLayout.prototype.prefHozEdgeSep = 5;
-
-/**
- * Variable: prefVertEdgeOff
- *
- * The preferred vertical offset between edges exiting a vertex
- */
-mxCompactTreeLayout.prototype.prefVertEdgeOff = 4;
-
-/**
- * Variable: minEdgeJetty
- *
- * The minimum distance for an edge jetty from a vertex
- */
-mxCompactTreeLayout.prototype.minEdgeJetty = 8;
-
-/**
- * Variable: channelBuffer
- *
- * The size of the vertical buffer in the center of inter-rank channels
- * where edge control points should not be placed
- */
-mxCompactTreeLayout.prototype.channelBuffer = 4;
-
-/**
- * Variable: edgeRouting
- *
- * Whether or not to apply the internal tree edge routing
- */
-mxCompactTreeLayout.prototype.edgeRouting = true;
-
-/**
- * Function: isVertexIgnored
- *
- * Returns a boolean indicating if the given <mxCell> should be ignored as a
- * vertex. This returns true if the cell has no connections.
- *
- * Parameters:
- *
- * vertex - <mxCell> whose ignored state should be returned.
- */
-mxCompactTreeLayout.prototype.isVertexIgnored = function(vertex)
-{
- return mxGraphLayout.prototype.isVertexIgnored.apply(this, arguments) ||
- this.graph.getConnections(vertex).length == 0;
-};
-
-/**
- * Function: isHorizontal
- *
- * Returns <horizontal>.
- */
-mxCompactTreeLayout.prototype.isHorizontal = function()
-{
- return this.horizontal;
-};
-
-/**
- * Function: execute
- *
- * Implements <mxGraphLayout.execute>.
- *
- * If the parent has any connected edges, then it is used as the root of
- * the tree. Else, <mxGraph.findTreeRoots> will be used to find a suitable
- * root node within the set of children of the given parent.
- *
- * Parameters:
- *
- * parent - <mxCell> whose children should be laid out.
- * root - Optional <mxCell> that will be used as the root of the tree.
- */
-mxCompactTreeLayout.prototype.execute = function(parent, root)
-{
- this.parent = parent;
- var model = this.graph.getModel();
-
- if (root == null)
- {
- // Takes the parent as the root if it has outgoing edges
- if (this.graph.getEdges(parent, model.getParent(parent),
- this.invert, !this.invert, false).length > 0)
- {
- root = parent;
- }
-
- // Tries to find a suitable root in the parent's
- // children
- else
- {
- var roots = this.graph.findTreeRoots(parent, true, this.invert);
-
- if (roots.length > 0)
- {
- for (var i = 0; i < roots.length; i++)
- {
- if (!this.isVertexIgnored(roots[i]) &&
- this.graph.getEdges(roots[i], null,
- this.invert, !this.invert, false).length > 0)
- {
- root = roots[i];
- break;
- }
- }
- }
- }
- }
-
- if (root != null)
- {
- if (this.resizeParent)
- {
- this.parentsChanged = new Object();
- }
- else
- {
- this.parentsChanged = null;
- }
-
- model.beginUpdate();
-
- try
- {
- var node = this.dfs(root, parent);
-
- if (node != null)
- {
- this.layout(node);
- var x0 = this.graph.gridSize;
- var y0 = x0;
-
- if (!this.moveTree)
- {
- var g = this.getVertexBounds(root);
-
- if (g != null)
- {
- x0 = g.x;
- y0 = g.y;
- }
- }
-
- var bounds = null;
-
- if (this.isHorizontal())
- {
- bounds = this.horizontalLayout(node, x0, y0);
- }
- else
- {
- bounds = this.verticalLayout(node, null, x0, y0);
- }
-
- if (bounds != null)
- {
- var dx = 0;
- var dy = 0;
-
- if (bounds.x < 0)
- {
- dx = Math.abs(x0 - bounds.x);
- }
-
- if (bounds.y < 0)
- {
- dy = Math.abs(y0 - bounds.y);
- }
-
- if (dx != 0 || dy != 0)
- {
- this.moveNode(node, dx, dy);
- }
-
- if (this.resizeParent)
- {
- this.adjustParents();
- }
-
- if (this.edgeRouting)
- {
- // Iterate through all edges setting their positions
- this.localEdgeProcessing(node);
- }
- }
- }
- }
- finally
- {
- model.endUpdate();
- }
- }
-};
-
-/**
- * Function: moveNode
- *
- * Moves the specified node and all of its children by the given amount.
- */
-mxCompactTreeLayout.prototype.moveNode = function(node, dx, dy)
-{
- node.x += dx;
- node.y += dy;
- this.apply(node);
-
- var child = node.child;
-
- while (child != null)
- {
- this.moveNode(child, dx, dy);
- child = child.next;
- }
-};
-
-/**
- * Function: dfs
- *
- * Does a depth first search starting at the specified cell.
- * Makes sure the specified parent is never left by the
- * algorithm.
- */
-mxCompactTreeLayout.prototype.dfs = function(cell, parent, visited)
-{
- visited = (visited != null) ? visited : [];
-
- var id = mxCellPath.create(cell);
- var node = null;
-
- if (cell != null && visited[id] == null && !this.isVertexIgnored(cell))
- {
- visited[id] = cell;
- node = this.createNode(cell);
-
- var model = this.graph.getModel();
- var prev = null;
- var out = this.graph.getEdges(cell, parent, this.invert, !this.invert, false, true);
- var view = this.graph.getView();
-
- for (var i = 0; i < out.length; i++)
- {
- var edge = out[i];
-
- if (!this.isEdgeIgnored(edge))
- {
- // Resets the points on the traversed edge
- if (this.resetEdges)
- {
- this.setEdgePoints(edge, null);
- }
-
- if (this.edgeRouting)
- {
- this.setEdgeStyleEnabled(edge, false);
- this.setEdgePoints(edge, null);
- }
-
- // Checks if terminal in same swimlane
- var state = view.getState(edge);
- var target = (state != null) ? state.getVisibleTerminal(this.invert) : view.getVisibleTerminal(edge, this.invert);
- var tmp = this.dfs(target, parent, visited);
-
- if (tmp != null && model.getGeometry(target) != null)
- {
- if (prev == null)
- {
- node.child = tmp;
- }
- else
- {
- prev.next = tmp;
- }
-
- prev = tmp;
- }
- }
- }
- }
-
- return node;
-};
-
-/**
- * Function: layout
- *
- * Starts the actual compact tree layout algorithm
- * at the given node.
- */
-mxCompactTreeLayout.prototype.layout = function(node)
-{
- if (node != null)
- {
- var child = node.child;
-
- while (child != null)
- {
- this.layout(child);
- child = child.next;
- }
-
- if (node.child != null)
- {
- this.attachParent(node, this.join(node));
- }
- else
- {
- this.layoutLeaf(node);
- }
- }
-};
-
-/**
- * Function: horizontalLayout
- */
-mxCompactTreeLayout.prototype.horizontalLayout = function(node, x0, y0, bounds)
-{
- node.x += x0 + node.offsetX;
- node.y += y0 + node.offsetY;
- bounds = this.apply(node, bounds);
- var child = node.child;
-
- if (child != null)
- {
- bounds = this.horizontalLayout(child, node.x, node.y, bounds);
- var siblingOffset = node.y + child.offsetY;
- var s = child.next;
-
- while (s != null)
- {
- bounds = this.horizontalLayout(s, node.x + child.offsetX, siblingOffset, bounds);
- siblingOffset += s.offsetY;
- s = s.next;
- }
- }
-
- return bounds;
-};
-
-/**
- * Function: verticalLayout
- */
-mxCompactTreeLayout.prototype.verticalLayout = function(node, parent, x0, y0, bounds)
-{
- node.x += x0 + node.offsetY;
- node.y += y0 + node.offsetX;
- bounds = this.apply(node, bounds);
- var child = node.child;
-
- if (child != null)
- {
- bounds = this.verticalLayout(child, node, node.x, node.y, bounds);
- var siblingOffset = node.x + child.offsetY;
- var s = child.next;
-
- while (s != null)
- {
- bounds = this.verticalLayout(s, node, siblingOffset, node.y + child.offsetX, bounds);
- siblingOffset += s.offsetY;
- s = s.next;
- }
- }
-
- return bounds;
-};
-
-/**
- * Function: attachParent
- */
-mxCompactTreeLayout.prototype.attachParent = function(node, height)
-{
- var x = this.nodeDistance + this.levelDistance;
- var y2 = (height - node.width) / 2 - this.nodeDistance;
- var y1 = y2 + node.width + 2 * this.nodeDistance - height;
-
- node.child.offsetX = x + node.height;
- node.child.offsetY = y1;
-
- node.contour.upperHead = this.createLine(node.height, 0,
- this.createLine(x, y1, node.contour.upperHead));
- node.contour.lowerHead = this.createLine(node.height, 0,
- this.createLine(x, y2, node.contour.lowerHead));
-};
-
-/**
- * Function: layoutLeaf
- */
-mxCompactTreeLayout.prototype.layoutLeaf = function(node)
-{
- var dist = 2 * this.nodeDistance;
-
- node.contour.upperTail = this.createLine(
- node.height + dist, 0);
- node.contour.upperHead = node.contour.upperTail;
- node.contour.lowerTail = this.createLine(
- 0, -node.width - dist);
- node.contour.lowerHead = this.createLine(
- node.height + dist, 0, node.contour.lowerTail);
-};
-
-/**
- * Function: join
- */
-mxCompactTreeLayout.prototype.join = function(node)
-{
- var dist = 2 * this.nodeDistance;
-
- var child = node.child;
- node.contour = child.contour;
- var h = child.width + dist;
- var sum = h;
- child = child.next;
-
- while (child != null)
- {
- var d = this.merge(node.contour, child.contour);
- child.offsetY = d + h;
- child.offsetX = 0;
- h = child.width + dist;
- sum += d + h;
- child = child.next;
- }
-
- return sum;
-};
-
-/**
- * Function: merge
- */
-mxCompactTreeLayout.prototype.merge = function(p1, p2)
-{
- var x = 0;
- var y = 0;
- var total = 0;
-
- var upper = p1.lowerHead;
- var lower = p2.upperHead;
-
- while (lower != null && upper != null)
- {
- var d = this.offset(x, y, lower.dx, lower.dy,
- upper.dx, upper.dy);
- y += d;
- total += d;
-
- if (x + lower.dx <= upper.dx)
- {
- x += lower.dx;
- y += lower.dy;
- lower = lower.next;
- }
- else
- {
- x -= upper.dx;
- y -= upper.dy;
- upper = upper.next;
- }
- }
-
- if (lower != null)
- {
- var b = this.bridge(p1.upperTail, 0, 0, lower, x, y);
- p1.upperTail = (b.next != null) ? p2.upperTail : b;
- p1.lowerTail = p2.lowerTail;
- }
- else
- {
- var b = this.bridge(p2.lowerTail, x, y, upper, 0, 0);
-
- if (b.next == null)
- {
- p1.lowerTail = b;
- }
- }
-
- p1.lowerHead = p2.lowerHead;
-
- return total;
-};
-
-/**
- * Function: offset
- */
-mxCompactTreeLayout.prototype.offset = function(p1, p2, a1, a2, b1, b2)
-{
- var d = 0;
-
- if (b1 <= p1 || p1 + a1 <= 0)
- {
- return 0;
- }
-
- var t = b1 * a2 - a1 * b2;
-
- if (t > 0)
- {
- if (p1 < 0)
- {
- var s = p1 * a2;
- d = s / a1 - p2;
- }
- else if (p1 > 0)
- {
- var s = p1 * b2;
- d = s / b1 - p2;
- }
- else
- {
- d = -p2;
- }
- }
- else if (b1 < p1 + a1)
- {
- var s = (b1 - p1) * a2;
- d = b2 - (p2 + s / a1);
- }
- else if (b1 > p1 + a1)
- {
- var s = (a1 + p1) * b2;
- d = s / b1 - (p2 + a2);
- }
- else
- {
- d = b2 - (p2 + a2);
- }
-
- if (d > 0)
- {
- return d;
- }
- else
- {
- return 0;
- }
-};
-
-/**
- * Function: bridge
- */
-mxCompactTreeLayout.prototype.bridge = function(line1, x1, y1, line2, x2, y2)
-{
- var dx = x2 + line2.dx - x1;
- var dy = 0;
- var s = 0;
-
- if (line2.dx == 0)
- {
- dy = line2.dy;
- }
- else
- {
- s = dx * line2.dy;
- dy = s / line2.dx;
- }
-
- var r = this.createLine(dx, dy, line2.next);
- line1.next = this.createLine(0, y2 + line2.dy - dy - y1, r);
-
- return r;
-};
-
-/**
- * Function: createNode
- */
-mxCompactTreeLayout.prototype.createNode = function(cell)
-{
- var node = new Object();
- node.cell = cell;
- node.x = 0;
- node.y = 0;
- node.width = 0;
- node.height = 0;
-
- var geo = this.getVertexBounds(cell);
-
- if (geo != null)
- {
- if (this.isHorizontal())
- {
- node.width = geo.height;
- node.height = geo.width;
- }
- else
- {
- node.width = geo.width;
- node.height = geo.height;
- }
- }
-
- node.offsetX = 0;
- node.offsetY = 0;
- node.contour = new Object();
-
- return node;
-};
-
-/**
- * Function: apply
- */
-mxCompactTreeLayout.prototype.apply = function(node, bounds)
-{
- var model = this.graph.getModel();
- var cell = node.cell;
- var g = model.getGeometry(cell);
-
- if (cell != null && g != null)
- {
- if (this.isVertexMovable(cell))
- {
- g = this.setVertexLocation(cell, node.x, node.y);
-
- if (this.resizeParent)
- {
- var parent = model.getParent(cell);
- var id = mxCellPath.create(parent);
-
- // Implements set semantic
- if (this.parentsChanged[id] == null)
- {
- this.parentsChanged[id] = parent;
- }
- }
- }
-
- if (bounds == null)
- {
- bounds = new mxRectangle(g.x, g.y, g.width, g.height);
- }
- else
- {
- bounds = new mxRectangle(Math.min(bounds.x, g.x),
- Math.min(bounds.y, g.y),
- Math.max(bounds.x + bounds.width, g.x + g.width),
- Math.max(bounds.y + bounds.height, g.y + g.height));
- }
- }
-
- return bounds;
-};
-
-/**
- * Function: createLine
- */
-mxCompactTreeLayout.prototype.createLine = function(dx, dy, next)
-{
- var line = new Object();
- line.dx = dx;
- line.dy = dy;
- line.next = next;
-
- return line;
-};
-
-/**
- * Function: adjustParents
- *
- * Adjust parent cells whose child geometries have changed. The default
- * implementation adjusts the group to just fit around the children with
- * a padding.
- */
-mxCompactTreeLayout.prototype.adjustParents = function()
-{
- var tmp = [];
-
- for (var id in this.parentsChanged)
- {
- tmp.push(this.parentsChanged[id]);
- }
-
- this.arrangeGroups(mxUtils.sortCells(tmp, true), this.groupPadding);
-};
-
-/**
- * Function: localEdgeProcessing
- *
- * Moves the specified node and all of its children by the given amount.
- */
-mxCompactTreeLayout.prototype.localEdgeProcessing = function(node)
-{
- this.processNodeOutgoing(node);
- var child = node.child;
-
- while (child != null)
- {
- this.localEdgeProcessing(child);
- child = child.next;
- }
-};
-
-/**
- * Function: localEdgeProcessing
- *
- * Separates the x position of edges as they connect to vertices
- */
-mxCompactTreeLayout.prototype.processNodeOutgoing = function(node)
-{
- var child = node.child;
- var parentCell = node.cell;
-
- var childCount = 0;
- var sortedCells = [];
-
- while (child != null)
- {
- childCount++;
-
- var sortingCriterion = child.x;
-
- if (this.horizontal)
- {
- sortingCriterion = child.y;
- }
-
- sortedCells.push(new WeightedCellSorter(child, sortingCriterion));
- child = child.next;
- }
-
- sortedCells.sort(WeightedCellSorter.prototype.compare);
-
- var availableWidth = node.width;
-
- var requiredWidth = (childCount + 1) * this.prefHozEdgeSep;
-
- // Add a buffer on the edges of the vertex if the edge count allows
- if (availableWidth > requiredWidth + (2 * this.prefHozEdgeSep))
- {
- availableWidth -= 2 * this.prefHozEdgeSep;
- }
-
- var edgeSpacing = availableWidth / childCount;
-
- var currentXOffset = edgeSpacing / 2.0;
-
- if (availableWidth > requiredWidth + (2 * this.prefHozEdgeSep))
- {
- currentXOffset += this.prefHozEdgeSep;
- }
-
- var currentYOffset = this.minEdgeJetty - this.prefVertEdgeOff;
- var maxYOffset = 0;
-
- var parentBounds = this.getVertexBounds(parentCell);
- child = node.child;
-
- for (var j = 0; j < sortedCells.length; j++)
- {
- var childCell = sortedCells[j].cell.cell;
- var childBounds = this.getVertexBounds(childCell);
-
- var edges = this.graph.getEdgesBetween(parentCell,
- childCell, false);
-
- var newPoints = [];
- var x = 0;
- var y = 0;
-
- for (var i = 0; i < edges.length; i++)
- {
- if (this.horizontal)
- {
- // Use opposite co-ords, calculation was done for
- //
- x = parentBounds.x + parentBounds.width;
- y = parentBounds.y + currentXOffset;
- newPoints.push(new mxPoint(x, y));
- x = parentBounds.x + parentBounds.width
- + currentYOffset;
- newPoints.push(new mxPoint(x, y));
- y = childBounds.y + childBounds.height / 2.0;
- newPoints.push(new mxPoint(x, y));
- this.setEdgePoints(edges[i], newPoints);
- }
- else
- {
- x = parentBounds.x + currentXOffset;
- y = parentBounds.y + parentBounds.height;
- newPoints.push(new mxPoint(x, y));
- y = parentBounds.y + parentBounds.height
- + currentYOffset;
- newPoints.push(new mxPoint(x, y));
- x = childBounds.x + childBounds.width / 2.0;
- newPoints.push(new mxPoint(x, y));
- this.setEdgePoints(edges[i], newPoints);
- }
- }
-
- if (j < childCount / 2)
- {
- currentYOffset += this.prefVertEdgeOff;
- }
- else if (j > childCount / 2)
- {
- currentYOffset -= this.prefVertEdgeOff;
- }
- // Ignore the case if equals, this means the second of 2
- // jettys with the same y (even number of edges)
-
- // pos[k * 2] = currentX;
- currentXOffset += edgeSpacing;
- // pos[k * 2 + 1] = currentYOffset;
-
- maxYOffset = Math.max(maxYOffset, currentYOffset);
- }
-};
-
-/**
- * Class: WeightedCellSorter
- *
- * A utility class used to track cells whilst sorting occurs on the weighted
- * sum of their connected edges. Does not violate (x.compareTo(y)==0) ==
- * (x.equals(y))
- *
- * Constructor: WeightedCellSorter
- *
- * Constructs a new weighted cell sorted for the given cell and weight.
- */
-function WeightedCellSorter(cell, weightedValue)
-{
- this.cell = cell;
- this.weightedValue = weightedValue;
-};
-
-/**
- * Variable: weightedValue
- *
- * The weighted value of the cell stored.
- */
-WeightedCellSorter.prototype.weightedValue = 0;
-
-/**
- * Variable: nudge
- *
- * Whether or not to flip equal weight values.
- */
-WeightedCellSorter.prototype.nudge = false;
-
-/**
- * Variable: visited
- *
- * Whether or not this cell has been visited in the current assignment.
- */
-WeightedCellSorter.prototype.visited = false;
-
-/**
- * Variable: rankIndex
- *
- * The index this cell is in the model rank.
- */
-WeightedCellSorter.prototype.rankIndex = null;
-
-/**
- * Variable: cell
- *
- * The cell whose median value is being calculated.
- */
-WeightedCellSorter.prototype.cell = null;
-
-/**
- * Function: compare
- *
- * Compares two WeightedCellSorters.
- */
-WeightedCellSorter.prototype.compare = function(a, b)
-{
- if (a != null && b != null)
- {
- if (b.weightedValue > a.weightedValue)
- {
- return 1;
- }
- else if (b.weightedValue < a.weightedValue)
- {
- return -1;
- }
- else
- {
- if (b.nudge)
- {
- return 1;
- }
- else
- {
- return -1;
- }
- }
- }
- else
- {
- return 0;
- }
-}; \ No newline at end of file
generated by cgit (git 2.34.1) at 2025-03-13 04:19:34 +0000