From 92f3207b50a1caca07df5c5b238212af3358905b Mon Sep 17 00:00:00 2001 From: adhitya Date: Mon, 11 Apr 2016 15:10:54 +0000 Subject: Revert last two commits - Keyboard shortcuts are not working --- .../model/mxGraphAbstractHierarchyCell.js | 206 +++ .../hierarchical/model/mxGraphHierarchyEdge.js | 174 ++ .../hierarchical/model/mxGraphHierarchyModel.js | 685 ++++++++ .../hierarchical/model/mxGraphHierarchyNode.js | 210 +++ src/js/layout/hierarchical/mxHierarchicalLayout.js | 623 +++++++ .../hierarchical/stage/mxCoordinateAssignment.js | 1836 ++++++++++++++++++++ .../stage/mxHierarchicalLayoutStage.js | 25 + .../stage/mxMedianHybridCrossingReduction.js | 674 +++++++ .../hierarchical/stage/mxMinimumCycleRemover.js | 131 ++ src/js/layout/mxCircleLayout.js | 203 +++ src/js/layout/mxCompactTreeLayout.js | 995 +++++++++++ src/js/layout/mxCompositeLayout.js | 101 ++ src/js/layout/mxEdgeLabelLayout.js | 165 ++ src/js/layout/mxFastOrganicLayout.js | 591 +++++++ src/js/layout/mxGraphLayout.js | 503 ++++++ src/js/layout/mxParallelEdgeLayout.js | 198 +++ src/js/layout/mxPartitionLayout.js | 240 +++ src/js/layout/mxStackLayout.js | 381 ++++ 18 files changed, 7941 insertions(+) create mode 100644 src/js/layout/hierarchical/model/mxGraphAbstractHierarchyCell.js create mode 100644 src/js/layout/hierarchical/model/mxGraphHierarchyEdge.js create mode 100644 src/js/layout/hierarchical/model/mxGraphHierarchyModel.js create mode 100644 src/js/layout/hierarchical/model/mxGraphHierarchyNode.js create mode 100644 src/js/layout/hierarchical/mxHierarchicalLayout.js create mode 100644 src/js/layout/hierarchical/stage/mxCoordinateAssignment.js create mode 100644 src/js/layout/hierarchical/stage/mxHierarchicalLayoutStage.js create mode 100644 src/js/layout/hierarchical/stage/mxMedianHybridCrossingReduction.js create mode 100644 src/js/layout/hierarchical/stage/mxMinimumCycleRemover.js create mode 100644 src/js/layout/mxCircleLayout.js create mode 100644 src/js/layout/mxCompactTreeLayout.js create mode 100644 src/js/layout/mxCompositeLayout.js create mode 100644 src/js/layout/mxEdgeLabelLayout.js create mode 100644 src/js/layout/mxFastOrganicLayout.js create mode 100644 src/js/layout/mxGraphLayout.js create mode 100644 src/js/layout/mxParallelEdgeLayout.js create mode 100644 src/js/layout/mxPartitionLayout.js create mode 100644 src/js/layout/mxStackLayout.js (limited to 'src/js/layout') diff --git a/src/js/layout/hierarchical/model/mxGraphAbstractHierarchyCell.js b/src/js/layout/hierarchical/model/mxGraphAbstractHierarchyCell.js new file mode 100644 index 0000000..e2fe6a6 --- /dev/null +++ b/src/js/layout/hierarchical/model/mxGraphAbstractHierarchyCell.js @@ -0,0 +1,206 @@ +/** + * $Id: mxGraphAbstractHierarchyCell.js,v 1.12 2010-01-04 11:18:26 gaudenz Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxGraphAbstractHierarchyCell + * + * An abstraction of an internal hierarchy node or edge + * + * Constructor: mxGraphAbstractHierarchyCell + * + * Constructs a new hierarchical layout algorithm. + * + * Arguments: + * + * graph - Reference to the enclosing . + * deterministic - Optional boolean that specifies if this layout should be + * deterministic. Default is true. + */ +function mxGraphAbstractHierarchyCell() +{ + this.x = []; + this.y = []; + this.temp = []; +}; + +/** + * Variable: maxRank + * + * The maximum rank this cell occupies. Default is -1. + */ +mxGraphAbstractHierarchyCell.prototype.maxRank = -1; + +/** + * Variable: minRank + * + * The minimum rank this cell occupies. Default is -1. + */ +mxGraphAbstractHierarchyCell.prototype.minRank = -1; + +/** + * Variable: x + * + * The x position of this cell for each layer it occupies + */ +mxGraphAbstractHierarchyCell.prototype.x = null; + +/** + * Variable: y + * + * The y position of this cell for each layer it occupies + */ +mxGraphAbstractHierarchyCell.prototype.y = null; + +/** + * Variable: width + * + * The width of this cell + */ +mxGraphAbstractHierarchyCell.prototype.width = 0; + +/** + * Variable: height + * + * The height of this cell + */ +mxGraphAbstractHierarchyCell.prototype.height = 0; + +/** + * Variable: nextLayerConnectedCells + * + * A cached version of the cells this cell connects to on the next layer up + */ +mxGraphAbstractHierarchyCell.prototype.nextLayerConnectedCells = null; + +/** + * Variable: previousLayerConnectedCells + * + * A cached version of the cells this cell connects to on the next layer down + */ +mxGraphAbstractHierarchyCell.prototype.previousLayerConnectedCells = null; + +/** + * Variable: temp + * + * Temporary variable for general use. Generally, try to avoid + * carrying information between stages. Currently, the longest + * path layering sets temp to the rank position in fixRanks() + * and the crossing reduction uses this. This meant temp couldn't + * be used for hashing the nodes in the model dfs and so hashCode + * was created + */ +mxGraphAbstractHierarchyCell.prototype.temp = null; + +/** + * Function: getNextLayerConnectedCells + * + * Returns the cells this cell connects to on the next layer up + */ +mxGraphAbstractHierarchyCell.prototype.getNextLayerConnectedCells = function(layer) +{ + return null; +}; + +/** + * Function: getPreviousLayerConnectedCells + * + * Returns the cells this cell connects to on the next layer down + */ +mxGraphAbstractHierarchyCell.prototype.getPreviousLayerConnectedCells = function(layer) +{ + return null; +}; + +/** + * Function: isEdge + * + * Returns whether or not this cell is an edge + */ +mxGraphAbstractHierarchyCell.prototype.isEdge = function() +{ + return false; +}; + +/** + * Function: isVertex + * + * Returns whether or not this cell is a node + */ +mxGraphAbstractHierarchyCell.prototype.isVertex = function() +{ + return false; +}; + +/** + * Function: getGeneralPurposeVariable + * + * Gets the value of temp for the specified layer + */ +mxGraphAbstractHierarchyCell.prototype.getGeneralPurposeVariable = function(layer) +{ + return null; +}; + +/** + * Function: setGeneralPurposeVariable + * + * Set the value of temp for the specified layer + */ +mxGraphAbstractHierarchyCell.prototype.setGeneralPurposeVariable = function(layer, value) +{ + return null; +}; + +/** + * Function: setX + * + * Set the value of x for the specified layer + */ +mxGraphAbstractHierarchyCell.prototype.setX = function(layer, value) +{ + if (this.isVertex()) + { + this.x[0] = value; + } + else if (this.isEdge()) + { + this.x[layer - this.minRank - 1] = value; + } +}; + +/** + * Function: getX + * + * Gets the value of x on the specified layer + */ +mxGraphAbstractHierarchyCell.prototype.getX = function(layer) +{ + if (this.isVertex()) + { + return this.x[0]; + } + else if (this.isEdge()) + { + return this.x[layer - this.minRank - 1]; + } + + return 0.0; +}; + +/** + * Function: setY + * + * Set the value of y for the specified layer + */ +mxGraphAbstractHierarchyCell.prototype.setY = function(layer, value) +{ + if (this.isVertex()) + { + this.y[0] = value; + } + else if (this.isEdge()) + { + this.y[layer -this. minRank - 1] = value; + } +}; diff --git a/src/js/layout/hierarchical/model/mxGraphHierarchyEdge.js b/src/js/layout/hierarchical/model/mxGraphHierarchyEdge.js new file mode 100644 index 0000000..8ba16dd --- /dev/null +++ b/src/js/layout/hierarchical/model/mxGraphHierarchyEdge.js @@ -0,0 +1,174 @@ +/** + * $Id: mxGraphHierarchyEdge.js,v 1.15 2012-06-12 20:23:14 david Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxGraphHierarchyEdge + * + * An abstraction of a hierarchical edge for the hierarchy layout + * + * Constructor: mxGraphHierarchyEdge + * + * Constructs a hierarchy edge + * + * Arguments: + * + * edges - a list of real graph edges this abstraction represents + */ +function mxGraphHierarchyEdge(edges) +{ + mxGraphAbstractHierarchyCell.apply(this, arguments); + this.edges = edges; +}; + +/** + * Extends mxGraphAbstractHierarchyCell. + */ +mxGraphHierarchyEdge.prototype = new mxGraphAbstractHierarchyCell(); +mxGraphHierarchyEdge.prototype.constructor = mxGraphHierarchyEdge; + +/** + * Variable: edges + * + * The graph edge(s) this object represents. Parallel edges are all grouped + * together within one hierarchy edge. + */ +mxGraphHierarchyEdge.prototype.edges = null; + +/** + * Variable: source + * + * The node this edge is sourced at + */ +mxGraphHierarchyEdge.prototype.source = null; + +/** + * Variable: target + * + * The node this edge targets + */ +mxGraphHierarchyEdge.prototype.target = null; + +/** + * Variable: isReversed + * + * Whether or not the direction of this edge has been reversed + * internally to create a DAG for the hierarchical layout + */ +mxGraphHierarchyEdge.prototype.isReversed = false; + +/** + * Function: invert + * + * Inverts the direction of this internal edge(s) + */ +mxGraphHierarchyEdge.prototype.invert = function(layer) +{ + var temp = this.source; + this.source = this.target; + this.target = temp; + this.isReversed = !this.isReversed; +}; + +/** + * Function: getNextLayerConnectedCells + * + * Returns the cells this cell connects to on the next layer up + */ +mxGraphHierarchyEdge.prototype.getNextLayerConnectedCells = function(layer) +{ + if (this.nextLayerConnectedCells == null) + { + this.nextLayerConnectedCells = []; + + for (var i = 0; i < this.temp.length; i++) + { + this.nextLayerConnectedCells[i] = []; + + if (i == this.temp.length - 1) + { + this.nextLayerConnectedCells[i].push(this.source); + } + else + { + this.nextLayerConnectedCells[i].push(this); + } + } + } + + return this.nextLayerConnectedCells[layer - this.minRank - 1]; +}; + +/** + * Function: getPreviousLayerConnectedCells + * + * Returns the cells this cell connects to on the next layer down + */ +mxGraphHierarchyEdge.prototype.getPreviousLayerConnectedCells = function(layer) +{ + if (this.previousLayerConnectedCells == null) + { + this.previousLayerConnectedCells = []; + + for (var i = 0; i < this.temp.length; i++) + { + this.previousLayerConnectedCells[i] = []; + + if (i == 0) + { + this.previousLayerConnectedCells[i].push(this.target); + } + else + { + this.previousLayerConnectedCells[i].push(this); + } + } + } + + return this.previousLayerConnectedCells[layer - this.minRank - 1]; +}; + +/** + * Function: isEdge + * + * Returns true. + */ +mxGraphHierarchyEdge.prototype.isEdge = function() +{ + return true; +}; + +/** + * Function: getGeneralPurposeVariable + * + * Gets the value of temp for the specified layer + */ +mxGraphHierarchyEdge.prototype.getGeneralPurposeVariable = function(layer) +{ + return this.temp[layer - this.minRank - 1]; +}; + +/** + * Function: setGeneralPurposeVariable + * + * Set the value of temp for the specified layer + */ +mxGraphHierarchyEdge.prototype.setGeneralPurposeVariable = function(layer, value) +{ + this.temp[layer - this.minRank - 1] = value; +}; + +/** + * Function: getCoreCell + * + * Gets the first core edge associated with this wrapper + */ +mxGraphHierarchyEdge.prototype.getCoreCell = function() +{ + if (this.edges != null && this.edges.length > 0) + { + return this.edges[0]; + } + + return null; +}; \ No newline at end of file diff --git a/src/js/layout/hierarchical/model/mxGraphHierarchyModel.js b/src/js/layout/hierarchical/model/mxGraphHierarchyModel.js new file mode 100644 index 0000000..ca2ba30 --- /dev/null +++ b/src/js/layout/hierarchical/model/mxGraphHierarchyModel.js @@ -0,0 +1,685 @@ +/** + * $Id: mxGraphHierarchyModel.js,v 1.33 2012-12-18 13:16:43 david Exp $ + * Copyright (c) 2006-2012, JGraph Ltd + */ +/** + * Class: mxGraphHierarchyModel + * + * Internal model of a hierarchical graph. This model stores nodes and edges + * equivalent to the real graph nodes and edges, but also stores the rank of the + * cells, the order within the ranks and the new candidate locations of cells. + * The internal model also reverses edge direction were appropriate , ignores + * self-loop and groups parallels together under one edge object. + * + * Constructor: mxGraphHierarchyModel + * + * Creates an internal ordered graph model using the vertices passed in. If + * there are any, leftward edge need to be inverted in the internal model + * + * Arguments: + * + * graph - the facade describing the graph to be operated on + * vertices - the vertices for this hierarchy + * ordered - whether or not the vertices are already ordered + * deterministic - whether or not this layout should be deterministic on each + * tightenToSource - whether or not to tighten vertices towards the sources + * scanRanksFromSinks - Whether rank assignment is from the sinks or sources. + * usage + */ +function mxGraphHierarchyModel(layout, vertices, roots, parent, tightenToSource) +{ + var graph = layout.getGraph(); + this.tightenToSource = tightenToSource; + this.roots = roots; + this.parent = parent; + + // map of cells to internal cell needed for second run through + // to setup the sink of edges correctly + this.vertexMapper = new Object(); + this.edgeMapper = new Object(); + this.maxRank = 0; + var internalVertices = []; + + if (vertices == null) + { + vertices = this.graph.getChildVertices(parent); + } + + this.maxRank = this.SOURCESCANSTARTRANK; + // map of cells to internal cell needed for second run through + // to setup the sink of edges correctly. Guess size by number + // of edges is roughly same as number of vertices. + this.createInternalCells(layout, vertices, internalVertices); + + // Go through edges set their sink values. Also check the + // ordering if and invert edges if necessary + for (var i = 0; i < vertices.length; i++) + { + var edges = internalVertices[i].connectsAsSource; + + for (var j = 0; j < edges.length; j++) + { + var internalEdge = edges[j]; + var realEdges = internalEdge.edges; + + // Only need to process the first real edge, since + // all the edges connect to the same other vertex + if (realEdges != null && realEdges.length > 0) + { + var realEdge = realEdges[0]; + var targetCell = graph.getView().getVisibleTerminal( + realEdge, false); + var targetCellId = mxCellPath.create(targetCell); + var internalTargetCell = this.vertexMapper[targetCellId]; + + if (internalVertices[i] == internalTargetCell) + { + // The real edge is reversed relative to the internal edge + targetCell = graph.getView().getVisibleTerminal( + realEdge, true); + targetCellId = mxCellPath.create(targetCell); + internalTargetCell = this.vertexMapper[targetCellId]; + } + + if (internalTargetCell != null + && internalVertices[i] != internalTargetCell) + { + internalEdge.target = internalTargetCell; + + if (internalTargetCell.connectsAsTarget.length == 0) + { + internalTargetCell.connectsAsTarget = []; + } + + if (mxUtils.indexOf(internalTargetCell.connectsAsTarget, internalEdge) < 0) + { + internalTargetCell.connectsAsTarget.push(internalEdge); + } + } + } + } + + // Use the temp variable in the internal nodes to mark this + // internal vertex as having been visited. + internalVertices[i].temp[0] = 1; + } +}; + +/** + * Variable: maxRank + * + * Stores the largest rank number allocated + */ +mxGraphHierarchyModel.prototype.maxRank = null; + +/** + * Variable: vertexMapper + * + * Map from graph vertices to internal model nodes. + */ +mxGraphHierarchyModel.prototype.vertexMapper = null; + +/** + * Variable: edgeMapper + * + * Map from graph edges to internal model edges + */ +mxGraphHierarchyModel.prototype.edgeMapper = null; + +/** + * Variable: ranks + * + * Mapping from rank number to actual rank + */ +mxGraphHierarchyModel.prototype.ranks = null; + +/** + * Variable: roots + * + * Store of roots of this hierarchy model, these are real graph cells, not + * internal cells + */ +mxGraphHierarchyModel.prototype.roots = null; + +/** + * Variable: parent + * + * The parent cell whose children are being laid out + */ +mxGraphHierarchyModel.prototype.parent = null; + +/** + * Variable: dfsCount + * + * Count of the number of times the ancestor dfs has been used. + */ +mxGraphHierarchyModel.prototype.dfsCount = 0; + +/** + * Variable: SOURCESCANSTARTRANK + * + * High value to start source layering scan rank value from. + */ +mxGraphHierarchyModel.prototype.SOURCESCANSTARTRANK = 100000000; + +/** + * Variable: tightenToSource + * + * Whether or not to tighten the assigned ranks of vertices up towards + * the source cells. + */ +mxGraphHierarchyModel.prototype.tightenToSource = false; + +/** + * Function: createInternalCells + * + * Creates all edges in the internal model + * + * Parameters: + * + * layout - Reference to the algorithm. + * vertices - Array of that represent the vertices whom are to + * have an internal representation created. + * internalVertices - The array of to have their + * information filled in using the real vertices. + */ +mxGraphHierarchyModel.prototype.createInternalCells = function(layout, vertices, internalVertices) +{ + var graph = layout.getGraph(); + + // Create internal edges + for (var i = 0; i < vertices.length; i++) + { + internalVertices[i] = new mxGraphHierarchyNode(vertices[i]); + var vertexId = mxCellPath.create(vertices[i]); + this.vertexMapper[vertexId] = internalVertices[i]; + + // If the layout is deterministic, order the cells + //List outgoingCells = graph.getNeighbours(vertices[i], deterministic); + var conns = layout.getEdges(vertices[i]); + var outgoingCells = graph.getOpposites(conns, vertices[i]); + internalVertices[i].connectsAsSource = []; + + // Create internal edges, but don't do any rank assignment yet + // First use the information from the greedy cycle remover to + // invert the leftward edges internally + for (var j = 0; j < outgoingCells.length; j++) + { + var cell = outgoingCells[j]; + + if (cell != vertices[i] && layout.graph.model.isVertex(cell) && + !layout.isVertexIgnored(cell)) + { + // We process all edge between this source and its targets + // If there are edges going both ways, we need to collect + // them all into one internal edges to avoid looping problems + // later. We assume this direction (source -> target) is the + // natural direction if at least half the edges are going in + // that direction. + + // The check below for edges[0] being in the vertex mapper is + // in case we've processed this the other way around + // (target -> source) and the number of edges in each direction + // are the same. All the graph edges will have been assigned to + // an internal edge going the other way, so we don't want to + // process them again + var undirectedEdges = graph.getEdgesBetween(vertices[i], + cell, false); + var directedEdges = graph.getEdgesBetween(vertices[i], + cell, true); + var edgeId = mxCellPath.create(undirectedEdges[0]); + + if (undirectedEdges != null && + undirectedEdges.length > 0 && + this.edgeMapper[edgeId] == null && + directedEdges.length * 2 >= undirectedEdges.length) + { + var internalEdge = new mxGraphHierarchyEdge(undirectedEdges); + + for (var k = 0; k < undirectedEdges.length; k++) + { + var edge = undirectedEdges[k]; + edgeId = mxCellPath.create(edge); + this.edgeMapper[edgeId] = internalEdge; + + // Resets all point on the edge and disables the edge style + // without deleting it from the cell style + graph.resetEdge(edge); + + if (layout.disableEdgeStyle) + { + layout.setEdgeStyleEnabled(edge, false); + layout.setOrthogonalEdge(edge,true); + } + } + + internalEdge.source = internalVertices[i]; + + if (mxUtils.indexOf(internalVertices[i].connectsAsSource, internalEdge) < 0) + { + internalVertices[i].connectsAsSource.push(internalEdge); + } + } + } + } + + // Ensure temp variable is cleared from any previous use + internalVertices[i].temp[0] = 0; + } +}; + +/** + * Function: initialRank + * + * Basic determination of minimum layer ranking by working from from sources + * or sinks and working through each node in the relevant edge direction. + * Starting at the sinks is basically a longest path layering algorithm. +*/ +mxGraphHierarchyModel.prototype.initialRank = function() +{ + var startNodes = []; + + if (this.roots != null) + { + for (var i = 0; i < this.roots.length; i++) + { + var vertexId = mxCellPath.create(this.roots[i]); + var internalNode = this.vertexMapper[vertexId]; + + if (internalNode != null) + { + startNodes.push(internalNode); + } + } + } + + for (var key in this.vertexMapper) + { + var internalNode = this.vertexMapper[key]; + + // Mark the node as not having had a layer assigned + internalNode.temp[0] = -1; + } + + var startNodesCopy = startNodes.slice(); + + while (startNodes.length > 0) + { + var internalNode = startNodes[0]; + var layerDeterminingEdges; + var edgesToBeMarked; + + layerDeterminingEdges = internalNode.connectsAsTarget; + edgesToBeMarked = internalNode.connectsAsSource; + + // flag to keep track of whether or not all layer determining + // edges have been scanned + var allEdgesScanned = true; + + // Work out the layer of this node from the layer determining + // edges. The minimum layer number of any node connected by one of + // the layer determining edges variable + var minimumLayer = this.SOURCESCANSTARTRANK; + + for (var i = 0; i < layerDeterminingEdges.length; i++) + { + var internalEdge = layerDeterminingEdges[i]; + + if (internalEdge.temp[0] == 5270620) + { + // This edge has been scanned, get the layer of the + // node on the other end + var otherNode = internalEdge.source; + minimumLayer = Math.min(minimumLayer, otherNode.temp[0] - 1); + } + else + { + allEdgesScanned = false; + + break; + } + } + + // If all edge have been scanned, assign the layer, mark all + // edges in the other direction and remove from the nodes list + if (allEdgesScanned) + { + internalNode.temp[0] = minimumLayer; + this.maxRank = Math.min(this.maxRank, minimumLayer); + + if (edgesToBeMarked != null) + { + for (var i = 0; i < edgesToBeMarked.length; i++) + { + var internalEdge = edgesToBeMarked[i]; + + // Assign unique stamp ( y/m/d/h ) + internalEdge.temp[0] = 5270620; + + // Add node on other end of edge to LinkedList of + // nodes to be analysed + var otherNode = internalEdge.target; + + // Only add node if it hasn't been assigned a layer + if (otherNode.temp[0] == -1) + { + startNodes.push(otherNode); + + // Mark this other node as neither being + // unassigned nor assigned so it isn't + // added to this list again, but it's + // layer isn't used in any calculation. + otherNode.temp[0] = -2; + } + } + } + + startNodes.shift(); + } + else + { + // Not all the edges have been scanned, get to the back of + // the class and put the dunces cap on + var removedCell = startNodes.shift(); + startNodes.push(internalNode); + + if (removedCell == internalNode && startNodes.length == 1) + { + // This is an error condition, we can't get out of + // this loop. It could happen for more than one node + // but that's a lot harder to detect. Log the error + // TODO make log comment + break; + } + } + } + + // Normalize the ranks down from their large starting value to place + // at least 1 sink on layer 0 + for (var key in this.vertexMapper) + { + var internalNode = this.vertexMapper[key]; + // Mark the node as not having had a layer assigned + internalNode.temp[0] -= this.maxRank; + } + + // Tighten the rank 0 nodes as far as possible + for ( var i = 0; i < startNodesCopy.length; i++) + { + var internalNode = startNodesCopy[i]; + var currentMaxLayer = 0; + var layerDeterminingEdges = internalNode.connectsAsSource; + + for ( var j = 0; j < layerDeterminingEdges.length; j++) + { + var internalEdge = layerDeterminingEdges[j]; + var otherNode = internalEdge.target; + internalNode.temp[0] = Math.max(currentMaxLayer, + otherNode.temp[0] + 1); + currentMaxLayer = internalNode.temp[0]; + } + } + + // Reset the maxRank to that which would be expected for a from-sink + // scan + this.maxRank = this.SOURCESCANSTARTRANK - this.maxRank; +}; + +/** + * Function: fixRanks + * + * Fixes the layer assignments to the values stored in the nodes. Also needs + * to create dummy nodes for edges that cross layers. + */ +mxGraphHierarchyModel.prototype.fixRanks = function() +{ + var rankList = []; + this.ranks = []; + + for (var i = 0; i < this.maxRank + 1; i++) + { + rankList[i] = []; + this.ranks[i] = rankList[i]; + } + + // Perform a DFS to obtain an initial ordering for each rank. + // Without doing this you would end up having to process + // crossings for a standard tree. + var rootsArray = null; + + if (this.roots != null) + { + var oldRootsArray = this.roots; + rootsArray = []; + + for (var i = 0; i < oldRootsArray.length; i++) + { + var cell = oldRootsArray[i]; + var cellId = mxCellPath.create(cell); + var internalNode = this.vertexMapper[cellId]; + rootsArray[i] = internalNode; + } + } + + this.visit(function(parent, node, edge, layer, seen) + { + if (seen == 0 && node.maxRank < 0 && node.minRank < 0) + { + rankList[node.temp[0]].push(node); + node.maxRank = node.temp[0]; + node.minRank = node.temp[0]; + + // Set temp[0] to the nodes position in the rank + node.temp[0] = rankList[node.maxRank].length - 1; + } + + if (parent != null && edge != null) + { + var parentToCellRankDifference = parent.maxRank - node.maxRank; + + if (parentToCellRankDifference > 1) + { + // There are ranks in between the parent and current cell + edge.maxRank = parent.maxRank; + edge.minRank = node.maxRank; + edge.temp = []; + edge.x = []; + edge.y = []; + + for (var i = edge.minRank + 1; i < edge.maxRank; i++) + { + // The connecting edge must be added to the + // appropriate ranks + rankList[i].push(edge); + edge.setGeneralPurposeVariable(i, rankList[i] + .length - 1); + } + } + } + }, rootsArray, false, null); +}; + +/** + * Function: visit + * + * A depth first search through the internal heirarchy model. + * + * Parameters: + * + * visitor - The visitor function pattern to be called for each node. + * trackAncestors - Whether or not the search is to keep track all nodes + * directly above this one in the search path. + */ +mxGraphHierarchyModel.prototype.visit = function(visitor, dfsRoots, trackAncestors, seenNodes) +{ + // Run dfs through on all roots + if (dfsRoots != null) + { + for (var i = 0; i < dfsRoots.length; i++) + { + var internalNode = dfsRoots[i]; + + if (internalNode != null) + { + if (seenNodes == null) + { + seenNodes = new Object(); + } + + if (trackAncestors) + { + // Set up hash code for root + internalNode.hashCode = []; + internalNode.hashCode[0] = this.dfsCount; + internalNode.hashCode[1] = i; + this.extendedDfs(null, internalNode, null, visitor, seenNodes, + internalNode.hashCode, i, 0); + } + else + { + this.dfs(null, internalNode, null, visitor, seenNodes, 0); + } + } + } + + this.dfsCount++; + } +}; + +/** + * Function: dfs + * + * Performs a depth first search on the internal hierarchy model + * + * Parameters: + * + * parent - the parent internal node of the current internal node + * root - the current internal node + * connectingEdge - the internal edge connecting the internal node and the parent + * internal node, if any + * visitor - the visitor pattern to be called for each node + * seen - a set of all nodes seen by this dfs a set of all of the + * ancestor node of the current node + * layer - the layer on the dfs tree ( not the same as the model ranks ) + */ +mxGraphHierarchyModel.prototype.dfs = function(parent, root, connectingEdge, visitor, seen, layer) +{ + if (root != null) + { + var rootId = mxCellPath.create(root.cell); + + if (seen[rootId] == null) + { + seen[rootId] = root; + visitor(parent, root, connectingEdge, layer, 0); + + // Copy the connects as source list so that visitors + // can change the original for edge direction inversions + var outgoingEdges = root.connectsAsSource.slice(); + + for (var i = 0; i< outgoingEdges.length; i++) + { + var internalEdge = outgoingEdges[i]; + var targetNode = internalEdge.target; + + // Root check is O(|roots|) + this.dfs(root, targetNode, internalEdge, visitor, seen, + layer + 1); + } + } + else + { + // Use the int field to indicate this node has been seen + visitor(parent, root, connectingEdge, layer, 1); + } + } +}; + +/** + * Function: extendedDfs + * + * Performs a depth first search on the internal hierarchy model. This dfs + * extends the default version by keeping track of cells ancestors, but it + * should be only used when necessary because of it can be computationally + * intensive for deep searches. + * + * Parameters: + * + * parent - the parent internal node of the current internal node + * root - the current internal node + * connectingEdge - the internal edge connecting the internal node and the parent + * internal node, if any + * visitor - the visitor pattern to be called for each node + * seen - a set of all nodes seen by this dfs + * ancestors - the parent hash code + * childHash - the new hash code for this node + * layer - the layer on the dfs tree ( not the same as the model ranks ) + */ +mxGraphHierarchyModel.prototype.extendedDfs = function(parent, root, connectingEdge, visitor, seen, ancestors, childHash, layer) +{ + // Explanation of custom hash set. Previously, the ancestors variable + // was passed through the dfs as a HashSet. The ancestors were copied + // into a new HashSet and when the new child was processed it was also + // added to the set. If the current node was in its ancestor list it + // meant there is a cycle in the graph and this information is passed + // to the visitor.visit() in the seen parameter. The HashSet clone was + // very expensive on CPU so a custom hash was developed using primitive + // types. temp[] couldn't be used so hashCode[] was added to each node. + // Each new child adds another int to the array, copying the prefix + // from its parent. Child of the same parent add different ints (the + // limit is therefore 2^32 children per parent...). If a node has a + // child with the hashCode already set then the child code is compared + // to the same portion of the current nodes array. If they match there + // is a loop. + // Note that the basic mechanism would only allow for 1 use of this + // functionality, so the root nodes have two ints. The second int is + // incremented through each node root and the first is incremented + // through each run of the dfs algorithm (therefore the dfs is not + // thread safe). The hash code of each node is set if not already set, + // or if the first int does not match that of the current run. + if (root != null) + { + if (parent != null) + { + // Form this nodes hash code if necessary, that is, if the + // hashCode variable has not been initialized or if the + // start of the parent hash code does not equal the start of + // this nodes hash code, indicating the code was set on a + // previous run of this dfs. + if (root.hashCode == null || + root.hashCode[0] != parent.hashCode[0]) + { + var hashCodeLength = parent.hashCode.length + 1; + root.hashCode = parent.hashCode.slice(); + root.hashCode[hashCodeLength - 1] = childHash; + } + } + + var rootId = mxCellPath.create(root.cell); + + if (seen[rootId] == null) + { + seen[rootId] = root; + visitor(parent, root, connectingEdge, layer, 0); + + // Copy the connects as source list so that visitors + // can change the original for edge direction inversions + var outgoingEdges = root.connectsAsSource.slice(); + + for (var i = 0; i < outgoingEdges.length; i++) + { + var internalEdge = outgoingEdges[i]; + var targetNode = internalEdge.target; + + // Root check is O(|roots|) + this.extendedDfs(root, targetNode, internalEdge, visitor, seen, + root.hashCode, i, layer + 1); + } + } + else + { + // Use the int field to indicate this node has been seen + visitor(parent, root, connectingEdge, layer, 1); + } + } +}; diff --git a/src/js/layout/hierarchical/model/mxGraphHierarchyNode.js b/src/js/layout/hierarchical/model/mxGraphHierarchyNode.js new file mode 100644 index 0000000..d901d57 --- /dev/null +++ b/src/js/layout/hierarchical/model/mxGraphHierarchyNode.js @@ -0,0 +1,210 @@ +/** + * $Id: mxGraphHierarchyNode.js,v 1.13 2012-06-12 20:24:58 david Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxGraphHierarchyNode + * + * An abstraction of a hierarchical edge for the hierarchy layout + * + * Constructor: mxGraphHierarchyNode + * + * Constructs an internal node to represent the specified real graph cell + * + * Arguments: + * + * cell - the real graph cell this node represents + */ +function mxGraphHierarchyNode(cell) +{ + mxGraphAbstractHierarchyCell.apply(this, arguments); + this.cell = cell; +}; + +/** + * Extends mxGraphAbstractHierarchyCell. + */ +mxGraphHierarchyNode.prototype = new mxGraphAbstractHierarchyCell(); +mxGraphHierarchyNode.prototype.constructor = mxGraphHierarchyNode; + +/** + * Variable: cell + * + * The graph cell this object represents. + */ +mxGraphHierarchyNode.prototype.cell = null; + +/** + * Variable: connectsAsTarget + * + * Collection of hierarchy edges that have this node as a target + */ +mxGraphHierarchyNode.prototype.connectsAsTarget = []; + +/** + * Variable: connectsAsSource + * + * Collection of hierarchy edges that have this node as a source + */ +mxGraphHierarchyNode.prototype.connectsAsSource = []; + +/** + * Variable: hashCode + * + * Assigns a unique hashcode for each node. Used by the model dfs instead + * of copying HashSets + */ +mxGraphHierarchyNode.prototype.hashCode = false; + +/** + * Function: getRankValue + * + * Returns the integer value of the layer that this node resides in + */ +mxGraphHierarchyNode.prototype.getRankValue = function(layer) +{ + return this.maxRank; +}; + +/** + * Function: getNextLayerConnectedCells + * + * Returns the cells this cell connects to on the next layer up + */ +mxGraphHierarchyNode.prototype.getNextLayerConnectedCells = function(layer) +{ + if (this.nextLayerConnectedCells == null) + { + this.nextLayerConnectedCells = []; + this.nextLayerConnectedCells[0] = []; + + for (var i = 0; i < this.connectsAsTarget.length; i++) + { + var edge = this.connectsAsTarget[i]; + + if (edge.maxRank == -1 || edge.maxRank == layer + 1) + { + // Either edge is not in any rank or + // no dummy nodes in edge, add node of other side of edge + this.nextLayerConnectedCells[0].push(edge.source); + } + else + { + // Edge spans at least two layers, add edge + this.nextLayerConnectedCells[0].push(edge); + } + } + } + + return this.nextLayerConnectedCells[0]; +}; + +/** + * Function: getPreviousLayerConnectedCells + * + * Returns the cells this cell connects to on the next layer down + */ +mxGraphHierarchyNode.prototype.getPreviousLayerConnectedCells = function(layer) +{ + if (this.previousLayerConnectedCells == null) + { + this.previousLayerConnectedCells = []; + this.previousLayerConnectedCells[0] = []; + + for (var i = 0; i < this.connectsAsSource.length; i++) + { + var edge = this.connectsAsSource[i]; + + if (edge.minRank == -1 || edge.minRank == layer - 1) + { + // No dummy nodes in edge, add node of other side of edge + this.previousLayerConnectedCells[0].push(edge.target); + } + else + { + // Edge spans at least two layers, add edge + this.previousLayerConnectedCells[0].push(edge); + } + } + } + + return this.previousLayerConnectedCells[0]; +}; + +/** + * Function: isVertex + * + * Returns true. + */ +mxGraphHierarchyNode.prototype.isVertex = function() +{ + return true; +}; + +/** + * Function: getGeneralPurposeVariable + * + * Gets the value of temp for the specified layer + */ +mxGraphHierarchyNode.prototype.getGeneralPurposeVariable = function(layer) +{ + return this.temp[0]; +}; + +/** + * Function: setGeneralPurposeVariable + * + * Set the value of temp for the specified layer + */ +mxGraphHierarchyNode.prototype.setGeneralPurposeVariable = function(layer, value) +{ + this.temp[0] = value; +}; + +/** + * Function: isAncestor + */ +mxGraphHierarchyNode.prototype.isAncestor = function(otherNode) +{ + // Firstly, the hash code of this node needs to be shorter than the + // other node + if (otherNode != null && this.hashCode != null && otherNode.hashCode != null + && this.hashCode.length < otherNode.hashCode.length) + { + if (this.hashCode == otherNode.hashCode) + { + return true; + } + + if (this.hashCode == null || this.hashCode == null) + { + return false; + } + + // Secondly, this hash code must match the start of the other + // node's hash code. Arrays.equals cannot be used here since + // the arrays are different length, and we do not want to + // perform another array copy. + for (var i = 0; i < this.hashCode.length; i++) + { + if (this.hashCode[i] != otherNode.hashCode[i]) + { + return false; + } + } + + return true; + } + + return false; +}; + +/** + * Function: getCoreCell + * + * Gets the core vertex associated with this wrapper + */ +mxGraphHierarchyNode.prototype.getCoreCell = function() +{ + return this.cell; +}; \ No newline at end of file diff --git a/src/js/layout/hierarchical/mxHierarchicalLayout.js b/src/js/layout/hierarchical/mxHierarchicalLayout.js new file mode 100644 index 0000000..6ce0e05 --- /dev/null +++ b/src/js/layout/hierarchical/mxHierarchicalLayout.js @@ -0,0 +1,623 @@ +/** + * $Id: mxHierarchicalLayout.js,v 1.30 2012-12-18 12:41:06 david Exp $ + * Copyright (c) 2005-2012, JGraph Ltd + */ +/** + * Class: mxHierarchicalLayout + * + * A hierarchical layout algorithm. + * + * Constructor: mxHierarchicalLayout + * + * Constructs a new hierarchical layout algorithm. + * + * Arguments: + * + * graph - Reference to the enclosing . + * orientation - Optional constant that defines the orientation of this + * layout. + * deterministic - Optional boolean that specifies if this layout should be + * deterministic. Default is true. + */ +function mxHierarchicalLayout(graph, orientation, deterministic) +{ + mxGraphLayout.call(this, graph); + this.orientation = (orientation != null) ? orientation : mxConstants.DIRECTION_NORTH; + this.deterministic = (deterministic != null) ? deterministic : true; +}; + +/** + * Extends mxGraphLayout. + */ +mxHierarchicalLayout.prototype = new mxGraphLayout(); +mxHierarchicalLayout.prototype.constructor = mxHierarchicalLayout; + +/** + * Variable: roots + * + * Holds the array of that this layout contains. + */ +mxHierarchicalLayout.prototype.roots = null; + +/** + * Variable: resizeParent + * + * Specifies if the parent should be resized after the layout so that it + * contains all the child cells. Default is false. See also . + */ +mxHierarchicalLayout.prototype.resizeParent = false; + +/** + * Variable: moveParent + * + * Specifies if the parent should be moved if is enabled. + * Default is false. + */ +mxHierarchicalLayout.prototype.moveParent = false; + +/** + * Variable: parentBorder + * + * The border to be added around the children if the parent is to be + * resized using . Default is 0. + */ +mxHierarchicalLayout.prototype.parentBorder = 0; + +/** + * Variable: intraCellSpacing + * + * The spacing buffer added between cells on the same layer. Default is 30. + */ +mxHierarchicalLayout.prototype.intraCellSpacing = 30; + +/** + * Variable: interRankCellSpacing + * + * The spacing buffer added between cell on adjacent layers. Default is 50. + */ +mxHierarchicalLayout.prototype.interRankCellSpacing = 50; + +/** + * Variable: interHierarchySpacing + * + * The spacing buffer between unconnected hierarchies. Default is 60. + */ +mxHierarchicalLayout.prototype.interHierarchySpacing = 60; + +/** + * Variable: parallelEdgeSpacing + * + * The distance between each parallel edge on each ranks for long edges + */ +mxHierarchicalLayout.prototype.parallelEdgeSpacing = 10; + +/** + * Variable: orientation + * + * The position of the root node(s) relative to the laid out graph in. + * Default is . + */ +mxHierarchicalLayout.prototype.orientation = mxConstants.DIRECTION_NORTH; + +/** + * Variable: fineTuning + * + * Whether or not to perform local optimisations and iterate multiple times + * through the algorithm. Default is true. + */ +mxHierarchicalLayout.prototype.fineTuning = true; + +/** + * + * Variable: tightenToSource + * + * Whether or not to tighten the assigned ranks of vertices up towards + * the source cells. + */ +mxHierarchicalLayout.prototype.tightenToSource = true; + +/** + * Variable: disableEdgeStyle + * + * Specifies if the STYLE_NOEDGESTYLE flag should be set on edges that are + * modified by the result. Default is true. + */ +mxHierarchicalLayout.prototype.disableEdgeStyle = true; + +/** + * Variable: promoteEdges + * + * Whether or not to promote edges that terminate on vertices with + * different but common ancestry to appear connected to the highest + * siblings in the ancestry chains + */ +mxHierarchicalLayout.prototype.promoteEdges = true; + +/** + * Variable: traverseAncestors + * + * Whether or not to navigate edges whose terminal vertices + * have different parents but are in the same ancestry chain + */ +mxHierarchicalLayout.prototype.traverseAncestors = true; + +/** + * Variable: model + * + * The internal formed of the layout. + */ +mxHierarchicalLayout.prototype.model = null; + +/** + * Function: getModel + * + * Returns the internal for this layout algorithm. + */ +mxHierarchicalLayout.prototype.getModel = function() +{ + return this.model; +}; + +/** + * Function: execute + * + * Executes the layout for the children of the specified parent. + * + * Parameters: + * + * parent - Parent that contains the children to be laid out. + * roots - Optional starting roots of the layout. + */ +mxHierarchicalLayout.prototype.execute = function(parent, roots) +{ + this.parent = parent; + var model = this.graph.model; + + // If the roots are set and the parent is set, only + // use the roots that are some dependent of the that + // parent. + // If just the root are set, use them as-is + // If just the parent is set use it's immediate + // children as the initial set + + if (roots == null && parent == null) + { + // TODO indicate the problem + return; + } + + if (roots != null && parent != null) + { + var rootsCopy = []; + + for (var i = 0; i < roots.length; i++) + { + + if (model.isAncestor(parent, roots[i])) + { + rootsCopy.push(roots[i]); + } + } + + this.roots = rootsCopy; + } + else + { + this.roots = roots; + } + + model.beginUpdate(); + try + { + this.run(parent); + + if (this.resizeParent && + !this.graph.isCellCollapsed(parent)) + { + this.graph.updateGroupBounds([parent], + this.parentBorder, this.moveParent); + } + } + finally + { + model.endUpdate(); + } +}; + +/** + * Function: findRoots + * + * Returns all visible children in the given parent which do not have + * incoming edges. If the result is empty then the children with the + * maximum difference between incoming and outgoing edges are returned. + * This takes into account edges that are being promoted to the given + * root due to invisible children or collapsed cells. + * + * Parameters: + * + * parent - whose children should be checked. + * vertices - array of vertices to limit search to + */ +mxHierarchicalLayout.prototype.findRoots = function(parent, vertices) +{ + var roots = []; + + if (parent != null && vertices != null) + { + var model = this.graph.model; + var best = null; + var maxDiff = -100000; + + for (var i in vertices) + { + var cell = vertices[i]; + + if (model.isVertex(cell) && this.graph.isCellVisible(cell)) + { + var conns = this.getEdges(cell); + var fanOut = 0; + var fanIn = 0; + + for (var k = 0; k < conns.length; k++) + { + var src = this.graph.view.getVisibleTerminal(conns[k], true); + + if (src == cell) + { + fanOut++; + } + else + { + fanIn++; + } + } + + if (fanIn == 0 && fanOut > 0) + { + roots.push(cell); + } + + var diff = fanOut - fanIn; + + if (diff > maxDiff) + { + maxDiff = diff; + best = cell; + } + } + } + + if (roots.length == 0 && best != null) + { + roots.push(best); + } + } + + return roots; +}; + +/** + * Function: getEdges + * + * Returns the connected edges for the given cell. + * + * Parameters: + * + * cell - whose edges should be returned. + */ +mxHierarchicalLayout.prototype.getEdges = function(cell) +{ + var model = this.graph.model; + var edges = []; + var isCollapsed = this.graph.isCellCollapsed(cell); + var childCount = model.getChildCount(cell); + + for (var i = 0; i < childCount; i++) + { + var child = model.getChildAt(cell, i); + + if (isCollapsed || !this.graph.isCellVisible(child)) + { + edges = edges.concat(model.getEdges(child, true, true)); + } + } + + edges = edges.concat(model.getEdges(cell, true, true)); + var result = []; + + for (var i = 0; i < edges.length; i++) + { + var state = this.graph.view.getState(edges[i]); + + var source = (state != null) ? state.getVisibleTerminal(true) : this.graph.view.getVisibleTerminal(edges[i], true); + var target = (state != null) ? state.getVisibleTerminal(false) : this.graph.view.getVisibleTerminal(edges[i], false); + + if ((source == target) || ((source != target) && ((target == cell && (this.parent == null || this.graph.isValidAncestor(source, this.parent, this.traverseAncestors))) || + (source == cell && (this.parent == null || + this.graph.isValidAncestor(target, this.parent, this.traverseAncestors)))))) + { + result.push(edges[i]); + } + } + + return result; +}; + +/** + * Function: run + * + * The API method used to exercise the layout upon the graph description + * and produce a separate description of the vertex position and edge + * routing changes made. It runs each stage of the layout that has been + * created. + */ +mxHierarchicalLayout.prototype.run = function(parent) +{ + // Separate out unconnected hierarchies + var hierarchyVertices = []; + var allVertexSet = []; + + if (this.roots == null && parent != null) + { + var filledVertexSet = this.filterDescendants(parent); + + this.roots = []; + var filledVertexSetEmpty = true; + + // Poor man's isSetEmpty + for (var key in filledVertexSet) + { + if (filledVertexSet[key] != null) + { + filledVertexSetEmpty = false; + break; + } + } + + while (!filledVertexSetEmpty) + { + var candidateRoots = this.findRoots(parent, filledVertexSet); + + for (var i = 0; i < candidateRoots.length; i++) + { + var vertexSet = []; + hierarchyVertices.push(vertexSet); + + this.traverse(candidateRoots[i], true, null, allVertexSet, vertexSet, + hierarchyVertices, filledVertexSet); + } + + for (var i = 0; i < candidateRoots.length; i++) + { + this.roots.push(candidateRoots[i]); + } + + filledVertexSetEmpty = true; + + // Poor man's isSetEmpty + for (var key in filledVertexSet) + { + if (filledVertexSet[key] != null) + { + filledVertexSetEmpty = false; + break; + } + } + } + } + else + { + // Find vertex set as directed traversal from roots + + for (var i = 0; i < roots.length; i++) + { + var vertexSet = []; + hierarchyVertices.push(vertexSet); + + traverse(roots.get(i), true, null, allVertexSet, vertexSet, + hierarchyVertices, null); + } + } + + // Iterate through the result removing parents who have children in this layout + + // Perform a layout for each seperate hierarchy + // Track initial coordinate x-positioning + var initialX = 0; + + for (var i = 0; i < hierarchyVertices.length; i++) + { + var vertexSet = hierarchyVertices[i]; + var tmp = []; + + for (var key in vertexSet) + { + tmp.push(vertexSet[key]); + } + + this.model = new mxGraphHierarchyModel(this, tmp, this.roots, + parent, this.tightenToSource); + + this.cycleStage(parent); + this.layeringStage(); + + this.crossingStage(parent); + initialX = this.placementStage(initialX, parent); + } +}; + +/** + * Function: filterDescendants + * + * Creates an array of descendant cells + */ +mxHierarchicalLayout.prototype.filterDescendants = function(cell) +{ + var model = this.graph.model; + var result = []; + + if (model.isVertex(cell) && cell != this.parent && this.graph.isCellVisible(cell)) + { + result.push(cell); + } + + if (this.traverseAncestors || cell == this.parent + && this.graph.isCellVisible(cell)) + { + var childCount = model.getChildCount(cell); + + for (var i = 0; i < childCount; i++) + { + var child = model.getChildAt(cell, i); + var children = this.filterDescendants(child); + + for (var j = 0; j < children.length; j++) + { + result[mxCellPath.create(children[j])] = children[j]; + } + } + } + + return result; +}; + +/** + * Traverses the (directed) graph invoking the given function for each + * visited vertex and edge. The function is invoked with the current vertex + * and the incoming edge as a parameter. This implementation makes sure + * each vertex is only visited once. The function may return false if the + * traversal should stop at the given vertex. + * + * Parameters: + * + * vertex - that represents the vertex where the traversal starts. + * directed - boolean indicating if edges should only be traversed + * from source to target. Default is true. + * edge - Optional that represents the incoming edge. This is + * null for the first step of the traversal. + * allVertices - Array of cell paths for the visited cells. + */ +mxHierarchicalLayout.prototype.traverse = function(vertex, directed, edge, allVertices, currentComp, + hierarchyVertices, filledVertexSet) +{ + var view = this.graph.view; + var model = this.graph.model; + + if (vertex != null && allVertices != null) + { + // Has this vertex been seen before in any traversal + // And if the filled vertex set is populated, only + // process vertices in that it contains + var vertexID = mxCellPath.create(vertex); + + if ((allVertices[vertexID] == null) + && (filledVertexSet == null ? true : filledVertexSet[vertexID] != null)) + { + if (currentComp[vertexID] == null) + { + currentComp[vertexID] = vertex; + } + if (allVertices[vertexID] == null) + { + allVertices[vertexID] = vertex; + } + + delete filledVertexSet[vertexID]; + + var edgeCount = model.getEdgeCount(vertex); + + if (edgeCount > 0) + { + for (var i = 0; i < edgeCount; i++) + { + var e = model.getEdgeAt(vertex, i); + var isSource = view.getVisibleTerminal(e, true) == vertex; + + if (!directed || isSource) + { + var next = view.getVisibleTerminal(e, !isSource); + currentComp = this.traverse(next, directed, e, allVertices, + currentComp, hierarchyVertices, + filledVertexSet); + } + } + } + } + else + { + if (currentComp[vertexID] == null) + { + // We've seen this vertex before, but not in the current component + // This component and the one it's in need to be merged + + for (var i = 0; i < hierarchyVertices.length; i++) + { + var comp = hierarchyVertices[i]; + + if (comp[vertexID] != null) + { + for (var key in currentComp) + { + comp[key] = currentComp[key]; + } + + // Remove the current component from the hierarchy set + hierarchyVertices.pop(); + return comp; + } + } + } + } + } + + return currentComp; +}; + +/** + * Function: cycleStage + * + * Executes the cycle stage using mxMinimumCycleRemover. + */ +mxHierarchicalLayout.prototype.cycleStage = function(parent) +{ + var cycleStage = new mxMinimumCycleRemover(this); + cycleStage.execute(parent); +}; + +/** + * Function: layeringStage + * + * Implements first stage of a Sugiyama layout. + */ +mxHierarchicalLayout.prototype.layeringStage = function() +{ + this.model.initialRank(); + this.model.fixRanks(); +}; + +/** + * Function: crossingStage + * + * Executes the crossing stage using mxMedianHybridCrossingReduction. + */ +mxHierarchicalLayout.prototype.crossingStage = function(parent) +{ + var crossingStage = new mxMedianHybridCrossingReduction(this); + crossingStage.execute(parent); +}; + +/** + * Function: placementStage + * + * Executes the placement stage using mxCoordinateAssignment. + */ +mxHierarchicalLayout.prototype.placementStage = function(initialX, parent) +{ + var placementStage = new mxCoordinateAssignment(this, this.intraCellSpacing, + this.interRankCellSpacing, this.orientation, initialX, + this.parallelEdgeSpacing); + placementStage.fineTuning = this.fineTuning; + placementStage.execute(parent); + + return placementStage.limitX + this.interHierarchySpacing; +}; diff --git a/src/js/layout/hierarchical/stage/mxCoordinateAssignment.js b/src/js/layout/hierarchical/stage/mxCoordinateAssignment.js new file mode 100644 index 0000000..8b73ccf --- /dev/null +++ b/src/js/layout/hierarchical/stage/mxCoordinateAssignment.js @@ -0,0 +1,1836 @@ +/** + * $Id: mxCoordinateAssignment.js,v 1.29 2012-06-21 14:28:09 david Exp $ + * Copyright (c) 2005-2012, JGraph Ltd + */ +/** + * Class: mxCoordinateAssignment + * + * Sets the horizontal locations of node and edge dummy nodes on each layer. + * Uses median down and up weighings as well as heuristics to straighten edges as + * far as possible. + * + * Constructor: mxCoordinateAssignment + * + * Creates a coordinate assignment. + * + * Arguments: + * + * intraCellSpacing - the minimum buffer between cells on the same rank + * interRankCellSpacing - the minimum distance between cells on adjacent ranks + * orientation - the position of the root node(s) relative to the graph + * initialX - the leftmost coordinate node placement starts at + */ +function mxCoordinateAssignment(layout, intraCellSpacing, interRankCellSpacing, + orientation, initialX, parallelEdgeSpacing) +{ + this.layout = layout; + this.intraCellSpacing = intraCellSpacing; + this.interRankCellSpacing = interRankCellSpacing; + this.orientation = orientation; + this.initialX = initialX; + this.parallelEdgeSpacing = parallelEdgeSpacing; +}; + +var mxHierarchicalEdgeStyle = +{ + ORTHOGONAL: 1, + POLYLINE: 2, + STRAIGHT: 3 +}; + +/** + * Extends mxHierarchicalLayoutStage. + */ +mxCoordinateAssignment.prototype = new mxHierarchicalLayoutStage(); +mxCoordinateAssignment.prototype.constructor = mxCoordinateAssignment; + +/** + * Variable: layout + * + * Reference to the enclosing . + */ +mxCoordinateAssignment.prototype.layout = null; + +/** + * Variable: intraCellSpacing + * + * The minimum buffer between cells on the same rank. Default is 30. + */ +mxCoordinateAssignment.prototype.intraCellSpacing = 30; + +/** + * Variable: interRankCellSpacing + * + * The minimum distance between cells on adjacent ranks. Default is 10. + */ +mxCoordinateAssignment.prototype.interRankCellSpacing = 10; + +/** + * Variable: parallelEdgeSpacing + * + * The distance between each parallel edge on each ranks for long edges. + * Default is 10. + */ +mxCoordinateAssignment.prototype.parallelEdgeSpacing = 10; + +/** + * Variable: maxIterations + * + * The number of heuristic iterations to run. Default is 8. + */ +mxCoordinateAssignment.prototype.maxIterations = 8; + +/** + * Variable: prefHozEdgeSep + * + * The preferred horizontal distance between edges exiting a vertex + */ +mxCoordinateAssignment.prototype.prefHozEdgeSep = 5; + +/** + * Variable: prefVertEdgeOff + * + * The preferred vertical offset between edges exiting a vertex + */ +mxCoordinateAssignment.prototype.prefVertEdgeOff = 2; + +/** + * Variable: minEdgeJetty + * + * The minimum distance for an edge jetty from a vertex + */ +mxCoordinateAssignment.prototype.minEdgeJetty = 12; + +/** + * Variable: channelBuffer + * + * The size of the vertical buffer in the center of inter-rank channels + * where edge control points should not be placed + */ +mxCoordinateAssignment.prototype.channelBuffer = 4; + +/** + * Variable: jettyPositions + * + * Map of internal edges and (x,y) pair of positions of the start and end jetty + * for that edge where it connects to the source and target vertices. + * Note this should technically be a WeakHashMap, but since JS does not + * have an equivalent, housekeeping must be performed before using. + * i.e. check all edges are still in the model and clear the values. + * Note that the y co-ord is the offset of the jetty, not the + * absolute point + */ +mxCoordinateAssignment.prototype.jettyPositions = null; + +/** + * Variable: orientation + * + * The position of the root ( start ) node(s) relative to the rest of the + * laid out graph. Default is . + */ +mxCoordinateAssignment.prototype.orientation = mxConstants.DIRECTION_NORTH; + +/** + * Variable: initialX + * + * The minimum x position node placement starts at + */ +mxCoordinateAssignment.prototype.initialX = null; + +/** + * Variable: limitX + * + * The maximum x value this positioning lays up to + */ +mxCoordinateAssignment.prototype.limitX = null; + +/** + * Variable: currentXDelta + * + * The sum of x-displacements for the current iteration + */ +mxCoordinateAssignment.prototype.currentXDelta = null; + +/** + * Variable: widestRank + * + * The rank that has the widest x position + */ +mxCoordinateAssignment.prototype.widestRank = null; + +/** + * Variable: rankTopY + * + * Internal cache of top-most values of Y for each rank + */ +mxCoordinateAssignment.prototype.rankTopY = null; + +/** + * Variable: rankBottomY + * + * Internal cache of bottom-most value of Y for each rank + */ +mxCoordinateAssignment.prototype.rankBottomY = null; + +/** + * Variable: widestRankValue + * + * The X-coordinate of the edge of the widest rank + */ +mxCoordinateAssignment.prototype.widestRankValue = null; + +/** + * Variable: rankWidths + * + * The width of all the ranks + */ +mxCoordinateAssignment.prototype.rankWidths = null; + +/** + * Variable: rankY + * + * The Y-coordinate of all the ranks + */ +mxCoordinateAssignment.prototype.rankY = null; + +/** + * Variable: fineTuning + * + * Whether or not to perform local optimisations and iterate multiple times + * through the algorithm. Default is true. + */ +mxCoordinateAssignment.prototype.fineTuning = true; + +/** + * Variable: edgeStyle + * + * The style to apply between cell layers to edge segments + */ +mxCoordinateAssignment.prototype.edgeStyle = mxHierarchicalEdgeStyle.POLYLINE; + +/** + * Variable: nextLayerConnectedCache + * + * A store of connections to the layer above for speed + */ +mxCoordinateAssignment.prototype.nextLayerConnectedCache = null; + +/** + * Variable: previousLayerConnectedCache + * + * A store of connections to the layer below for speed + */ +mxCoordinateAssignment.prototype.previousLayerConnectedCache = null; + +/** + * Variable: groupPadding + * + * Padding added to resized parents + */ +mxCoordinateAssignment.prototype.groupPadding = 10; + +/** + * Utility method to display current positions + */ +mxCoordinateAssignment.prototype.printStatus = function() +{ + var model = this.layout.getModel(); + mxLog.show(); + + mxLog.writeln('======Coord assignment debug======='); + + for (var j = 0; j < model.ranks.length; j++) + { + mxLog.write('Rank ', j, ' : ' ); + var rank = model.ranks[j]; + + for (var k = 0; k < rank.length; k++) + { + var cell = rank[k]; + + mxLog.write(cell.getGeneralPurposeVariable(j), ' '); + } + mxLog.writeln(); + } + + mxLog.writeln('===================================='); +}; + +/** + * Function: execute + * + * A basic horizontal coordinate assignment algorithm + */ +mxCoordinateAssignment.prototype.execute = function(parent) +{ + this.jettyPositions = []; + var model = this.layout.getModel(); + this.currentXDelta = 0.0; + + this.initialCoords(this.layout.getGraph(), model); + +// this.printStatus(); + + if (this.fineTuning) + { + this.minNode(model); + } + + var bestXDelta = 100000000.0; + + if (this.fineTuning) + { + for (var i = 0; i < this.maxIterations; i++) + { +// this.printStatus(); + + // Median Heuristic + if (i != 0) + { + this.medianPos(i, model); + this.minNode(model); + } + + // if the total offset is less for the current positioning, + // there are less heavily angled edges and so the current + // positioning is used + if (this.currentXDelta < bestXDelta) + { + for (var j = 0; j < model.ranks.length; j++) + { + var rank = model.ranks[j]; + + for (var k = 0; k < rank.length; k++) + { + var cell = rank[k]; + cell.setX(j, cell.getGeneralPurposeVariable(j)); + } + } + + bestXDelta = this.currentXDelta; + } + else + { + // Restore the best positions + for (var j = 0; j < model.ranks.length; j++) + { + var rank = model.ranks[j]; + + for (var k = 0; k < rank.length; k++) + { + var cell = rank[k]; + cell.setGeneralPurposeVariable(j, cell.getX(j)); + } + } + } + + this.minPath(this.layout.getGraph(), model); + + this.currentXDelta = 0; + } + } + + this.setCellLocations(this.layout.getGraph(), model); +}; + +/** + * Function: minNode + * + * Performs one median positioning sweep in both directions + */ +mxCoordinateAssignment.prototype.minNode = function(model) +{ + // Queue all nodes + var nodeList = []; + + // Need to be able to map from cell to cellWrapper + var map = []; + var rank = []; + + for (var i = 0; i <= model.maxRank; i++) + { + rank[i] = model.ranks[i]; + + for (var j = 0; j < rank[i].length; j++) + { + // Use the weight to store the rank and visited to store whether + // or not the cell is in the list + var node = rank[i][j]; + var nodeWrapper = new WeightedCellSorter(node, i); + nodeWrapper.rankIndex = j; + nodeWrapper.visited = true; + nodeList.push(nodeWrapper); + + var cellId = mxCellPath.create(node.getCoreCell()); + map[cellId] = nodeWrapper; + } + } + + // Set a limit of the maximum number of times we will access the queue + // in case a loop appears + var maxTries = nodeList.length * 10; + var count = 0; + + // Don't move cell within this value of their median + var tolerance = 1; + + while (nodeList.length > 0 && count <= maxTries) + { + var cellWrapper = nodeList.shift(); + var cell = cellWrapper.cell; + + var rankValue = cellWrapper.weightedValue; + var rankIndex = parseInt(cellWrapper.rankIndex); + + var nextLayerConnectedCells = cell.getNextLayerConnectedCells(rankValue); + var previousLayerConnectedCells = cell.getPreviousLayerConnectedCells(rankValue); + + var numNextLayerConnected = nextLayerConnectedCells.length; + var numPreviousLayerConnected = previousLayerConnectedCells.length; + + var medianNextLevel = this.medianXValue(nextLayerConnectedCells, + rankValue + 1); + var medianPreviousLevel = this.medianXValue(previousLayerConnectedCells, + rankValue - 1); + + var numConnectedNeighbours = numNextLayerConnected + + numPreviousLayerConnected; + var currentPosition = cell.getGeneralPurposeVariable(rankValue); + var cellMedian = currentPosition; + + if (numConnectedNeighbours > 0) + { + cellMedian = (medianNextLevel * numNextLayerConnected + medianPreviousLevel + * numPreviousLayerConnected) + / numConnectedNeighbours; + } + + // Flag storing whether or not position has changed + var positionChanged = false; + + if (cellMedian < currentPosition - tolerance) + { + if (rankIndex == 0) + { + cell.setGeneralPurposeVariable(rankValue, cellMedian); + positionChanged = true; + } + else + { + var leftCell = rank[rankValue][rankIndex - 1]; + var leftLimit = leftCell + .getGeneralPurposeVariable(rankValue); + leftLimit = leftLimit + leftCell.width / 2 + + this.intraCellSpacing + cell.width / 2; + + if (leftLimit < cellMedian) + { + cell.setGeneralPurposeVariable(rankValue, cellMedian); + positionChanged = true; + } + else if (leftLimit < cell + .getGeneralPurposeVariable(rankValue) + - tolerance) + { + cell.setGeneralPurposeVariable(rankValue, leftLimit); + positionChanged = true; + } + } + } + else if (cellMedian > currentPosition + tolerance) + { + var rankSize = rank[rankValue].length; + + if (rankIndex == rankSize - 1) + { + cell.setGeneralPurposeVariable(rankValue, cellMedian); + positionChanged = true; + } + else + { + var rightCell = rank[rankValue][rankIndex + 1]; + var rightLimit = rightCell + .getGeneralPurposeVariable(rankValue); + rightLimit = rightLimit - rightCell.width / 2 + - this.intraCellSpacing - cell.width / 2; + + if (rightLimit > cellMedian) + { + cell.setGeneralPurposeVariable(rankValue, cellMedian); + positionChanged = true; + } + else if (rightLimit > cell + .getGeneralPurposeVariable(rankValue) + + tolerance) + { + cell.setGeneralPurposeVariable(rankValue, rightLimit); + positionChanged = true; + } + } + } + + if (positionChanged) + { + // Add connected nodes to map and list + for (var i = 0; i < nextLayerConnectedCells.length; i++) + { + var connectedCell = nextLayerConnectedCells[i]; + var connectedCellId = mxCellPath.create(connectedCell.getCoreCell()); + var connectedCellWrapper = map[connectedCellId]; + + if (connectedCellWrapper != null) + { + if (connectedCellWrapper.visited == false) + { + connectedCellWrapper.visited = true; + nodeList.push(connectedCellWrapper); + } + } + } + + // Add connected nodes to map and list + for (var i = 0; i < previousLayerConnectedCells.length; i++) + { + var connectedCell = previousLayerConnectedCells[i]; + var connectedCellId = mxCellPath.create(connectedCell.getCoreCell()); + var connectedCellWrapper = map[connectedCellId]; + + if (connectedCellWrapper != null) + { + if (connectedCellWrapper.visited == false) + { + connectedCellWrapper.visited = true; + nodeList.push(connectedCellWrapper); + } + } + } + } + + cellWrapper.visited = false; + count++; + } +}; + +/** + * Function: medianPos + * + * Performs one median positioning sweep in one direction + * + * Parameters: + * + * i - the iteration of the whole process + * model - an internal model of the hierarchical layout + */ +mxCoordinateAssignment.prototype.medianPos = function(i, model) +{ + // Reverse sweep direction each time through this method + var downwardSweep = (i % 2 == 0); + + if (downwardSweep) + { + for (var j = model.maxRank; j > 0; j--) + { + this.rankMedianPosition(j - 1, model, j); + } + } + else + { + for (var j = 0; j < model.maxRank - 1; j++) + { + this.rankMedianPosition(j + 1, model, j); + } + } +}; + +/** + * Function: rankMedianPosition + * + * Performs median minimisation over one rank. + * + * Parameters: + * + * rankValue - the layer number of this rank + * model - an internal model of the hierarchical layout + * nextRankValue - the layer number whose connected cels are to be laid out + * relative to + */ +mxCoordinateAssignment.prototype.rankMedianPosition = function(rankValue, model, nextRankValue) +{ + var rank = model.ranks[rankValue]; + + // Form an array of the order in which the cell are to be processed + // , the order is given by the weighted sum of the in or out edges, + // depending on whether we're travelling up or down the hierarchy. + var weightedValues = []; + var cellMap = []; + + for (var i = 0; i < rank.length; i++) + { + var currentCell = rank[i]; + weightedValues[i] = new WeightedCellSorter(); + weightedValues[i].cell = currentCell; + weightedValues[i].rankIndex = i; + var currentCellId = mxCellPath.create(currentCell.getCoreCell()); + cellMap[currentCellId] = weightedValues[i]; + var nextLayerConnectedCells = null; + + if (nextRankValue < rankValue) + { + nextLayerConnectedCells = currentCell + .getPreviousLayerConnectedCells(rankValue); + } + else + { + nextLayerConnectedCells = currentCell + .getNextLayerConnectedCells(rankValue); + } + + // Calculate the weighing based on this node type and those this + // node is connected to on the next layer + weightedValues[i].weightedValue = this.calculatedWeightedValue( + currentCell, nextLayerConnectedCells); + } + + weightedValues.sort(WeightedCellSorter.prototype.compare); + + // Set the new position of each node within the rank using + // its temp variable + + for (var i = 0; i < weightedValues.length; i++) + { + var numConnectionsNextLevel = 0; + var cell = weightedValues[i].cell; + var nextLayerConnectedCells = null; + var medianNextLevel = 0; + + if (nextRankValue < rankValue) + { + nextLayerConnectedCells = cell.getPreviousLayerConnectedCells( + rankValue).slice(); + } + else + { + nextLayerConnectedCells = cell.getNextLayerConnectedCells( + rankValue).slice(); + } + + if (nextLayerConnectedCells != null) + { + numConnectionsNextLevel = nextLayerConnectedCells.length; + + if (numConnectionsNextLevel > 0) + { + medianNextLevel = this.medianXValue(nextLayerConnectedCells, + nextRankValue); + } + else + { + // For case of no connections on the next level set the + // median to be the current position and try to be + // positioned there + medianNextLevel = cell.getGeneralPurposeVariable(rankValue); + } + } + + var leftBuffer = 0.0; + var leftLimit = -100000000.0; + + for (var j = weightedValues[i].rankIndex - 1; j >= 0;) + { + var rankId = mxCellPath.create(rank[j].getCoreCell()); + var weightedValue = cellMap[rankId]; + + if (weightedValue != null) + { + var leftCell = weightedValue.cell; + + if (weightedValue.visited) + { + // The left limit is the right hand limit of that + // cell plus any allowance for unallocated cells + // in-between + leftLimit = leftCell + .getGeneralPurposeVariable(rankValue) + + leftCell.width + / 2.0 + + this.intraCellSpacing + + leftBuffer + cell.width / 2.0; + j = -1; + } + else + { + leftBuffer += leftCell.width + this.intraCellSpacing; + j--; + } + } + } + + var rightBuffer = 0.0; + var rightLimit = 100000000.0; + + for (var j = weightedValues[i].rankIndex + 1; j < weightedValues.length;) + { + var rankId = mxCellPath.create(rank[j].getCoreCell()); + var weightedValue = cellMap[rankId]; + + if (weightedValue != null) + { + var rightCell = weightedValue.cell; + + if (weightedValue.visited) + { + // The left limit is the right hand limit of that + // cell plus any allowance for unallocated cells + // in-between + rightLimit = rightCell + .getGeneralPurposeVariable(rankValue) + - rightCell.width + / 2.0 + - this.intraCellSpacing + - rightBuffer - cell.width / 2.0; + j = weightedValues.length; + } + else + { + rightBuffer += rightCell.width + this.intraCellSpacing; + j++; + } + } + } + + if (medianNextLevel >= leftLimit && medianNextLevel <= rightLimit) + { + cell.setGeneralPurposeVariable(rankValue, medianNextLevel); + } + else if (medianNextLevel < leftLimit) + { + // Couldn't place at median value, place as close to that + // value as possible + cell.setGeneralPurposeVariable(rankValue, leftLimit); + this.currentXDelta += leftLimit - medianNextLevel; + } + else if (medianNextLevel > rightLimit) + { + // Couldn't place at median value, place as close to that + // value as possible + cell.setGeneralPurposeVariable(rankValue, rightLimit); + this.currentXDelta += medianNextLevel - rightLimit; + } + + weightedValues[i].visited = true; + } +}; + +/** + * Function: calculatedWeightedValue + * + * Calculates the priority the specified cell has based on the type of its + * cell and the cells it is connected to on the next layer + * + * Parameters: + * + * currentCell - the cell whose weight is to be calculated + * collection - the cells the specified cell is connected to + */ +mxCoordinateAssignment.prototype.calculatedWeightedValue = function(currentCell, collection) +{ + var totalWeight = 0; + + for (var i = 0; i < collection.length; i++) + { + var cell = collection[i]; + + if (currentCell.isVertex() && cell.isVertex()) + { + totalWeight++; + } + else if (currentCell.isEdge() && cell.isEdge()) + { + totalWeight += 8; + } + else + { + totalWeight += 2; + } + } + + return totalWeight; +}; + +/** + * Function: medianXValue + * + * Calculates the median position of the connected cell on the specified + * rank + * + * Parameters: + * + * connectedCells - the cells the candidate connects to on this level + * rankValue - the layer number of this rank + */ +mxCoordinateAssignment.prototype.medianXValue = function(connectedCells, rankValue) +{ + if (connectedCells.length == 0) + { + return 0; + } + + var medianValues = []; + + for (var i = 0; i < connectedCells.length; i++) + { + medianValues[i] = connectedCells[i].getGeneralPurposeVariable(rankValue); + } + + medianValues.sort(function(a,b){return a - b;}); + + if (connectedCells.length % 2 == 1) + { + // For odd numbers of adjacent vertices return the median + return medianValues[Math.floor(connectedCells.length / 2)]; + } + else + { + var medianPoint = connectedCells.length / 2; + var leftMedian = medianValues[medianPoint - 1]; + var rightMedian = medianValues[medianPoint]; + + return ((leftMedian + rightMedian) / 2); + } +}; + +/** + * Function: initialCoords + * + * Sets up the layout in an initial positioning. The ranks are all centered + * as much as possible along the middle vertex in each rank. The other cells + * are then placed as close as possible on either side. + * + * Parameters: + * + * facade - the facade describing the input graph + * model - an internal model of the hierarchical layout + */ +mxCoordinateAssignment.prototype.initialCoords = function(facade, model) +{ + this.calculateWidestRank(facade, model); + + // Sweep up and down from the widest rank + for (var i = this.widestRank; i >= 0; i--) + { + if (i < model.maxRank) + { + this.rankCoordinates(i, facade, model); + } + } + + for (var i = this.widestRank+1; i <= model.maxRank; i++) + { + if (i > 0) + { + this.rankCoordinates(i, facade, model); + } + } +}; + +/** + * Function: rankCoordinates + * + * Sets up the layout in an initial positioning. All the first cells in each + * rank are moved to the left and the rest of the rank inserted as close + * together as their size and buffering permits. This method works on just + * the specified rank. + * + * Parameters: + * + * rankValue - the current rank being processed + * graph - the facade describing the input graph + * model - an internal model of the hierarchical layout + */ +mxCoordinateAssignment.prototype.rankCoordinates = function(rankValue, graph, model) +{ + var rank = model.ranks[rankValue]; + var maxY = 0.0; + var localX = this.initialX + (this.widestRankValue - this.rankWidths[rankValue]) + / 2; + + // Store whether or not any of the cells' bounds were unavailable so + // to only issue the warning once for all cells + var boundsWarning = false; + + for (var i = 0; i < rank.length; i++) + { + var node = rank[i]; + + if (node.isVertex()) + { + var bounds = this.layout.getVertexBounds(node.cell); + + if (bounds != null) + { + if (this.orientation == mxConstants.DIRECTION_NORTH || + this.orientation == mxConstants.DIRECTION_SOUTH) + { + node.width = bounds.width; + node.height = bounds.height; + } + else + { + node.width = bounds.height; + node.height = bounds.width; + } + } + else + { + boundsWarning = true; + } + + maxY = Math.max(maxY, node.height); + } + else if (node.isEdge()) + { + // The width is the number of additional parallel edges + // time the parallel edge spacing + var numEdges = 1; + + if (node.edges != null) + { + numEdges = node.edges.length; + } + else + { + mxLog.warn('edge.edges is null'); + } + + node.width = (numEdges - 1) * this.parallelEdgeSpacing; + } + + // Set the initial x-value as being the best result so far + localX += node.width / 2.0; + node.setX(rankValue, localX); + node.setGeneralPurposeVariable(rankValue, localX); + localX += node.width / 2.0; + localX += this.intraCellSpacing; + } + + if (boundsWarning == true) + { + mxLog.warn('At least one cell has no bounds'); + } +}; + +/** + * Function: calculateWidestRank + * + * Calculates the width rank in the hierarchy. Also set the y value of each + * rank whilst performing the calculation + * + * Parameters: + * + * graph - the facade describing the input graph + * model - an internal model of the hierarchical layout + */ +mxCoordinateAssignment.prototype.calculateWidestRank = function(graph, model) +{ + // Starting y co-ordinate + var y = -this.interRankCellSpacing; + + // Track the widest cell on the last rank since the y + // difference depends on it + var lastRankMaxCellHeight = 0.0; + this.rankWidths = []; + this.rankY = []; + + for (var rankValue = model.maxRank; rankValue >= 0; rankValue--) + { + // Keep track of the widest cell on this rank + var maxCellHeight = 0.0; + var rank = model.ranks[rankValue]; + var localX = this.initialX; + + // Store whether or not any of the cells' bounds were unavailable so + // to only issue the warning once for all cells + var boundsWarning = false; + + for (var i = 0; i < rank.length; i++) + { + var node = rank[i]; + + if (node.isVertex()) + { + var bounds = this.layout.getVertexBounds(node.cell); + + if (bounds != null) + { + if (this.orientation == mxConstants.DIRECTION_NORTH || + this.orientation == mxConstants.DIRECTION_SOUTH) + { + node.width = bounds.width; + node.height = bounds.height; + } + else + { + node.width = bounds.height; + node.height = bounds.width; + } + } + else + { + boundsWarning = true; + } + + maxCellHeight = Math.max(maxCellHeight, node.height); + } + else if (node.isEdge()) + { + // The width is the number of additional parallel edges + // time the parallel edge spacing + var numEdges = 1; + + if (node.edges != null) + { + numEdges = node.edges.length; + } + else + { + mxLog.warn('edge.edges is null'); + } + + node.width = (numEdges - 1) * this.parallelEdgeSpacing; + } + + // Set the initial x-value as being the best result so far + localX += node.width / 2.0; + node.setX(rankValue, localX); + node.setGeneralPurposeVariable(rankValue, localX); + localX += node.width / 2.0; + localX += this.intraCellSpacing; + + if (localX > this.widestRankValue) + { + this.widestRankValue = localX; + this.widestRank = rankValue; + } + + this.rankWidths[rankValue] = localX; + } + + if (boundsWarning == true) + { + mxLog.warn('At least one cell has no bounds'); + } + + this.rankY[rankValue] = y; + var distanceToNextRank = maxCellHeight / 2.0 + + lastRankMaxCellHeight / 2.0 + this.interRankCellSpacing; + lastRankMaxCellHeight = maxCellHeight; + + if (this.orientation == mxConstants.DIRECTION_NORTH || + this.orientation == mxConstants.DIRECTION_WEST) + { + y += distanceToNextRank; + } + else + { + y -= distanceToNextRank; + } + + for (var i = 0; i < rank.length; i++) + { + var cell = rank[i]; + cell.setY(rankValue, y); + } + } +}; + +/** + * Function: minPath + * + * Straightens out chains of virtual nodes where possibleacade to those stored after this layout + * processing step has completed. + * + * Parameters: + * + * graph - the facade describing the input graph + * model - an internal model of the hierarchical layout + */ +mxCoordinateAssignment.prototype.minPath = function(graph, model) +{ + // Work down and up each edge with at least 2 control points + // trying to straighten each one out. If the same number of + // straight segments are formed in both directions, the + // preferred direction used is the one where the final + // control points have the least offset from the connectable + // region of the terminating vertices + var edges = model.edgeMapper; + + for (var key in edges) + { + var cell = edges[key]; + + if (cell.maxRank - cell.minRank - 1 < 1) + { + continue; + } + + // At least two virtual nodes in the edge + // Check first whether the edge is already straight + var referenceX = cell + .getGeneralPurposeVariable(cell.minRank + 1); + var edgeStraight = true; + var refSegCount = 0; + + for (var i = cell.minRank + 2; i < cell.maxRank; i++) + { + var x = cell.getGeneralPurposeVariable(i); + + if (referenceX != x) + { + edgeStraight = false; + referenceX = x; + } + else + { + refSegCount++; + } + } + + if (!edgeStraight) + { + var upSegCount = 0; + var downSegCount = 0; + var upXPositions = []; + var downXPositions = []; + + var currentX = cell.getGeneralPurposeVariable(cell.minRank + 1); + + for (var i = cell.minRank + 1; i < cell.maxRank - 1; i++) + { + // Attempt to straight out the control point on the + // next segment up with the current control point. + var nextX = cell.getX(i + 1); + + if (currentX == nextX) + { + upXPositions[i - cell.minRank - 1] = currentX; + upSegCount++; + } + else if (this.repositionValid(model, cell, i + 1, currentX)) + { + upXPositions[i - cell.minRank - 1] = currentX; + upSegCount++; + // Leave currentX at same value + } + else + { + upXPositions[i - cell.minRank - 1] = nextX; + currentX = nextX; + } + } + + currentX = cell.getX(i); + + for (var i = cell.maxRank - 1; i > cell.minRank + 1; i--) + { + // Attempt to straight out the control point on the + // next segment down with the current control point. + var nextX = cell.getX(i - 1); + + if (currentX == nextX) + { + downXPositions[i - cell.minRank - 2] = currentX; + downSegCount++; + } + else if (this.repositionValid(model, cell, i - 1, currentX)) + { + downXPositions[i - cell.minRank - 2] = currentX; + downSegCount++; + // Leave currentX at same value + } + else + { + downXPositions[i - cell.minRank - 2] = cell.getX(i-1); + currentX = nextX; + } + } + + if (downSegCount > refSegCount || upSegCount > refSegCount) + { + if (downSegCount >= upSegCount) + { + // Apply down calculation values + for (var i = cell.maxRank - 2; i > cell.minRank; i--) + { + cell.setX(i, downXPositions[i - cell.minRank - 1]); + } + } + else if (upSegCount > downSegCount) + { + // Apply up calculation values + for (var i = cell.minRank + 2; i < cell.maxRank; i++) + { + cell.setX(i, upXPositions[i - cell.minRank - 2]); + } + } + else + { + // Neither direction provided a favourable result + // But both calculations are better than the + // existing solution, so apply the one with minimal + // offset to attached vertices at either end. + } + } + } + } +}; + +/** + * Function: repositionValid + * + * Determines whether or not a node may be moved to the specified x + * position on the specified rank + * + * Parameters: + * + * model - the layout model + * cell - the cell being analysed + * rank - the layer of the cell + * position - the x position being sought + */ +mxCoordinateAssignment.prototype.repositionValid = function(model, cell, rank, position) +{ + var rankArray = model.ranks[rank]; + var rankIndex = -1; + + for (var i = 0; i < rankArray.length; i++) + { + if (cell == rankArray[i]) + { + rankIndex = i; + break; + } + } + + if (rankIndex < 0) + { + return false; + } + + var currentX = cell.getGeneralPurposeVariable(rank); + + if (position < currentX) + { + // Trying to move node to the left. + if (rankIndex == 0) + { + // Left-most node, can move anywhere + return true; + } + + var leftCell = rankArray[rankIndex - 1]; + var leftLimit = leftCell.getGeneralPurposeVariable(rank); + leftLimit = leftLimit + leftCell.width / 2 + + this.intraCellSpacing + cell.width / 2; + + if (leftLimit <= position) + { + return true; + } + else + { + return false; + } + } + else if (position > currentX) + { + // Trying to move node to the right. + if (rankIndex == rankArray.length - 1) + { + // Right-most node, can move anywhere + return true; + } + + var rightCell = rankArray[rankIndex + 1]; + var rightLimit = rightCell.getGeneralPurposeVariable(rank); + rightLimit = rightLimit - rightCell.width / 2 + - this.intraCellSpacing - cell.width / 2; + + if (rightLimit >= position) + { + return true; + } + else + { + return false; + } + } + + return true; +}; + +/** + * Function: setCellLocations + * + * Sets the cell locations in the facade to those stored after this layout + * processing step has completed. + * + * Parameters: + * + * graph - the input graph + * model - the layout model + */ +mxCoordinateAssignment.prototype.setCellLocations = function(graph, model) +{ + this.rankTopY = []; + this.rankBottomY = []; + + for (var i = 0; i < model.ranks.length; i++) + { + this.rankTopY[i] = Number.MAX_VALUE; + this.rankBottomY[i] = 0.0; + } + + var parentsChanged = null; + + if (this.layout.resizeParent) + { + parentsChanged = new Object(); + } + + var edges = model.edgeMapper; + var vertices = model.vertexMapper; + + // Process vertices all first, since they define the lower and + // limits of each rank. Between these limits lie the channels + // where the edges can be routed across the graph + + for (var key in vertices) + { + var vertex = vertices[key]; + this.setVertexLocation(vertex); + + if (this.layout.resizeParent) + { + var parent = graph.model.getParent(vertex.cell); + var id = mxCellPath.create(parent); + + // Implements set semantic + if (parentsChanged[id] == null) + { + parentsChanged[id] = parent; + } + } + } + + if (this.layout.resizeParent && parentsChanged != null) + { + this.adjustParents(parentsChanged); + } + + // Post process edge styles. Needs the vertex locations set for initial + // values of the top and bottoms of each rank + if (this.edgeStyle == mxHierarchicalEdgeStyle.ORTHOGONAL + || this.edgeStyle == mxHierarchicalEdgeStyle.POLYLINE) + { + this.localEdgeProcessing(model); + } + + for (var key in edges) + { + this.setEdgePosition(edges[key]); + } +}; + +/** + * 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. + */ +mxCoordinateAssignment.prototype.adjustParents = function(parentsChanged) +{ + var tmp = []; + + for (var id in parentsChanged) + { + tmp.push(parentsChanged[id]); + } + + this.layout.arrangeGroups(mxUtils.sortCells(tmp, true), this.groupPadding); +}; + +/** + * Function: localEdgeProcessing + * + * Separates the x position of edges as they connect to vertices + * + * Parameters: + * + * model - the layout model + */ +mxCoordinateAssignment.prototype.localEdgeProcessing = function(model) +{ + var edgeMapping = model.edgeMapper; + + // Iterate through each vertex, look at the edges connected in + // both directions. + for (var rankIndex = 0; rankIndex < model.ranks.length; rankIndex++) + { + var rank = model.ranks[rankIndex]; + + for (var cellIndex = 0; cellIndex < rank.length; cellIndex++) + { + var cell = rank[cellIndex]; + + if (cell.isVertex()) + { + var currentCells = cell.getPreviousLayerConnectedCells(rankIndex); + + var currentRank = rankIndex - 1; + + // Two loops, last connected cells, and next + for (var k = 0; k < 2; k++) + { + if (currentRank > -1 + && currentRank < model.ranks.length + && currentCells != null + && currentCells.length > 0) + { + var sortedCells = []; + + for (var j = 0; j < currentCells.length; j++) + { + var sorter = new WeightedCellSorter( + currentCells[j], currentCells[j].getX(currentRank)); + sortedCells.push(sorter); + } + + sortedCells.sort(WeightedCellSorter.prototype.compare); + + var leftLimit = cell.x[0] - cell.width / 2; + var rightLimit = leftLimit + cell.width; + + // Connected edge count starts at 1 to allow for buffer + // with edge of vertex + var connectedEdgeCount = 0; + var connectedEdgeGroupCount = 0; + var connectedEdges = []; + // Calculate width requirements for all connected edges + for (var j = 0; j < sortedCells.length; j++) + { + var innerCell = sortedCells[j].cell; + var connections; + + if (innerCell.isVertex()) + { + // Get the connecting edge + if (k == 0) + { + connections = cell.connectsAsSource; + + } + else + { + connections = cell.connectsAsTarget; + } + + for (var connIndex = 0; connIndex < connections.length; connIndex++) + { + if (connections[connIndex].source == innerCell + || connections[connIndex].target == innerCell) + { + connectedEdgeCount += connections[connIndex].edges + .length; + connectedEdgeGroupCount++; + + connectedEdges.push(connections[connIndex]); + } + } + } + else + { + connectedEdgeCount += innerCell.edges.length; + connectedEdgeGroupCount++; + connectedEdges.push(innerCell); + } + } + + var requiredWidth = (connectedEdgeCount + 1) + * this.prefHozEdgeSep; + + // Add a buffer on the edges of the vertex if the edge count allows + if (cell.width > requiredWidth + + (2 * this.prefHozEdgeSep)) + { + leftLimit += this.prefHozEdgeSep; + rightLimit -= this.prefHozEdgeSep; + } + + var availableWidth = rightLimit - leftLimit; + var edgeSpacing = availableWidth / connectedEdgeCount; + + var currentX = leftLimit + edgeSpacing / 2.0; + var currentYOffset = this.minEdgeJetty - this.prefVertEdgeOff; + var maxYOffset = 0; + + for (var j = 0; j < connectedEdges.length; j++) + { + var numActualEdges = connectedEdges[j].edges + .length; + var edgeId = mxCellPath.create(connectedEdges[j].edges[0]); + var pos = this.jettyPositions[edgeId]; + + if (pos == null) + { + pos = []; + this.jettyPositions[edgeId] = pos; + } + + if (j < connectedEdgeCount / 2) + { + currentYOffset += this.prefVertEdgeOff; + } + else if (j > connectedEdgeCount / 2) + { + currentYOffset -= this.prefVertEdgeOff; + } + // Ignore the case if equals, this means the second of 2 + // jettys with the same y (even number of edges) + + for (var m = 0; m < numActualEdges; m++) + { + pos[m * 4 + k * 2] = currentX; + currentX += edgeSpacing; + pos[m * 4 + k * 2 + 1] = currentYOffset; + } + + maxYOffset = Math.max(maxYOffset, + currentYOffset); + } + } + + currentCells = cell.getNextLayerConnectedCells(rankIndex); + + currentRank = rankIndex + 1; + } + } + } + } +}; + +/** + * Function: setEdgePosition + * + * Fixes the control points + */ +mxCoordinateAssignment.prototype.setEdgePosition = function(cell) +{ + // For parallel edges we need to seperate out the points a + // little + var offsetX = 0; + // Only set the edge control points once + + if (cell.temp[0] != 101207) + { + var maxRank = cell.maxRank; + var minRank = cell.minRank; + + if (maxRank == minRank) + { + maxRank = cell.source.maxRank; + minRank = cell.target.minRank; + } + + var parallelEdgeCount = 0; + var edgeId = mxCellPath.create(cell.edges[0]); + var jettys = this.jettyPositions[edgeId]; + + var source = cell.isReversed ? cell.target.cell : cell.source.cell; + + for (var i = 0; i < cell.edges.length; i++) + { + var realEdge = cell.edges[i]; + var realSource = this.layout.graph.view.getVisibleTerminal(realEdge, true); + + //List oldPoints = graph.getPoints(realEdge); + var newPoints = []; + + // Single length reversed edges end up with the jettys in the wrong + // places. Since single length edges only have jettys, not segment + // control points, we just say the edge isn't reversed in this section + var reversed = cell.isReversed; + + if (realSource != source) + { + // The real edges include all core model edges and these can go + // in both directions. If the source of the hierarchical model edge + // isn't the source of the specific real edge in this iteration + // treat if as reversed + reversed = !reversed; + } + + // First jetty of edge + if (jettys != null) + { + var arrayOffset = reversed ? 2 : 0; + var y = reversed ? this.rankTopY[minRank] : this.rankBottomY[maxRank]; + var jetty = jettys[parallelEdgeCount * 4 + 1 + arrayOffset]; + + if (reversed) + { + jetty = -jetty; + } + + y += jetty; + var x = jettys[parallelEdgeCount * 4 + arrayOffset]; + + if (this.orientation == mxConstants.DIRECTION_NORTH + || this.orientation == mxConstants.DIRECTION_SOUTH) + { + newPoints.push(new mxPoint(x, y)); + } + else + { + newPoints.push(new mxPoint(y, x)); + } + } + + // Declare variables to define loop through edge points and + // change direction if edge is reversed + + var loopStart = cell.x.length - 1; + var loopLimit = -1; + var loopDelta = -1; + var currentRank = cell.maxRank - 1; + + if (reversed) + { + loopStart = 0; + loopLimit = cell.x.length; + loopDelta = 1; + currentRank = cell.minRank + 1; + } + // Reversed edges need the points inserted in + // reverse order + for (var j = loopStart; (cell.maxRank != cell.minRank) && j != loopLimit; j += loopDelta) + { + // The horizontal position in a vertical layout + var positionX = cell.x[j] + offsetX; + + // Work out the vertical positions in a vertical layout + // in the edge buffer channels above and below this rank + var topChannelY = (this.rankTopY[currentRank] + this.rankBottomY[currentRank + 1]) / 2.0; + var bottomChannelY = (this.rankTopY[currentRank - 1] + this.rankBottomY[currentRank]) / 2.0; + + if (reversed) + { + var tmp = topChannelY; + topChannelY = bottomChannelY; + bottomChannelY = tmp; + } + + if (this.orientation == mxConstants.DIRECTION_NORTH || + this.orientation == mxConstants.DIRECTION_SOUTH) + { + newPoints.push(new mxPoint(positionX, topChannelY)); + newPoints.push(new mxPoint(positionX, bottomChannelY)); + } + else + { + newPoints.push(new mxPoint(topChannelY, positionX)); + newPoints.push(new mxPoint(bottomChannelY, positionX)); + } + + this.limitX = Math.max(this.limitX, positionX); + currentRank += loopDelta; + } + + // Second jetty of edge + if (jettys != null) + { + var arrayOffset = reversed ? 2 : 0; + var rankY = reversed ? this.rankBottomY[maxRank] : this.rankTopY[minRank]; + var jetty = jettys[parallelEdgeCount * 4 + 3 - arrayOffset]; + + if (reversed) + { + jetty = -jetty; + } + var y = rankY - jetty; + var x = jettys[parallelEdgeCount * 4 + 2 - arrayOffset]; + + if (this.orientation == mxConstants.DIRECTION_NORTH || + this.orientation == mxConstants.DIRECTION_SOUTH) + { + newPoints.push(new mxPoint(x, y)); + } + else + { + newPoints.push(new mxPoint(y, x)); + } + } + + if (cell.isReversed) + { + this.processReversedEdge(cell, realEdge); + } + + this.layout.setEdgePoints(realEdge, newPoints); + + // Increase offset so next edge is drawn next to + // this one + if (offsetX == 0.0) + { + offsetX = this.parallelEdgeSpacing; + } + else if (offsetX > 0) + { + offsetX = -offsetX; + } + else + { + offsetX = -offsetX + this.parallelEdgeSpacing; + } + + parallelEdgeCount++; + } + + cell.temp[0] = 101207; + } +}; + + +/** + * Function: setVertexLocation + * + * Fixes the position of the specified vertex. + * + * Parameters: + * + * cell - the vertex to position + */ +mxCoordinateAssignment.prototype.setVertexLocation = function(cell) +{ + var realCell = cell.cell; + var positionX = cell.x[0] - cell.width / 2; + var positionY = cell.y[0] - cell.height / 2; + + this.rankTopY[cell.minRank] = Math.min(this.rankTopY[cell.minRank], positionY); + this.rankBottomY[cell.minRank] = Math.max(this.rankBottomY[cell.minRank], + positionY + cell.height); + + if (this.orientation == mxConstants.DIRECTION_NORTH || + this.orientation == mxConstants.DIRECTION_SOUTH) + { + this.layout.setVertexLocation(realCell, positionX, positionY); + } + else + { + this.layout.setVertexLocation(realCell, positionY, positionX); + } + + this.limitX = Math.max(this.limitX, positionX + cell.width); +}; + +/** + * Function: processReversedEdge + * + * Hook to add additional processing + * + * Parameters: + * + * edge - the hierarchical model edge + * realEdge - the real edge in the graph + */ +mxCoordinateAssignment.prototype.processReversedEdge = function(graph, model) +{ + // hook for subclassers +}; + +/** + * 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; + } +}; diff --git a/src/js/layout/hierarchical/stage/mxHierarchicalLayoutStage.js b/src/js/layout/hierarchical/stage/mxHierarchicalLayoutStage.js new file mode 100644 index 0000000..2e635fc --- /dev/null +++ b/src/js/layout/hierarchical/stage/mxHierarchicalLayoutStage.js @@ -0,0 +1,25 @@ +/** + * $Id: mxHierarchicalLayoutStage.js,v 1.8 2010-01-02 09:45:15 gaudenz Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxHierarchicalLayoutStage + * + * The specific layout interface for hierarchical layouts. It adds a + * run method with a parameter for the hierarchical layout model + * that is shared between the layout stages. + * + * Constructor: mxHierarchicalLayoutStage + * + * Constructs a new hierarchical layout stage. + */ +function mxHierarchicalLayoutStage() { }; + +/** + * Function: execute + * + * Takes the graph detail and configuration information within the facade + * and creates the resulting laid out graph within that facade for further + * use. + */ +mxHierarchicalLayoutStage.prototype.execute = function(parent) { }; diff --git a/src/js/layout/hierarchical/stage/mxMedianHybridCrossingReduction.js b/src/js/layout/hierarchical/stage/mxMedianHybridCrossingReduction.js new file mode 100644 index 0000000..997890e --- /dev/null +++ b/src/js/layout/hierarchical/stage/mxMedianHybridCrossingReduction.js @@ -0,0 +1,674 @@ +/** + * $Id: mxMedianHybridCrossingReduction.js,v 1.25 2012-06-07 11:16:41 david Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxMedianHybridCrossingReduction + * + * Sets the horizontal locations of node and edge dummy nodes on each layer. + * Uses median down and up weighings as well heuristic to straighten edges as + * far as possible. + * + * Constructor: mxMedianHybridCrossingReduction + * + * Creates a coordinate assignment. + * + * Arguments: + * + * intraCellSpacing - the minimum buffer between cells on the same rank + * interRankCellSpacing - the minimum distance between cells on adjacent ranks + * orientation - the position of the root node(s) relative to the graph + * initialX - the leftmost coordinate node placement starts at + */ +function mxMedianHybridCrossingReduction(layout) +{ + this.layout = layout; +}; + +/** + * Extends mxMedianHybridCrossingReduction. + */ +mxMedianHybridCrossingReduction.prototype = new mxHierarchicalLayoutStage(); +mxMedianHybridCrossingReduction.prototype.constructor = mxMedianHybridCrossingReduction; + +/** + * Variable: layout + * + * Reference to the enclosing . + */ +mxMedianHybridCrossingReduction.prototype.layout = null; + +/** + * Variable: maxIterations + * + * The maximum number of iterations to perform whilst reducing edge + * crossings. Default is 24. + */ +mxMedianHybridCrossingReduction.prototype.maxIterations = 24; + +/** + * Variable: nestedBestRanks + * + * Stores each rank as a collection of cells in the best order found for + * each layer so far + */ +mxMedianHybridCrossingReduction.prototype.nestedBestRanks = null; + +/** + * Variable: currentBestCrossings + * + * The total number of crossings found in the best configuration so far + */ +mxMedianHybridCrossingReduction.prototype.currentBestCrossings = 0; + +/** + * Variable: iterationsWithoutImprovement + * + * The total number of crossings found in the best configuration so far + */ +mxMedianHybridCrossingReduction.prototype.iterationsWithoutImprovement = 0; + +/** + * Variable: maxNoImprovementIterations + * + * The total number of crossings found in the best configuration so far + */ +mxMedianHybridCrossingReduction.prototype.maxNoImprovementIterations = 2; + +/** + * Function: execute + * + * Performs a vertex ordering within ranks as described by Gansner et al + * 1993 + */ +mxMedianHybridCrossingReduction.prototype.execute = function(parent) +{ + var model = this.layout.getModel(); + + // Stores initial ordering as being the best one found so far + this.nestedBestRanks = []; + + for (var i = 0; i < model.ranks.length; i++) + { + this.nestedBestRanks[i] = model.ranks[i].slice(); + } + + var iterationsWithoutImprovement = 0; + var currentBestCrossings = this.calculateCrossings(model); + + for (var i = 0; i < this.maxIterations && + iterationsWithoutImprovement < this.maxNoImprovementIterations; i++) + { + this.weightedMedian(i, model); + this.transpose(i, model); + var candidateCrossings = this.calculateCrossings(model); + + if (candidateCrossings < currentBestCrossings) + { + currentBestCrossings = candidateCrossings; + iterationsWithoutImprovement = 0; + + // Store the current rankings as the best ones + for (var j = 0; j < this.nestedBestRanks.length; j++) + { + var rank = model.ranks[j]; + + for (var k = 0; k < rank.length; k++) + { + var cell = rank[k]; + this.nestedBestRanks[j][cell.getGeneralPurposeVariable(j)] = cell; + } + } + } + else + { + // Increase count of iterations where we haven't improved the + // layout + iterationsWithoutImprovement++; + + // Restore the best values to the cells + for (var j = 0; j < this.nestedBestRanks.length; j++) + { + var rank = model.ranks[j]; + + for (var k = 0; k < rank.length; k++) + { + var cell = rank[k]; + cell.setGeneralPurposeVariable(j, k); + } + } + } + + if (currentBestCrossings == 0) + { + // Do nothing further + break; + } + } + + // Store the best rankings but in the model + var ranks = []; + var rankList = []; + + for (var i = 0; i < model.maxRank + 1; i++) + { + rankList[i] = []; + ranks[i] = rankList[i]; + } + + for (var i = 0; i < this.nestedBestRanks.length; i++) + { + for (var j = 0; j < this.nestedBestRanks[i].length; j++) + { + rankList[i].push(this.nestedBestRanks[i][j]); + } + } + + model.ranks = ranks; +}; + + +/** + * Function: calculateCrossings + * + * Calculates the total number of edge crossing in the current graph. + * Returns the current number of edge crossings in the hierarchy graph + * model in the current candidate layout + * + * Parameters: + * + * model - the internal model describing the hierarchy + */ +mxMedianHybridCrossingReduction.prototype.calculateCrossings = function(model) +{ + var numRanks = model.ranks.length; + var totalCrossings = 0; + + for (var i = 1; i < numRanks; i++) + { + totalCrossings += this.calculateRankCrossing(i, model); + } + + return totalCrossings; +}; + +/** + * Function: calculateRankCrossing + * + * Calculates the number of edges crossings between the specified rank and + * the rank below it. Returns the number of edges crossings with the rank + * beneath + * + * Parameters: + * + * i - the topmost rank of the pair ( higher rank value ) + * model - the internal model describing the hierarchy + */ +mxMedianHybridCrossingReduction.prototype.calculateRankCrossing = function(i, model) +{ + var totalCrossings = 0; + var rank = model.ranks[i]; + var previousRank = model.ranks[i - 1]; + + // Create an array of connections between these two levels + var currentRankSize = rank.length; + var previousRankSize = previousRank.length; + var connections = []; + + for (var j = 0; j < currentRankSize; j++) + { + connections[j] = []; + } + + // Iterate over the top rank and fill in the connection information + for (var j = 0; j < rank.length; j++) + { + var node = rank[j]; + var rankPosition = node.getGeneralPurposeVariable(i); + var connectedCells = node.getPreviousLayerConnectedCells(i); + + for (var k = 0; k < connectedCells.length; k++) + { + var connectedNode = connectedCells[k]; + var otherCellRankPosition = connectedNode.getGeneralPurposeVariable(i - 1); + connections[rankPosition][otherCellRankPosition] = 201207; + } + } + + // Iterate through the connection matrix, crossing edges are + // indicated by other connected edges with a greater rank position + // on one rank and lower position on the other + for (var j = 0; j < currentRankSize; j++) + { + for (var k = 0; k < previousRankSize; k++) + { + if (connections[j][k] == 201207) + { + // Draw a grid of connections, crossings are top right + // and lower left from this crossing pair + for (var j2 = j + 1; j2 < currentRankSize; j2++) + { + for (var k2 = 0; k2 < k; k2++) + { + if (connections[j2][k2] == 201207) + { + totalCrossings++; + } + } + } + + for (var j2 = 0; j2 < j; j2++) + { + for (var k2 = k + 1; k2 < previousRankSize; k2++) + { + if (connections[j2][k2] == 201207) + { + totalCrossings++; + } + } + } + + } + } + } + + return totalCrossings / 2; +}; + +/** + * Function: transpose + * + * Takes each possible adjacent cell pair on each rank and checks if + * swapping them around reduces the number of crossing + * + * Parameters: + * + * mainLoopIteration - the iteration number of the main loop + * model - the internal model describing the hierarchy + */ +mxMedianHybridCrossingReduction.prototype.transpose = function(mainLoopIteration, model) +{ + var improved = true; + + // Track the number of iterations in case of looping + var count = 0; + var maxCount = 10; + while (improved && count++ < maxCount) + { + // On certain iterations allow allow swapping of cell pairs with + // equal edge crossings switched or not switched. This help to + // nudge a stuck layout into a lower crossing total. + var nudge = mainLoopIteration % 2 == 1 && count % 2 == 1; + improved = false; + + for (var i = 0; i < model.ranks.length; i++) + { + var rank = model.ranks[i]; + var orderedCells = []; + + for (var j = 0; j < rank.length; j++) + { + var cell = rank[j]; + var tempRank = cell.getGeneralPurposeVariable(i); + + // FIXME: Workaround to avoid negative tempRanks + if (tempRank < 0) + { + tempRank = j; + } + orderedCells[tempRank] = cell; + } + + var leftCellAboveConnections = null; + var leftCellBelowConnections = null; + var rightCellAboveConnections = null; + var rightCellBelowConnections = null; + + var leftAbovePositions = null; + var leftBelowPositions = null; + var rightAbovePositions = null; + var rightBelowPositions = null; + + var leftCell = null; + var rightCell = null; + + for (var j = 0; j < (rank.length - 1); j++) + { + // For each intra-rank adjacent pair of cells + // see if swapping them around would reduce the + // number of edges crossing they cause in total + // On every cell pair except the first on each rank, we + // can save processing using the previous values for the + // right cell on the new left cell + if (j == 0) + { + leftCell = orderedCells[j]; + leftCellAboveConnections = leftCell + .getNextLayerConnectedCells(i); + leftCellBelowConnections = leftCell + .getPreviousLayerConnectedCells(i); + leftAbovePositions = []; + leftBelowPositions = []; + + for (var k = 0; k < leftCellAboveConnections.length; k++) + { + leftAbovePositions[k] = leftCellAboveConnections[k].getGeneralPurposeVariable(i + 1); + } + + for (var k = 0; k < leftCellBelowConnections.length; k++) + { + leftBelowPositions[k] = leftCellBelowConnections[k].getGeneralPurposeVariable(i - 1); + } + } + else + { + leftCellAboveConnections = rightCellAboveConnections; + leftCellBelowConnections = rightCellBelowConnections; + leftAbovePositions = rightAbovePositions; + leftBelowPositions = rightBelowPositions; + leftCell = rightCell; + } + + rightCell = orderedCells[j + 1]; + rightCellAboveConnections = rightCell + .getNextLayerConnectedCells(i); + rightCellBelowConnections = rightCell + .getPreviousLayerConnectedCells(i); + + rightAbovePositions = []; + rightBelowPositions = []; + + for (var k = 0; k < rightCellAboveConnections.length; k++) + { + rightAbovePositions[k] = rightCellAboveConnections[k].getGeneralPurposeVariable(i + 1); + } + + for (var k = 0; k < rightCellBelowConnections.length; k++) + { + rightBelowPositions[k] = rightCellBelowConnections[k].getGeneralPurposeVariable(i - 1); + } + + var totalCurrentCrossings = 0; + var totalSwitchedCrossings = 0; + + for (var k = 0; k < leftAbovePositions.length; k++) + { + for (var ik = 0; ik < rightAbovePositions.length; ik++) + { + if (leftAbovePositions[k] > rightAbovePositions[ik]) + { + totalCurrentCrossings++; + } + + if (leftAbovePositions[k] < rightAbovePositions[ik]) + { + totalSwitchedCrossings++; + } + } + } + + for (var k = 0; k < leftBelowPositions.length; k++) + { + for (var ik = 0; ik < rightBelowPositions.length; ik++) + { + if (leftBelowPositions[k] > rightBelowPositions[ik]) + { + totalCurrentCrossings++; + } + + if (leftBelowPositions[k] < rightBelowPositions[ik]) + { + totalSwitchedCrossings++; + } + } + } + + if ((totalSwitchedCrossings < totalCurrentCrossings) || + (totalSwitchedCrossings == totalCurrentCrossings && + nudge)) + { + var temp = leftCell.getGeneralPurposeVariable(i); + leftCell.setGeneralPurposeVariable(i, rightCell + .getGeneralPurposeVariable(i)); + rightCell.setGeneralPurposeVariable(i, temp); + + // With this pair exchanged we have to switch all of + // values for the left cell to the right cell so the + // next iteration for this rank uses it as the left + // cell again + rightCellAboveConnections = leftCellAboveConnections; + rightCellBelowConnections = leftCellBelowConnections; + rightAbovePositions = leftAbovePositions; + rightBelowPositions = leftBelowPositions; + rightCell = leftCell; + + if (!nudge) + { + // Don't count nudges as improvement or we'll end + // up stuck in two combinations and not finishing + // as early as we should + improved = true; + } + } + } + } + } +}; + +/** + * Function: weightedMedian + * + * Sweeps up or down the layout attempting to minimise the median placement + * of connected cells on adjacent ranks + * + * Parameters: + * + * iteration - the iteration number of the main loop + * model - the internal model describing the hierarchy + */ +mxMedianHybridCrossingReduction.prototype.weightedMedian = function(iteration, model) +{ + // Reverse sweep direction each time through this method + var downwardSweep = (iteration % 2 == 0); + if (downwardSweep) + { + for (var j = model.maxRank - 1; j >= 0; j--) + { + this.medianRank(j, downwardSweep); + } + } + else + { + for (var j = 1; j < model.maxRank; j++) + { + this.medianRank(j, downwardSweep); + } + } +}; + +/** + * Function: medianRank + * + * Attempts to minimise the median placement of connected cells on this rank + * and one of the adjacent ranks + * + * Parameters: + * + * rankValue - the layer number of this rank + * downwardSweep - whether or not this is a downward sweep through the graph + */ +mxMedianHybridCrossingReduction.prototype.medianRank = function(rankValue, downwardSweep) +{ + var numCellsForRank = this.nestedBestRanks[rankValue].length; + var medianValues = []; + var reservedPositions = []; + + for (var i = 0; i < numCellsForRank; i++) + { + var cell = this.nestedBestRanks[rankValue][i]; + var sorterEntry = new MedianCellSorter(); + sorterEntry.cell = cell; + + // Flip whether or not equal medians are flipped on up and down + // sweeps + // TODO re-implement some kind of nudge + // medianValues[i].nudge = !downwardSweep; + var nextLevelConnectedCells; + + if (downwardSweep) + { + nextLevelConnectedCells = cell + .getNextLayerConnectedCells(rankValue); + } + else + { + nextLevelConnectedCells = cell + .getPreviousLayerConnectedCells(rankValue); + } + + var nextRankValue; + + if (downwardSweep) + { + nextRankValue = rankValue + 1; + } + else + { + nextRankValue = rankValue - 1; + } + + if (nextLevelConnectedCells != null + && nextLevelConnectedCells.length != 0) + { + sorterEntry.medianValue = this.medianValue( + nextLevelConnectedCells, nextRankValue); + medianValues.push(sorterEntry); + } + else + { + // Nodes with no adjacent vertices are flagged in the reserved array + // to indicate they should be left in their current position. + reservedPositions[cell.getGeneralPurposeVariable(rankValue)] = true; + } + } + + medianValues.sort(MedianCellSorter.prototype.compare); + + // Set the new position of each node within the rank using + // its temp variable + for (var i = 0; i < numCellsForRank; i++) + { + if (reservedPositions[i] == null) + { + var cell = medianValues.shift().cell; + cell.setGeneralPurposeVariable(rankValue, i); + } + } +}; + +/** + * Function: medianValue + * + * Calculates the median rank order positioning for the specified cell using + * the connected cells on the specified rank. Returns the median rank + * ordering value of the connected cells + * + * Parameters: + * + * connectedCells - the cells on the specified rank connected to the + * specified cell + * rankValue - the rank that the connected cell lie upon + */ +mxMedianHybridCrossingReduction.prototype.medianValue = function(connectedCells, rankValue) +{ + var medianValues = []; + var arrayCount = 0; + + for (var i = 0; i < connectedCells.length; i++) + { + var cell = connectedCells[i]; + medianValues[arrayCount++] = cell.getGeneralPurposeVariable(rankValue); + } + + // Sort() sorts lexicographically by default (i.e. 11 before 9) so force + // numerical order sort + medianValues.sort(function(a,b){return a - b;}); + + if (arrayCount % 2 == 1) + { + // For odd numbers of adjacent vertices return the median + return medianValues[Math.floor(arrayCount / 2)]; + } + else if (arrayCount == 2) + { + return ((medianValues[0] + medianValues[1]) / 2.0); + } + else + { + var medianPoint = arrayCount / 2; + var leftMedian = medianValues[medianPoint - 1] - medianValues[0]; + var rightMedian = medianValues[arrayCount - 1] + - medianValues[medianPoint]; + + return (medianValues[medianPoint - 1] * rightMedian + medianValues[medianPoint] + * leftMedian) + / (leftMedian + rightMedian); + } +}; + +/** + * Class: MedianCellSorter + * + * A utility class used to track cells whilst sorting occurs on the median + * values. Does not violate (x.compareTo(y)==0) == (x.equals(y)) + * + * Constructor: MedianCellSorter + * + * Constructs a new median cell sorter. + */ +function MedianCellSorter() +{ + // empty +}; + +/** + * Variable: medianValue + * + * The weighted value of the cell stored. + */ +MedianCellSorter.prototype.medianValue = 0; + +/** + * Variable: cell + * + * The cell whose median value is being calculated + */ +MedianCellSorter.prototype.cell = false; + +/** + * Function: compare + * + * Compares two MedianCellSorters. + */ +MedianCellSorter.prototype.compare = function(a, b) +{ + if (a != null && b != null) + { + if (b.medianValue > a.medianValue) + { + return -1; + } + else if (b.medianValue < a.medianValue) + { + return 1; + } + else + { + return 0; + } + } + else + { + return 0; + } +}; diff --git a/src/js/layout/hierarchical/stage/mxMinimumCycleRemover.js b/src/js/layout/hierarchical/stage/mxMinimumCycleRemover.js new file mode 100644 index 0000000..4f18f62 --- /dev/null +++ b/src/js/layout/hierarchical/stage/mxMinimumCycleRemover.js @@ -0,0 +1,131 @@ +/** + * $Id: mxMinimumCycleRemover.js,v 1.14 2010-01-04 11:18:26 gaudenz Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxMinimumCycleRemover + * + * An implementation of the first stage of the Sugiyama layout. Straightforward + * longest path calculation of layer assignment + * + * Constructor: mxMinimumCycleRemover + * + * Creates a cycle remover for the given internal model. + */ +function mxMinimumCycleRemover(layout) +{ + this.layout = layout; +}; + +/** + * Extends mxHierarchicalLayoutStage. + */ +mxMinimumCycleRemover.prototype = new mxHierarchicalLayoutStage(); +mxMinimumCycleRemover.prototype.constructor = mxMinimumCycleRemover; + +/** + * Variable: layout + * + * Reference to the enclosing . + */ +mxMinimumCycleRemover.prototype.layout = null; + +/** + * Function: execute + * + * Takes the graph detail and configuration information within the facade + * and creates the resulting laid out graph within that facade for further + * use. + */ +mxMinimumCycleRemover.prototype.execute = function(parent) +{ + var model = this.layout.getModel(); + var seenNodes = new Object(); + var unseenNodes = mxUtils.clone(model.vertexMapper, null, true); + + // Perform a dfs through the internal model. If a cycle is found, + // reverse it. + var rootsArray = null; + + if (model.roots != null) + { + var modelRoots = model.roots; + rootsArray = []; + + for (var i = 0; i < modelRoots.length; i++) + { + var nodeId = mxCellPath.create(modelRoots[i]); + rootsArray[i] = model.vertexMapper[nodeId]; + } + } + + model.visit(function(parent, node, connectingEdge, layer, seen) + { + // Check if the cell is in it's own ancestor list, if so + // invert the connecting edge and reverse the target/source + // relationship to that edge in the parent and the cell + if (node.isAncestor(parent)) + { + connectingEdge.invert(); + mxUtils.remove(connectingEdge, parent.connectsAsSource); + parent.connectsAsTarget.push(connectingEdge); + mxUtils.remove(connectingEdge, node.connectsAsTarget); + node.connectsAsSource.push(connectingEdge); + } + + var cellId = mxCellPath.create(node.cell); + seenNodes[cellId] = node; + delete unseenNodes[cellId]; + }, rootsArray, true, null); + + var possibleNewRoots = null; + + if (unseenNodes.lenth > 0) + { + possibleNewRoots = mxUtils.clone(unseenNodes, null, true); + } + + // If there are any nodes that should be nodes that the dfs can miss + // these need to be processed with the dfs and the roots assigned + // correctly to form a correct internal model + var seenNodesCopy = mxUtils.clone(seenNodes, null, true); + + // Pick a random cell and dfs from it + model.visit(function(parent, node, connectingEdge, layer, seen) + { + // Check if the cell is in it's own ancestor list, if so + // invert the connecting edge and reverse the target/source + // relationship to that edge in the parent and the cell + if (node.isAncestor(parent)) + { + connectingEdge.invert(); + mxUtils.remove(connectingEdge, parent.connectsAsSource); + node.connectsAsSource.push(connectingEdge); + parent.connectsAsTarget.push(connectingEdge); + mxUtils.remove(connectingEdge, node.connectsAsTarget); + } + + var cellId = mxCellPath.create(node.cell); + seenNodes[cellId] = node; + delete unseenNodes[cellId]; + }, unseenNodes, true, seenNodesCopy); + + var graph = this.layout.getGraph(); + + if (possibleNewRoots != null && possibleNewRoots.length > 0) + { + var roots = model.roots; + + for (var i = 0; i < possibleNewRoots.length; i++) + { + var node = possibleNewRoots[i]; + var realNode = node.cell; + var numIncomingEdges = graph.getIncomingEdges(realNode).length; + + if (numIncomingEdges == 0) + { + roots.push(realNode); + } + } + } +}; diff --git a/src/js/layout/mxCircleLayout.js b/src/js/layout/mxCircleLayout.js new file mode 100644 index 0000000..e3e6ec1 --- /dev/null +++ b/src/js/layout/mxCircleLayout.js @@ -0,0 +1,203 @@ +/** + * $Id: mxCircleLayout.js,v 1.25 2012-08-22 17:26:12 gaudenz Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxCircleLayout + * + * Extends to implement a circluar layout for a given radius. + * The vertices do not need to be connected for this layout to work and all + * connections between vertices are not taken into account. + * + * Example: + * + * (code) + * var layout = new mxCircleLayout(graph); + * layout.execute(graph.getDefaultParent()); + * (end) + * + * Constructor: mxCircleLayout + * + * Constructs a new circular layout for the specified radius. + * + * Arguments: + * + * graph - that contains the cells. + * radius - Optional radius as an int. Default is 100. + */ +function mxCircleLayout(graph, radius) +{ + mxGraphLayout.call(this, graph); + this.radius = (radius != null) ? radius : 100; +}; + +/** + * Extends mxGraphLayout. + */ +mxCircleLayout.prototype = new mxGraphLayout(); +mxCircleLayout.prototype.constructor = mxCircleLayout; + +/** + * Variable: radius + * + * Integer specifying the size of the radius. Default is 100. + */ +mxCircleLayout.prototype.radius = null; + +/** + * Variable: moveCircle + * + * Boolean specifying if the circle should be moved to the top, + * left corner specified by and . Default is false. + */ +mxCircleLayout.prototype.moveCircle = false; + +/** + * Variable: x0 + * + * Integer specifying the left coordinate of the circle. + * Default is 0. + */ +mxCircleLayout.prototype.x0 = 0; + +/** + * Variable: y0 + * + * Integer specifying the top coordinate of the circle. + * Default is 0. + */ +mxCircleLayout.prototype.y0 = 0; + +/** + * Variable: resetEdges + * + * Specifies if all edge points of traversed edges should be removed. + * Default is true. + */ +mxCircleLayout.prototype.resetEdges = true; + +/** + * Variable: disableEdgeStyle + * + * Specifies if the STYLE_NOEDGESTYLE flag should be set on edges that are + * modified by the result. Default is true. + */ +mxCircleLayout.prototype.disableEdgeStyle = true; + +/** + * Function: execute + * + * Implements . + */ +mxCircleLayout.prototype.execute = function(parent) +{ + var model = this.graph.getModel(); + + // Moves the vertices to build a circle. Makes sure the + // radius is large enough for the vertices to not + // overlap + model.beginUpdate(); + try + { + // Gets all vertices inside the parent and finds + // the maximum dimension of the largest vertex + var max = 0; + var top = null; + var left = null; + var vertices = []; + var childCount = model.getChildCount(parent); + + for (var i = 0; i < childCount; i++) + { + var cell = model.getChildAt(parent, i); + + if (!this.isVertexIgnored(cell)) + { + vertices.push(cell); + var bounds = this.getVertexBounds(cell); + + if (top == null) + { + top = bounds.y; + } + else + { + top = Math.min(top, bounds.y); + } + + if (left == null) + { + left = bounds.x; + } + else + { + left = Math.min(left, bounds.x); + } + + max = Math.max(max, Math.max(bounds.width, bounds.height)); + } + else if (!this.isEdgeIgnored(cell)) + { + // Resets the points on the traversed edge + if (this.resetEdges) + { + this.graph.resetEdge(cell); + } + + if (this.disableEdgeStyle) + { + this.setEdgeStyleEnabled(cell, false); + } + } + } + + var r = this.getRadius(vertices.length, max); + + // Moves the circle to the specified origin + if (this.moveCircle) + { + left = this.x0; + top = this.y0; + } + + this.circle(vertices, r, left, top); + } + finally + { + model.endUpdate(); + } +}; + +/** + * Function: getRadius + * + * Returns the radius to be used for the given vertex count. Max is the maximum + * width or height of all vertices in the layout. + */ +mxCircleLayout.prototype.getRadius = function(count, max) +{ + return Math.max(count * max / Math.PI, this.radius); +}; + +/** + * Function: circle + * + * Executes the circular layout for the specified array + * of vertices and the given radius. This is called from + * . + */ +mxCircleLayout.prototype.circle = function(vertices, r, left, top) +{ + var vertexCount = vertices.length; + var phi = 2 * Math.PI / vertexCount; + + for (var i = 0; i < vertexCount; i++) + { + if (this.isVertexMovable(vertices[i])) + { + this.setVertexLocation(vertices[i], + left + r + r * Math.sin(i*phi), + top + r + r * Math.cos(i*phi)); + } + } +}; diff --git a/src/js/layout/mxCompactTreeLayout.js b/src/js/layout/mxCompactTreeLayout.js new file mode 100644 index 0000000..db6324c --- /dev/null +++ b/src/js/layout/mxCompactTreeLayout.js @@ -0,0 +1,995 @@ +/** + * $Id: mxCompactTreeLayout.js,v 1.57 2012-05-24 13:09:34 david Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxCompactTreeLayout + * + * Extends 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 should be ignored as a + * vertex. This returns true if the cell has no connections. + * + * Parameters: + * + * vertex - 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 . + */ +mxCompactTreeLayout.prototype.isHorizontal = function() +{ + return this.horizontal; +}; + +/** + * Function: execute + * + * Implements . + * + * If the parent has any connected edges, then it is used as the root of + * the tree. Else, will be used to find a suitable + * root node within the set of children of the given parent. + * + * Parameters: + * + * parent - whose children should be laid out. + * root - Optional 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 diff --git a/src/js/layout/mxCompositeLayout.js b/src/js/layout/mxCompositeLayout.js new file mode 100644 index 0000000..2ceb5f5 --- /dev/null +++ b/src/js/layout/mxCompositeLayout.js @@ -0,0 +1,101 @@ +/** + * $Id: mxCompositeLayout.js,v 1.11 2010-01-02 09:45:15 gaudenz Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxCompositeLayout + * + * Allows to compose multiple layouts into a single layout. The master layout + * is the layout that handles move operations if another layout than the first + * element in should be used. The layout is not executed as + * the code assumes that it is part of . + * + * Example: + * (code) + * var first = new mxFastOrganicLayout(graph); + * var second = new mxParallelEdgeLayout(graph); + * var layout = new mxCompositeLayout(graph, [first, second], first); + * layout.execute(graph.getDefaultParent()); + * (end) + * + * Constructor: mxCompositeLayout + * + * Constructs a new layout using the given layouts. The graph instance is + * required for creating the transaction that contains all layouts. + * + * Arguments: + * + * graph - Reference to the enclosing . + * layouts - Array of . + * master - Optional layout that handles moves. If no layout is given then + * the first layout of the above array is used to handle moves. + */ +function mxCompositeLayout(graph, layouts, master) +{ + mxGraphLayout.call(this, graph); + this.layouts = layouts; + this.master = master; +}; + +/** + * Extends mxGraphLayout. + */ +mxCompositeLayout.prototype = new mxGraphLayout(); +mxCompositeLayout.prototype.constructor = mxCompositeLayout; + +/** + * Variable: layouts + * + * Holds the array of that this layout contains. + */ +mxCompositeLayout.prototype.layouts = null; + +/** + * Variable: layouts + * + * Reference to the that handles moves. If this is null + * then the first layout in is used. + */ +mxCompositeLayout.prototype.master = null; + +/** + * Function: moveCell + * + * Implements by calling move on or the first + * layout in . + */ +mxCompositeLayout.prototype.moveCell = function(cell, x, y) +{ + if (this.master != null) + { + this.master.move.apply(this.master, arguments); + } + else + { + this.layouts[0].move.apply(this.layouts[0], arguments); + } +}; + +/** + * Function: execute + * + * Implements by executing all in a + * single transaction. + */ +mxCompositeLayout.prototype.execute = function(parent) +{ + var model = this.graph.getModel(); + + model.beginUpdate(); + try + { + for (var i = 0; i < this.layouts.length; i++) + { + this.layouts[i].execute.apply(this.layouts[i], arguments); + } + } + finally + { + model.endUpdate(); + } +}; diff --git a/src/js/layout/mxEdgeLabelLayout.js b/src/js/layout/mxEdgeLabelLayout.js new file mode 100644 index 0000000..2bfb3c2 --- /dev/null +++ b/src/js/layout/mxEdgeLabelLayout.js @@ -0,0 +1,165 @@ +/** + * $Id: mxEdgeLabelLayout.js,v 1.8 2010-01-04 11:18:25 gaudenz Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxEdgeLabelLayout + * + * Extends to implement an edge label layout. This layout + * makes use of cell states, which means the graph must be validated in + * a graph view (so that the label bounds are available) before this layout + * can be executed. + * + * Example: + * + * (code) + * var layout = new mxEdgeLabelLayout(graph); + * layout.execute(graph.getDefaultParent()); + * (end) + * + * Constructor: mxEdgeLabelLayout + * + * Constructs a new edge label layout. + * + * Arguments: + * + * graph - that contains the cells. + */ +function mxEdgeLabelLayout(graph, radius) +{ + mxGraphLayout.call(this, graph); +}; + +/** + * Extends mxGraphLayout. + */ +mxEdgeLabelLayout.prototype = new mxGraphLayout(); +mxEdgeLabelLayout.prototype.constructor = mxEdgeLabelLayout; + +/** + * Function: execute + * + * Implements . + */ +mxEdgeLabelLayout.prototype.execute = function(parent) +{ + var view = this.graph.view; + var model = this.graph.getModel(); + + // Gets all vertices and edges inside the parent + var edges = []; + var vertices = []; + var childCount = model.getChildCount(parent); + + for (var i = 0; i < childCount; i++) + { + var cell = model.getChildAt(parent, i); + var state = view.getState(cell); + + if (state != null) + { + if (!this.isVertexIgnored(cell)) + { + vertices.push(state); + } + else if (!this.isEdgeIgnored(cell)) + { + edges.push(state); + } + } + } + + this.placeLabels(vertices, edges); +}; + +/** + * Function: placeLabels + * + * Places the labels of the given edges. + */ +mxEdgeLabelLayout.prototype.placeLabels = function(v, e) +{ + var model = this.graph.getModel(); + + // Moves the vertices to build a circle. Makes sure the + // radius is large enough for the vertices to not + // overlap + model.beginUpdate(); + try + { + for (var i = 0; i < e.length; i++) + { + var edge = e[i]; + + if (edge != null && edge.text != null && + edge.text.boundingBox != null) + { + for (var j = 0; j < v.length; j++) + { + var vertex = v[j]; + + if (vertex != null) + { + this.avoid(edge, vertex); + } + } + } + } + } + finally + { + model.endUpdate(); + } +}; + +/** + * Function: avoid + * + * Places the labels of the given edges. + */ +mxEdgeLabelLayout.prototype.avoid = function(edge, vertex) +{ + var model = this.graph.getModel(); + var labRect = edge.text.boundingBox; + + if (mxUtils.intersects(labRect, vertex)) + { + var dy1 = -labRect.y - labRect.height + vertex.y; + var dy2 = -labRect.y + vertex.y + vertex.height; + + var dy = (Math.abs(dy1) < Math.abs(dy2)) ? dy1 : dy2; + + var dx1 = -labRect.x - labRect.width + vertex.x; + var dx2 = -labRect.x + vertex.x + vertex.width; + + var dx = (Math.abs(dx1) < Math.abs(dx2)) ? dx1 : dx2; + + if (Math.abs(dx) < Math.abs(dy)) + { + dy = 0; + } + else + { + dx = 0; + } + + var g = model.getGeometry(edge.cell); + + if (g != null) + { + g = g.clone(); + + if (g.offset != null) + { + g.offset.x += dx; + g.offset.y += dy; + } + else + { + g.offset = new mxPoint(dx, dy); + } + + model.setGeometry(edge.cell, g); + } + } +}; diff --git a/src/js/layout/mxFastOrganicLayout.js b/src/js/layout/mxFastOrganicLayout.js new file mode 100644 index 0000000..d7d6b5d --- /dev/null +++ b/src/js/layout/mxFastOrganicLayout.js @@ -0,0 +1,591 @@ +/** + * $Id: mxFastOrganicLayout.js,v 1.37 2011-04-28 13:14:55 david Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxFastOrganicLayout + * + * Extends to implement a fast organic layout algorithm. + * The vertices need to be connected for this layout to work, vertices + * with no connections are ignored. + * + * Example: + * + * (code) + * var layout = new mxFastOrganicLayout(graph); + * layout.execute(graph.getDefaultParent()); + * (end) + * + * Constructor: mxCompactTreeLayout + * + * Constructs a new fast organic layout for the specified graph. + */ +function mxFastOrganicLayout(graph) +{ + mxGraphLayout.call(this, graph); +}; + +/** + * Extends mxGraphLayout. + */ +mxFastOrganicLayout.prototype = new mxGraphLayout(); +mxFastOrganicLayout.prototype.constructor = mxFastOrganicLayout; + +/** + * Variable: useInputOrigin + * + * Specifies if the top left corner of the input cells should be the origin + * of the layout result. Default is true. + */ +mxFastOrganicLayout.prototype.useInputOrigin = true; + +/** + * Variable: resetEdges + * + * Specifies if all edge points of traversed edges should be removed. + * Default is true. + */ +mxFastOrganicLayout.prototype.resetEdges = true; + +/** + * Variable: disableEdgeStyle + * + * Specifies if the STYLE_NOEDGESTYLE flag should be set on edges that are + * modified by the result. Default is true. + */ +mxFastOrganicLayout.prototype.disableEdgeStyle = true; + +/** + * Variable: forceConstant + * + * The force constant by which the attractive forces are divided and the + * replusive forces are multiple by the square of. The value equates to the + * average radius there is of free space around each node. Default is 50. + */ +mxFastOrganicLayout.prototype.forceConstant = 50; + +/** + * Variable: forceConstantSquared + * + * Cache of ^2 for performance. + */ +mxFastOrganicLayout.prototype.forceConstantSquared = 0; + +/** + * Variable: minDistanceLimit + * + * Minimal distance limit. Default is 2. Prevents of + * dividing by zero. + */ +mxFastOrganicLayout.prototype.minDistanceLimit = 2; + +/** + * Variable: minDistanceLimit + * + * Minimal distance limit. Default is 2. Prevents of + * dividing by zero. + */ +mxFastOrganicLayout.prototype.maxDistanceLimit = 500; + +/** + * Variable: minDistanceLimitSquared + * + * Cached version of squared. + */ +mxFastOrganicLayout.prototype.minDistanceLimitSquared = 4; + +/** + * Variable: initialTemp + * + * Start value of temperature. Default is 200. + */ +mxFastOrganicLayout.prototype.initialTemp = 200; + +/** + * Variable: temperature + * + * Temperature to limit displacement at later stages of layout. + */ +mxFastOrganicLayout.prototype.temperature = 0; + +/** + * Variable: maxIterations + * + * Total number of iterations to run the layout though. + */ +mxFastOrganicLayout.prototype.maxIterations = 0; + +/** + * Variable: iteration + * + * Current iteration count. + */ +mxFastOrganicLayout.prototype.iteration = 0; + +/** + * Variable: vertexArray + * + * An array of all vertices to be laid out. + */ +mxFastOrganicLayout.prototype.vertexArray; + +/** + * Variable: dispX + * + * An array of locally stored X co-ordinate displacements for the vertices. + */ +mxFastOrganicLayout.prototype.dispX; + +/** + * Variable: dispY + * + * An array of locally stored Y co-ordinate displacements for the vertices. + */ +mxFastOrganicLayout.prototype.dispY; + +/** + * Variable: cellLocation + * + * An array of locally stored co-ordinate positions for the vertices. + */ +mxFastOrganicLayout.prototype.cellLocation; + +/** + * Variable: radius + * + * The approximate radius of each cell, nodes only. + */ +mxFastOrganicLayout.prototype.radius; + +/** + * Variable: radiusSquared + * + * The approximate radius squared of each cell, nodes only. + */ +mxFastOrganicLayout.prototype.radiusSquared; + +/** + * Variable: isMoveable + * + * Array of booleans representing the movable states of the vertices. + */ +mxFastOrganicLayout.prototype.isMoveable; + +/** + * Variable: neighbours + * + * Local copy of cell neighbours. + */ +mxFastOrganicLayout.prototype.neighbours; + +/** + * Variable: indices + * + * Hashtable from cells to local indices. + */ +mxFastOrganicLayout.prototype.indices; + +/** + * Variable: allowedToRun + * + * Boolean flag that specifies if the layout is allowed to run. If this is + * set to false, then the layout exits in the following iteration. + */ +mxFastOrganicLayout.prototype.allowedToRun = true; + +/** + * Function: isVertexIgnored + * + * Returns a boolean indicating if the given should be ignored as a + * vertex. This returns true if the cell has no connections. + * + * Parameters: + * + * vertex - whose ignored state should be returned. + */ +mxFastOrganicLayout.prototype.isVertexIgnored = function(vertex) +{ + return mxGraphLayout.prototype.isVertexIgnored.apply(this, arguments) || + this.graph.getConnections(vertex).length == 0; +}; + +/** + * Function: execute + * + * Implements . This operates on all children of the + * given parent where returns false. + */ +mxFastOrganicLayout.prototype.execute = function(parent) +{ + var model = this.graph.getModel(); + this.vertexArray = []; + var cells = this.graph.getChildVertices(parent); + + for (var i = 0; i < cells.length; i++) + { + if (!this.isVertexIgnored(cells[i])) + { + this.vertexArray.push(cells[i]); + } + } + + var initialBounds = (this.useInputOrigin) ? + this.graph.view.getBounds(this.vertexArray) : + null; + var n = this.vertexArray.length; + + this.indices = []; + this.dispX = []; + this.dispY = []; + this.cellLocation = []; + this.isMoveable = []; + this.neighbours = []; + this.radius = []; + this.radiusSquared = []; + + if (this.forceConstant < 0.001) + { + this.forceConstant = 0.001; + } + + this.forceConstantSquared = this.forceConstant * this.forceConstant; + + // Create a map of vertices first. This is required for the array of + // arrays called neighbours which holds, for each vertex, a list of + // ints which represents the neighbours cells to that vertex as + // the indices into vertexArray + for (var i = 0; i < this.vertexArray.length; i++) + { + var vertex = this.vertexArray[i]; + this.cellLocation[i] = []; + + // Set up the mapping from array indices to cells + var id = mxCellPath.create(vertex); + this.indices[id] = i; + var bounds = this.getVertexBounds(vertex); + + // Set the X,Y value of the internal version of the cell to + // the center point of the vertex for better positioning + var width = bounds.width; + var height = bounds.height; + + // Randomize (0, 0) locations + var x = bounds.x; + var y = bounds.y; + + this.cellLocation[i][0] = x + width / 2.0; + this.cellLocation[i][1] = y + height / 2.0; + this.radius[i] = Math.min(width, height); + this.radiusSquared[i] = this.radius[i] * this.radius[i]; + } + + // Moves cell location back to top-left from center locations used in + // algorithm, resetting the edge points is part of the transaction + model.beginUpdate(); + try + { + for (var i = 0; i < n; i++) + { + this.dispX[i] = 0; + this.dispY[i] = 0; + this.isMoveable[i] = this.isVertexMovable(this.vertexArray[i]); + + // Get lists of neighbours to all vertices, translate the cells + // obtained in indices into vertexArray and store as an array + // against the orginial cell index + var edges = this.graph.getConnections(this.vertexArray[i], parent); + var cells = this.graph.getOpposites(edges, this.vertexArray[i]); + this.neighbours[i] = []; + + for (var j = 0; j < cells.length; j++) + { + // Resets the points on the traversed edge + if (this.resetEdges) + { + this.graph.resetEdge(edges[j]); + } + + if (this.disableEdgeStyle) + { + this.setEdgeStyleEnabled(edges[j], false); + } + + // Looks the cell up in the indices dictionary + var id = mxCellPath.create(cells[j]); + var index = this.indices[id]; + + // Check the connected cell in part of the vertex list to be + // acted on by this layout + if (index != null) + { + this.neighbours[i][j] = index; + } + + // Else if index of the other cell doesn't correspond to + // any cell listed to be acted upon in this layout. Set + // the index to the value of this vertex (a dummy self-loop) + // so the attraction force of the edge is not calculated + else + { + this.neighbours[i][j] = i; + } + } + } + this.temperature = this.initialTemp; + + // If max number of iterations has not been set, guess it + if (this.maxIterations == 0) + { + this.maxIterations = 20 * Math.sqrt(n); + } + + // Main iteration loop + for (this.iteration = 0; this.iteration < this.maxIterations; this.iteration++) + { + if (!this.allowedToRun) + { + return; + } + + // Calculate repulsive forces on all vertices + this.calcRepulsion(); + + // Calculate attractive forces through edges + this.calcAttraction(); + + this.calcPositions(); + this.reduceTemperature(); + } + + var minx = null; + var miny = null; + + for (var i = 0; i < this.vertexArray.length; i++) + { + var vertex = this.vertexArray[i]; + + if (this.isVertexMovable(vertex)) + { + var bounds = this.getVertexBounds(vertex); + + if (bounds != null) + { + this.cellLocation[i][0] -= bounds.width / 2.0; + this.cellLocation[i][1] -= bounds.height / 2.0; + + var x = this.graph.snap(this.cellLocation[i][0]); + var y = this.graph.snap(this.cellLocation[i][1]); + + this.setVertexLocation(vertex, x, y); + + if (minx == null) + { + minx = x; + } + else + { + minx = Math.min(minx, x); + } + + if (miny == null) + { + miny = y; + } + else + { + miny = Math.min(miny, y); + } + } + } + } + + // Modifies the cloned geometries in-place. Not needed + // to clone the geometries again as we're in the same + // undoable change. + var dx = -(minx || 0) + 1; + var dy = -(miny || 0) + 1; + + if (initialBounds != null) + { + dx += initialBounds.x; + dy += initialBounds.y; + } + + this.graph.moveCells(this.vertexArray, dx, dy); + } + finally + { + model.endUpdate(); + } +}; + +/** + * Function: calcPositions + * + * Takes the displacements calculated for each cell and applies them to the + * local cache of cell positions. Limits the displacement to the current + * temperature. + */ +mxFastOrganicLayout.prototype.calcPositions = function() +{ + for (var index = 0; index < this.vertexArray.length; index++) + { + if (this.isMoveable[index]) + { + // Get the distance of displacement for this node for this + // iteration + var deltaLength = Math.sqrt(this.dispX[index] * this.dispX[index] + + this.dispY[index] * this.dispY[index]); + + if (deltaLength < 0.001) + { + deltaLength = 0.001; + } + + // Scale down by the current temperature if less than the + // displacement distance + var newXDisp = this.dispX[index] / deltaLength + * Math.min(deltaLength, this.temperature); + + var newYDisp = this.dispY[index] / deltaLength + * Math.min(deltaLength, this.temperature); + + // reset displacements + this.dispX[index] = 0; + this.dispY[index] = 0; + + // Update the cached cell locations + this.cellLocation[index][0] += newXDisp; + this.cellLocation[index][1] += newYDisp; + } + } +}; + +/** + * Function: calcAttraction + * + * Calculates the attractive forces between all laid out nodes linked by + * edges + */ +mxFastOrganicLayout.prototype.calcAttraction = function() +{ + // Check the neighbours of each vertex and calculate the attractive + // force of the edge connecting them + for (var i = 0; i < this.vertexArray.length; i++) + { + for (var k = 0; k < this.neighbours[i].length; k++) + { + // Get the index of the othe cell in the vertex array + var j = this.neighbours[i][k]; + + // Do not proceed self-loops + if (i != j && + this.isMoveable[i] && + this.isMoveable[j]) + { + var xDelta = this.cellLocation[i][0] - this.cellLocation[j][0]; + var yDelta = this.cellLocation[i][1] - this.cellLocation[j][1]; + + // The distance between the nodes + var deltaLengthSquared = xDelta * xDelta + yDelta + * yDelta - this.radiusSquared[i] - this.radiusSquared[j]; + + if (deltaLengthSquared < this.minDistanceLimitSquared) + { + deltaLengthSquared = this.minDistanceLimitSquared; + } + + var deltaLength = Math.sqrt(deltaLengthSquared); + var force = (deltaLengthSquared) / this.forceConstant; + + var displacementX = (xDelta / deltaLength) * force; + var displacementY = (yDelta / deltaLength) * force; + + this.dispX[i] -= displacementX; + this.dispY[i] -= displacementY; + + this.dispX[j] += displacementX; + this.dispY[j] += displacementY; + } + } + } +}; + +/** + * Function: calcRepulsion + * + * Calculates the repulsive forces between all laid out nodes + */ +mxFastOrganicLayout.prototype.calcRepulsion = function() +{ + var vertexCount = this.vertexArray.length; + + for (var i = 0; i < vertexCount; i++) + { + for (var j = i; j < vertexCount; j++) + { + // Exits if the layout is no longer allowed to run + if (!this.allowedToRun) + { + return; + } + + if (j != i && + this.isMoveable[i] && + this.isMoveable[j]) + { + var xDelta = this.cellLocation[i][0] - this.cellLocation[j][0]; + var yDelta = this.cellLocation[i][1] - this.cellLocation[j][1]; + + if (xDelta == 0) + { + xDelta = 0.01 + Math.random(); + } + + if (yDelta == 0) + { + yDelta = 0.01 + Math.random(); + } + + // Distance between nodes + var deltaLength = Math.sqrt((xDelta * xDelta) + + (yDelta * yDelta)); + var deltaLengthWithRadius = deltaLength - this.radius[i] + - this.radius[j]; + + if (deltaLengthWithRadius > this.maxDistanceLimit) + { + // Ignore vertices too far apart + continue; + } + + if (deltaLengthWithRadius < this.minDistanceLimit) + { + deltaLengthWithRadius = this.minDistanceLimit; + } + + var force = this.forceConstantSquared / deltaLengthWithRadius; + + var displacementX = (xDelta / deltaLength) * force; + var displacementY = (yDelta / deltaLength) * force; + + this.dispX[i] += displacementX; + this.dispY[i] += displacementY; + + this.dispX[j] -= displacementX; + this.dispY[j] -= displacementY; + } + } + } +}; + +/** + * Function: reduceTemperature + * + * Reduces the temperature of the layout from an initial setting in a linear + * fashion to zero. + */ +mxFastOrganicLayout.prototype.reduceTemperature = function() +{ + this.temperature = this.initialTemp * (1.0 - this.iteration / this.maxIterations); +}; diff --git a/src/js/layout/mxGraphLayout.js b/src/js/layout/mxGraphLayout.js new file mode 100644 index 0000000..c9f5f32 --- /dev/null +++ b/src/js/layout/mxGraphLayout.js @@ -0,0 +1,503 @@ +/** + * $Id: mxGraphLayout.js,v 1.48 2012-08-21 17:22:21 gaudenz Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxGraphLayout + * + * Base class for all layout algorithms in mxGraph. Main public functions are + * for handling a moved cell within a layouted parent, and for + * running the layout on a given parent cell. + * + * Known Subclasses: + * + * , , , + * , , , + * + * + * Constructor: mxGraphLayout + * + * Constructs a new layout using the given layouts. + * + * Arguments: + * + * graph - Enclosing + */ +function mxGraphLayout(graph) +{ + this.graph = graph; +}; + +/** + * Variable: graph + * + * Reference to the enclosing . + */ +mxGraphLayout.prototype.graph = null; + +/** + * Variable: useBoundingBox + * + * Boolean indicating if the bounding box of the label should be used if + * its available. Default is true. + */ +mxGraphLayout.prototype.useBoundingBox = true; + +/** + * Variable: parent + * + * The parent cell of the layout, if any + */ +mxGraphLayout.prototype.parent = null; + +/** + * Function: moveCell + * + * Notified when a cell is being moved in a parent that has automatic + * layout to update the cell state (eg. index) so that the outcome of the + * layout will position the vertex as close to the point (x, y) as + * possible. + * + * Empty implementation. + * + * Parameters: + * + * cell - which has been moved. + * x - X-coordinate of the new cell location. + * y - Y-coordinate of the new cell location. + */ +mxGraphLayout.prototype.moveCell = function(cell, x, y) { }; + +/** + * Function: execute + * + * Executes the layout algorithm for the children of the given parent. + * + * Parameters: + * + * parent - whose children should be layed out. + */ +mxGraphLayout.prototype.execute = function(parent) { }; + +/** + * Function: getGraph + * + * Returns the graph that this layout operates on. + */ +mxGraphLayout.prototype.getGraph = function() +{ + return this.graph; +}; + +/** + * Function: getConstraint + * + * Returns the constraint for the given key and cell. The optional edge and + * source arguments are used to return inbound and outgoing routing- + * constraints for the given edge and vertex. This implementation always + * returns the value for the given key in the style of the given cell. + * + * Parameters: + * + * key - Key of the constraint to be returned. + * cell - whose constraint should be returned. + * edge - Optional that represents the connection whose constraint + * should be returned. Default is null. + * source - Optional boolean that specifies if the connection is incoming + * or outgoing. Default is null. + */ +mxGraphLayout.prototype.getConstraint = function(key, cell, edge, source) +{ + var state = this.graph.view.getState(cell); + var style = (state != null) ? state.style : this.graph.getCellStyle(cell); + + return (style != null) ? style[key] : null; +}; + +/** + * Function: traverse + * + * Traverses the (directed) graph invoking the given function for each + * visited vertex and edge. The function is invoked with the current vertex + * and the incoming edge as a parameter. This implementation makes sure + * each vertex is only visited once. The function may return false if the + * traversal should stop at the given vertex. + * + * Example: + * + * (code) + * mxLog.show(); + * var cell = graph.getSelectionCell(); + * graph.traverse(cell, false, function(vertex, edge) + * { + * mxLog.debug(graph.getLabel(vertex)); + * }); + * (end) + * + * Parameters: + * + * vertex - that represents the vertex where the traversal starts. + * directed - Optional boolean indicating if edges should only be traversed + * from source to target. Default is true. + * func - Visitor function that takes the current vertex and the incoming + * edge as arguments. The traversal stops if the function returns false. + * edge - Optional that represents the incoming edge. This is + * null for the first step of the traversal. + * visited - Optional array of cell paths for the visited cells. + */ +mxGraphLayout.traverse = function(vertex, directed, func, edge, visited) +{ + if (func != null && vertex != null) + { + directed = (directed != null) ? directed : true; + visited = visited || []; + var id = mxCellPath.create(vertex); + + if (visited[id] == null) + { + visited[id] = vertex; + var result = func(vertex, edge); + + if (result == null || result) + { + var edgeCount = this.graph.model.getEdgeCount(vertex); + + if (edgeCount > 0) + { + for (var i = 0; i < edgeCount; i++) + { + var e = this.graph.model.getEdgeAt(vertex, i); + var isSource = this.graph.model.getTerminal(e, true) == vertex; + + if (!directed || isSource) + { + var next = this.graph.view.getVisibleTerminal(e, !isSource); + this.traverse(next, directed, func, e, visited); + } + } + } + } + } + } +}; + +/** + * Function: isVertexMovable + * + * Returns a boolean indicating if the given is movable or + * bendable by the algorithm. This implementation returns true if the given + * cell is movable in the graph. + * + * Parameters: + * + * cell - whose movable state should be returned. + */ +mxGraphLayout.prototype.isVertexMovable = function(cell) +{ + return this.graph.isCellMovable(cell); +}; + +/** + * Function: isVertexIgnored + * + * Returns a boolean indicating if the given should be ignored by + * the algorithm. This implementation returns false for all vertices. + * + * Parameters: + * + * vertex - whose ignored state should be returned. + */ +mxGraphLayout.prototype.isVertexIgnored = function(vertex) +{ + return !this.graph.getModel().isVertex(vertex) || + !this.graph.isCellVisible(vertex); +}; + +/** + * Function: isEdgeIgnored + * + * Returns a boolean indicating if the given should be ignored by + * the algorithm. This implementation returns false for all vertices. + * + * Parameters: + * + * cell - whose ignored state should be returned. + */ +mxGraphLayout.prototype.isEdgeIgnored = function(edge) +{ + var model = this.graph.getModel(); + + return !model.isEdge(edge) || + !this.graph.isCellVisible(edge) || + model.getTerminal(edge, true) == null || + model.getTerminal(edge, false) == null; +}; + +/** + * Function: setEdgeStyleEnabled + * + * Disables or enables the edge style of the given edge. + */ +mxGraphLayout.prototype.setEdgeStyleEnabled = function(edge, value) +{ + this.graph.setCellStyles(mxConstants.STYLE_NOEDGESTYLE, + (value) ? '0' : '1', [edge]); +}; + +/** + * Function: setOrthogonalEdge + * + * Disables or enables orthogonal end segments of the given edge. + */ +mxGraphLayout.prototype.setOrthogonalEdge = function(edge, value) +{ + this.graph.setCellStyles(mxConstants.STYLE_ORTHOGONAL, + (value) ? '1' : '0', [edge]); +}; + +/** + * Function: getParentOffset + * + * Determines the offset of the given parent to the parent + * of the layout + */ +mxGraphLayout.prototype.getParentOffset = function(parent) +{ + var result = new mxPoint(); + + if (parent != null && parent != this.parent) + { + var model = this.graph.getModel(); + + if (model.isAncestor(this.parent, parent)) + { + var parentGeo = model.getGeometry(parent); + + while (parent != this.parent) + { + result.x = result.x + parentGeo.x; + result.y = result.y + parentGeo.y; + + parent = model.getParent(parent);; + parentGeo = model.getGeometry(parent); + } + } + } + + return result; +}; + +/** + * Function: setEdgePoints + * + * Replaces the array of mxPoints in the geometry of the given edge + * with the given array of mxPoints. + */ +mxGraphLayout.prototype.setEdgePoints = function(edge, points) +{ + if (edge != null) + { + var model = this.graph.model; + var geometry = model.getGeometry(edge); + + if (geometry == null) + { + geometry = new mxGeometry(); + geometry.setRelative(true); + } + else + { + geometry = geometry.clone(); + } + + if (this.parent != null && points != null) + { + var parent = model.getParent(edge); + + var parentOffset = this.getParentOffset(parent); + + for (var i = 0; i < points.length; i++) + { + points[i].x = points[i].x - parentOffset.x; + points[i].y = points[i].y - parentOffset.y; + } + } + + geometry.points = points; + model.setGeometry(edge, geometry); + } +}; + +/** + * Function: setVertexLocation + * + * Sets the new position of the given cell taking into account the size of + * the bounding box if is true. The change is only carried + * out if the new location is not equal to the existing location, otherwise + * the geometry is not replaced with an updated instance. The new or old + * bounds are returned (including overlapping labels). + * + * Parameters: + * + * cell - whose geometry is to be set. + * x - Integer that defines the x-coordinate of the new location. + * y - Integer that defines the y-coordinate of the new location. + */ +mxGraphLayout.prototype.setVertexLocation = function(cell, x, y) +{ + var model = this.graph.getModel(); + var geometry = model.getGeometry(cell); + var result = null; + + if (geometry != null) + { + result = new mxRectangle(x, y, geometry.width, geometry.height); + + // Checks for oversize labels and shifts the result + // TODO: Use mxUtils.getStringSize for label bounds + if (this.useBoundingBox) + { + var state = this.graph.getView().getState(cell); + + if (state != null && state.text != null && state.text.boundingBox != null) + { + var scale = this.graph.getView().scale; + var box = state.text.boundingBox; + + if (state.text.boundingBox.x < state.x) + { + x += (state.x - box.x) / scale; + result.width = box.width; + } + + if (state.text.boundingBox.y < state.y) + { + y += (state.y - box.y) / scale; + result.height = box.height; + } + } + } + + if (this.parent != null) + { + var parent = model.getParent(cell); + + if (parent != null && parent != this.parent) + { + var parentOffset = this.getParentOffset(parent); + + x = x - parentOffset.x; + y = y - parentOffset.y; + } + } + + if (geometry.x != x || geometry.y != y) + { + geometry = geometry.clone(); + geometry.x = x; + geometry.y = y; + + model.setGeometry(cell, geometry); + } + } + + return result; +}; + +/** + * Function: getVertexBounds + * + * Returns an that defines the bounds of the given cell or + * the bounding box if is true. + */ +mxGraphLayout.prototype.getVertexBounds = function(cell) +{ + var geo = this.graph.getModel().getGeometry(cell); + + // Checks for oversize label bounding box and corrects + // the return value accordingly + // TODO: Use mxUtils.getStringSize for label bounds + if (this.useBoundingBox) + { + var state = this.graph.getView().getState(cell); + + if (state != null && state.text != null && state.text.boundingBox != null) + { + var scale = this.graph.getView().scale; + var tmp = state.text.boundingBox; + + var dx0 = Math.max(state.x - tmp.x, 0) / scale; + var dy0 = Math.max(state.y - tmp.y, 0) / scale; + var dx1 = Math.max((tmp.x + tmp.width) - (state.x + state.width), 0) / scale; + var dy1 = Math.max((tmp.y + tmp.height) - (state.y + state.height), 0) / scale; + + geo = new mxRectangle(geo.x - dx0, geo.y - dy0, + geo.width + dx0 + dx1, geo.height + dy0 + dy1); + } + } + + if (this.parent != null) + { + var parent = this.graph.getModel().getParent(cell); + geo = geo.clone(); + + if (parent != null && parent != this.parent) + { + var parentOffset = this.getParentOffset(parent); + geo.x = geo.x + parentOffset.x; + geo.y = geo.y + parentOffset.y; + } + } + + return new mxRectangle(geo.x, geo.y, geo.width, geo.height); +}; + +/** + * Function: arrangeGroups + * + * Updates the bounds of the given groups to include all children. Call + * this with the groups in parent to child order, top-most group first, eg. + * + * arrangeGroups(graph, mxUtils.sortCells(Arrays.asList( + * new Object[] { v1, v3 }), true).toArray(), 10); + */ +mxGraphLayout.prototype.arrangeGroups = function(groups, border) +{ + this.graph.getModel().beginUpdate(); + try + { + for (var i = groups.length - 1; i >= 0; i--) + { + var group = groups[i]; + var children = this.graph.getChildVertices(group); + var bounds = this.graph.getBoundingBoxFromGeometry(children); + var geometry = this.graph.getCellGeometry(group); + var left = 0; + var top = 0; + + // Adds the size of the title area for swimlanes + if (this.graph.isSwimlane(group)) + { + var size = this.graph.getStartSize(group); + left = size.width; + top = size.height; + } + + if (bounds != null && geometry != null) + { + geometry = geometry.clone(); + geometry.x = geometry.x + bounds.x - border - left; + geometry.y = geometry.y + bounds.y - border - top; + geometry.width = bounds.width + 2 * border + left; + geometry.height = bounds.height + 2 * border + top; + this.graph.getModel().setGeometry(group, geometry); + this.graph.moveCells(children, border + left - bounds.x, + border + top - bounds.y); + } + } + } + finally + { + this.graph.getModel().endUpdate(); + } +}; diff --git a/src/js/layout/mxParallelEdgeLayout.js b/src/js/layout/mxParallelEdgeLayout.js new file mode 100644 index 0000000..e1ad57c --- /dev/null +++ b/src/js/layout/mxParallelEdgeLayout.js @@ -0,0 +1,198 @@ +/** + * $Id: mxParallelEdgeLayout.js,v 1.24 2012-03-27 15:03:34 david Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxParallelEdgeLayout + * + * Extends for arranging parallel edges. This layout works + * on edges for all pairs of vertices where there is more than one edge + * connecting the latter. + * + * Example: + * + * (code) + * var layout = new mxParallelEdgeLayout(graph); + * layout.execute(graph.getDefaultParent()); + * (end) + * + * Constructor: mxCompactTreeLayout + * + * Constructs a new fast organic layout for the specified graph. + */ +function mxParallelEdgeLayout(graph) +{ + mxGraphLayout.call(this, graph); +}; + +/** + * Extends mxGraphLayout. + */ +mxParallelEdgeLayout.prototype = new mxGraphLayout(); +mxParallelEdgeLayout.prototype.constructor = mxParallelEdgeLayout; + +/** + * Variable: spacing + * + * Defines the spacing between the parallels. Default is 20. + */ +mxParallelEdgeLayout.prototype.spacing = 20; + +/** + * Function: execute + * + * Implements . + */ +mxParallelEdgeLayout.prototype.execute = function(parent) +{ + var lookup = this.findParallels(parent); + + this.graph.model.beginUpdate(); + try + { + for (var i in lookup) + { + var parallels = lookup[i]; + + if (parallels.length > 1) + { + this.layout(parallels); + } + } + } + finally + { + this.graph.model.endUpdate(); + } +}; + +/** + * Function: findParallels + * + * Finds the parallel edges in the given parent. + */ +mxParallelEdgeLayout.prototype.findParallels = function(parent) +{ + var model = this.graph.getModel(); + var lookup = []; + var childCount = model.getChildCount(parent); + + for (var i = 0; i < childCount; i++) + { + var child = model.getChildAt(parent, i); + + if (!this.isEdgeIgnored(child)) + { + var id = this.getEdgeId(child); + + if (id != null) + { + if (lookup[id] == null) + { + lookup[id] = []; + } + + lookup[id].push(child); + } + } + } + + return lookup; +}; + +/** + * Function: getEdgeId + * + * Returns a unique ID for the given edge. The id is independent of the + * edge direction and is built using the visible terminal of the given + * edge. + */ +mxParallelEdgeLayout.prototype.getEdgeId = function(edge) +{ + var view = this.graph.getView(); + + var state = view.getState(edge); + + var src = (state != null) ? state.getVisibleTerminal(true) : view.getVisibleTerminal(edge, true); + var trg = (state != null) ? state.getVisibleTerminal(false) : view.getVisibleTerminal(edge, false); + + if (src != null && trg != null) + { + src = mxCellPath.create(src); + trg = mxCellPath.create(trg); + + return (src > trg) ? trg+'-'+src : src+'-'+trg; + } + + return null; +}; + +/** + * Function: layout + * + * Lays out the parallel edges in the given array. + */ +mxParallelEdgeLayout.prototype.layout = function(parallels) +{ + var edge = parallels[0]; + var model = this.graph.getModel(); + + var src = model.getGeometry(model.getTerminal(edge, true)); + var trg = model.getGeometry(model.getTerminal(edge, false)); + + // Routes multiple loops + if (src == trg) + { + var x0 = src.x + src.width + this.spacing; + var y0 = src.y + src.height / 2; + + for (var i = 0; i < parallels.length; i++) + { + this.route(parallels[i], x0, y0); + x0 += this.spacing; + } + } + else if (src != null && trg != null) + { + // Routes parallel edges + var scx = src.x + src.width / 2; + var scy = src.y + src.height / 2; + + var tcx = trg.x + trg.width / 2; + var tcy = trg.y + trg.height / 2; + + var dx = tcx - scx; + var dy = tcy - scy; + + var len = Math.sqrt(dx*dx+dy*dy); + + var x0 = scx + dx / 2; + var y0 = scy + dy / 2; + + var nx = dy * this.spacing / len; + var ny = dx * this.spacing / len; + + x0 += nx * (parallels.length - 1) / 2; + y0 -= ny * (parallels.length - 1) / 2; + + for (var i = 0; i < parallels.length; i++) + { + this.route(parallels[i], x0, y0); + x0 -= nx; + y0 += ny; + } + } +}; + +/** + * Function: route + * + * Routes the given edge via the given point. + */ +mxParallelEdgeLayout.prototype.route = function(edge, x, y) +{ + if (this.graph.isCellMovable(edge)) + { + this.setEdgePoints(edge, [new mxPoint(x, y)]); + } +}; diff --git a/src/js/layout/mxPartitionLayout.js b/src/js/layout/mxPartitionLayout.js new file mode 100644 index 0000000..d3592f8 --- /dev/null +++ b/src/js/layout/mxPartitionLayout.js @@ -0,0 +1,240 @@ +/** + * $Id: mxPartitionLayout.js,v 1.25 2010-01-04 11:18:25 gaudenz Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxPartitionLayout + * + * Extends for partitioning the parent cell vertically or + * horizontally by filling the complete area with the child cells. A horizontal + * layout partitions the height of the given parent whereas a a non-horizontal + * layout partitions the width. If the parent is a layer (that is, a child of + * the root node), then the current graph size is partitioned. The children do + * not need to be connected for this layout to work. + * + * Example: + * + * (code) + * var layout = new mxPartitionLayout(graph, true, 10, 20); + * layout.execute(graph.getDefaultParent()); + * (end) + * + * Constructor: mxPartitionLayout + * + * Constructs a new stack layout layout for the specified graph, + * spacing, orientation and offset. + */ +function mxPartitionLayout(graph, horizontal, spacing, border) +{ + mxGraphLayout.call(this, graph); + this.horizontal = (horizontal != null) ? horizontal : true; + this.spacing = spacing || 0; + this.border = border || 0; +}; + +/** + * Extends mxGraphLayout. + */ +mxPartitionLayout.prototype = new mxGraphLayout(); +mxPartitionLayout.prototype.constructor = mxPartitionLayout; + +/** + * Variable: horizontal + * + * Boolean indicating the direction in which the space is partitioned. + * Default is true. + */ +mxPartitionLayout.prototype.horizontal = null; + +/** + * Variable: spacing + * + * Integer that specifies the absolute spacing in pixels between the + * children. Default is 0. + */ +mxPartitionLayout.prototype.spacing = null; + +/** + * Variable: border + * + * Integer that specifies the absolute inset in pixels for the parent that + * contains the children. Default is 0. + */ +mxPartitionLayout.prototype.border = null; + +/** + * Variable: resizeVertices + * + * Boolean that specifies if vertices should be resized. Default is true. + */ +mxPartitionLayout.prototype.resizeVertices = true; + +/** + * Function: isHorizontal + * + * Returns . + */ +mxPartitionLayout.prototype.isHorizontal = function() +{ + return this.horizontal; +}; + +/** + * Function: moveCell + * + * Implements . + */ +mxPartitionLayout.prototype.moveCell = function(cell, x, y) +{ + var model = this.graph.getModel(); + var parent = model.getParent(cell); + + if (cell != null && + parent != null) + { + var i = 0; + var last = 0; + var childCount = model.getChildCount(parent); + + // Finds index of the closest swimlane + // TODO: Take into account the orientation + for (i = 0; i < childCount; i++) + { + var child = model.getChildAt(parent, i); + var bounds = this.getVertexBounds(child); + + if (bounds != null) + { + var tmp = bounds.x + bounds.width / 2; + + if (last < x && tmp > x) + { + break; + } + + last = tmp; + } + } + + // Changes child order in parent + var idx = parent.getIndex(cell); + idx = Math.max(0, i - ((i > idx) ? 1 : 0)); + + model.add(parent, cell, idx); + } +}; + +/** + * Function: execute + * + * Implements . All children where + * returns false and returns true are modified. + */ +mxPartitionLayout.prototype.execute = function(parent) +{ + var horizontal = this.isHorizontal(); + var model = this.graph.getModel(); + var pgeo = model.getGeometry(parent); + + // Handles special case where the parent is either a layer with no + // geometry or the current root of the view in which case the size + // of the graph's container will be used. + if (this.graph.container != null && + ((pgeo == null && + model.isLayer(parent)) || + parent == this.graph.getView().currentRoot)) + { + var width = this.graph.container.offsetWidth - 1; + var height = this.graph.container.offsetHeight - 1; + pgeo = new mxRectangle(0, 0, width, height); + } + + if (pgeo != null) + { + var children = []; + var childCount = model.getChildCount(parent); + + for (var i = 0; i < childCount; i++) + { + var child = model.getChildAt(parent, i); + + if (!this.isVertexIgnored(child) && + this.isVertexMovable(child)) + { + children.push(child); + } + } + + var n = children.length; + + if (n > 0) + { + var x0 = this.border; + var y0 = this.border; + var other = (horizontal) ? pgeo.height : pgeo.width; + other -= 2 * this.border; + + var size = (this.graph.isSwimlane(parent)) ? + this.graph.getStartSize(parent) : + new mxRectangle(); + + other -= (horizontal) ? size.height : size.width; + x0 = x0 + size.width; + y0 = y0 + size.height; + + var tmp = this.border + (n - 1) * this.spacing; + var value = (horizontal) ? + ((pgeo.width - x0 - tmp) / n) : + ((pgeo.height - y0 - tmp) / n); + + // Avoids negative values, that is values where the sum of the + // spacing plus the border is larger then the available space + if (value > 0) + { + model.beginUpdate(); + try + { + for (var i = 0; i < n; i++) + { + var child = children[i]; + var geo = model.getGeometry(child); + + if (geo != null) + { + geo = geo.clone(); + geo.x = x0; + geo.y = y0; + + if (horizontal) + { + if (this.resizeVertices) + { + geo.width = value; + geo.height = other; + } + + x0 += value + this.spacing; + } + else + { + if (this.resizeVertices) + { + geo.height = value; + geo.width = other; + } + + y0 += value + this.spacing; + } + + model.setGeometry(child, geo); + } + } + } + finally + { + model.endUpdate(); + } + } + } + } +}; diff --git a/src/js/layout/mxStackLayout.js b/src/js/layout/mxStackLayout.js new file mode 100644 index 0000000..7f5cd47 --- /dev/null +++ b/src/js/layout/mxStackLayout.js @@ -0,0 +1,381 @@ +/** + * $Id: mxStackLayout.js,v 1.47 2012-12-14 08:54:34 gaudenz Exp $ + * Copyright (c) 2006-2010, JGraph Ltd + */ +/** + * Class: mxStackLayout + * + * Extends to create a horizontal or vertical stack of the + * child vertices. The children do not need to be connected for this layout + * to work. + * + * Example: + * + * (code) + * var layout = new mxStackLayout(graph, true); + * layout.execute(graph.getDefaultParent()); + * (end) + * + * Constructor: mxStackLayout + * + * Constructs a new stack layout layout for the specified graph, + * spacing, orientation and offset. + */ +function mxStackLayout(graph, horizontal, spacing, x0, y0, border) +{ + mxGraphLayout.call(this, graph); + this.horizontal = (horizontal != null) ? horizontal : true; + this.spacing = (spacing != null) ? spacing : 0; + this.x0 = (x0 != null) ? x0 : 0; + this.y0 = (y0 != null) ? y0 : 0; + this.border = (border != null) ? border : 0; +}; + +/** + * Extends mxGraphLayout. + */ +mxStackLayout.prototype = new mxGraphLayout(); +mxStackLayout.prototype.constructor = mxStackLayout; + +/** + * Variable: horizontal + * + * Specifies the orientation of the layout. Default is true. + */ +mxStackLayout.prototype.horizontal = null; + +/** + * Variable: spacing + * + * Specifies the spacing between the cells. Default is 0. + */ +mxStackLayout.prototype.spacing = null; + +/** + * Variable: x0 + * + * Specifies the horizontal origin of the layout. Default is 0. + */ +mxStackLayout.prototype.x0 = null; + +/** + * Variable: y0 + * + * Specifies the vertical origin of the layout. Default is 0. + */ +mxStackLayout.prototype.y0 = null; + +/** + * Variable: border + * + * Border to be added if fill is true. Default is 0. + */ +mxStackLayout.prototype.border = 0; + +/** + * Variable: keepFirstLocation + * + * Boolean indicating if the location of the first cell should be + * kept, that is, it will not be moved to x0 or y0. + */ +mxStackLayout.prototype.keepFirstLocation = false; + +/** + * Variable: fill + * + * Boolean indicating if dimension should be changed to fill out the parent + * cell. Default is false. + */ +mxStackLayout.prototype.fill = false; + +/** + * Variable: resizeParent + * + * If the parent should be resized to match the width/height of the + * stack. Default is false. + */ +mxStackLayout.prototype.resizeParent = false; + +/** + * Variable: resizeLast + * + * If the last element should be resized to fill out the parent. Default is + * false. If is true then this is ignored. + */ +mxStackLayout.prototype.resizeLast = false; + +/** + * Variable: wrap + * + * Value at which a new column or row should be created. Default is null. + */ +mxStackLayout.prototype.wrap = null; + +/** + * Function: isHorizontal + * + * Returns . + */ +mxStackLayout.prototype.isHorizontal = function() +{ + return this.horizontal; +}; + +/** + * Function: moveCell + * + * Implements . + */ +mxStackLayout.prototype.moveCell = function(cell, x, y) +{ + var model = this.graph.getModel(); + var parent = model.getParent(cell); + var horizontal = this.isHorizontal(); + + if (cell != null && parent != null) + { + var i = 0; + var last = 0; + var childCount = model.getChildCount(parent); + var value = (horizontal) ? x : y; + var pstate = this.graph.getView().getState(parent); + + if (pstate != null) + { + value -= (horizontal) ? pstate.x : pstate.y; + } + + for (i = 0; i < childCount; i++) + { + var child = model.getChildAt(parent, i); + + if (child != cell) + { + var bounds = model.getGeometry(child); + + if (bounds != null) + { + var tmp = (horizontal) ? + bounds.x + bounds.width / 2 : + bounds.y + bounds.height / 2; + + if (last < value && tmp > value) + { + break; + } + + last = tmp; + } + } + } + + // Changes child order in parent + var idx = parent.getIndex(cell); + idx = Math.max(0, i - ((i > idx) ? 1 : 0)); + + model.add(parent, cell, idx); + } +}; + +/** + * Function: getParentSize + * + * Returns the size for the parent container or the size of the graph + * container if the parent is a layer or the root of the model. + */ +mxStackLayout.prototype.getParentSize = function(parent) +{ + var model = this.graph.getModel(); + var pgeo = model.getGeometry(parent); + + // Handles special case where the parent is either a layer with no + // geometry or the current root of the view in which case the size + // of the graph's container will be used. + if (this.graph.container != null && ((pgeo == null && + model.isLayer(parent)) || parent == this.graph.getView().currentRoot)) + { + var width = this.graph.container.offsetWidth - 1; + var height = this.graph.container.offsetHeight - 1; + pgeo = new mxRectangle(0, 0, width, height); + } + + return pgeo; +}; + +/** + * Function: execute + * + * Implements . + * + * Only children where returns false are taken into + * account. + */ +mxStackLayout.prototype.execute = function(parent) +{ + if (parent != null) + { + var horizontal = this.isHorizontal(); + var model = this.graph.getModel(); + var pgeo = this.getParentSize(parent); + + var fillValue = 0; + + if (pgeo != null) + { + fillValue = (horizontal) ? pgeo.height : pgeo.width; + } + + fillValue -= 2 * this.spacing + 2 * this.border; + var x0 = this.x0 + this.border; + var y0 = this.y0 + this.border; + + // Handles swimlane start size + if (this.graph.isSwimlane(parent)) + { + // Uses computed style to get latest + var style = this.graph.getCellStyle(parent); + var start = mxUtils.getValue(style, mxConstants.STYLE_STARTSIZE, mxConstants.DEFAULT_STARTSIZE); + var horz = mxUtils.getValue(style, mxConstants.STYLE_HORIZONTAL, true); + + if (horizontal == horz) + { + fillValue -= start; + } + + if (horizontal) + { + y0 += start; + } + else + { + x0 += start; + } + } + + model.beginUpdate(); + try + { + var tmp = 0; + var last = null; + var childCount = model.getChildCount(parent); + + for (var i = 0; i < childCount; i++) + { + var child = model.getChildAt(parent, i); + + if (!this.isVertexIgnored(child) && this.isVertexMovable(child)) + { + var geo = model.getGeometry(child); + + if (geo != null) + { + geo = geo.clone(); + + if (this.wrap != null && last != null) + { + if ((horizontal && last.x + last.width + + geo.width + 2 * this.spacing > this.wrap) || + (!horizontal && last.y + last.height + + geo.height + 2 * this.spacing > this.wrap)) + { + last = null; + + if (horizontal) + { + y0 += tmp + this.spacing; + } + else + { + x0 += tmp + this.spacing; + } + + tmp = 0; + } + } + + tmp = Math.max(tmp, (horizontal) ? geo.height : geo.width); + + if (last != null) + { + if (horizontal) + { + geo.x = last.x + last.width + this.spacing; + } + else + { + geo.y = last.y + last.height + this.spacing; + } + } + else if (!this.keepFirstLocation) + { + if (horizontal) + { + geo.x = x0; + } + else + { + geo.y = y0; + } + } + + if (horizontal) + { + geo.y = y0; + } + else + { + geo.x = x0; + } + + if (this.fill && fillValue > 0) + { + if (horizontal) + { + geo.height = fillValue; + } + else + { + geo.width = fillValue; + } + } + + model.setGeometry(child, geo); + last = geo; + } + } + } + + if (this.resizeParent && pgeo != null && last != null && + !this.graph.isCellCollapsed(parent)) + { + pgeo = pgeo.clone(); + + if (horizontal) + { + pgeo.width = last.x + last.width + this.spacing; + } + else + { + pgeo.height = last.y + last.height + this.spacing; + } + + model.setGeometry(parent, pgeo); + } + else if (this.resizeLast && pgeo != null && last != null) + { + if (horizontal) + { + last.width = pgeo.width - last.x - this.spacing; + } + else + { + last.height = pgeo.height - last.y - this.spacing; + } + } + } + finally + { + model.endUpdate(); + } + } +}; -- cgit