diff options
Diffstat (limited to 'src/js/layout')
18 files changed, 0 insertions, 7941 deletions
diff --git a/src/js/layout/hierarchical/model/mxGraphAbstractHierarchyCell.js b/src/js/layout/hierarchical/model/mxGraphAbstractHierarchyCell.js deleted file mode 100644 index e2fe6a6..0000000 --- a/src/js/layout/hierarchical/model/mxGraphAbstractHierarchyCell.js +++ /dev/null @@ -1,206 +0,0 @@ -/** - * $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 <mxGraph>. - * 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 deleted file mode 100644 index 8ba16dd..0000000 --- a/src/js/layout/hierarchical/model/mxGraphHierarchyEdge.js +++ /dev/null @@ -1,174 +0,0 @@ -/** - * $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 deleted file mode 100644 index ca2ba30..0000000 --- a/src/js/layout/hierarchical/model/mxGraphHierarchyModel.js +++ /dev/null @@ -1,685 +0,0 @@ -/** - * $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 <mxHierarchicalLayout> algorithm. - * vertices - Array of <mxCells> that represent the vertices whom are to - * have an internal representation created. - * internalVertices - The array of <mxGraphHierarchyNodes> 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 deleted file mode 100644 index d901d57..0000000 --- a/src/js/layout/hierarchical/model/mxGraphHierarchyNode.js +++ /dev/null @@ -1,210 +0,0 @@ -/** - * $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 deleted file mode 100644 index 6ce0e05..0000000 --- a/src/js/layout/hierarchical/mxHierarchicalLayout.js +++ /dev/null @@ -1,623 +0,0 @@ -/** - * $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 <mxGraph>. - * 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 <mxGraphLayouts> 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 <parentBorder>. - */ -mxHierarchicalLayout.prototype.resizeParent = false; - -/** - * Variable: moveParent - * - * Specifies if the parent should be moved if <resizeParent> 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 <resizeParent>. 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 <mxConstants.DIRECTION_NORTH>. - */ -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 <mxGraphHierarchyModel> formed of the layout. - */ -mxHierarchicalLayout.prototype.model = null; - -/** - * Function: getModel - * - * Returns the internal <mxGraphHierarchyModel> 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 <mxCell> 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 - <mxCell> 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 - <mxCell> 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 - <mxCell> 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 <mxCell> 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 deleted file mode 100644 index 8b73ccf..0000000 --- a/src/js/layout/hierarchical/stage/mxCoordinateAssignment.js +++ /dev/null @@ -1,1836 +0,0 @@ -/** - * $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 <mxHierarchicalLayout>. - */ -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 <mxConstants.DIRECTION_NORTH>. - */ -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 deleted file mode 100644 index 2e635fc..0000000 --- a/src/js/layout/hierarchical/stage/mxHierarchicalLayoutStage.js +++ /dev/null @@ -1,25 +0,0 @@ -/** - * $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 - * <code>run</code> 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 deleted file mode 100644 index 997890e..0000000 --- a/src/js/layout/hierarchical/stage/mxMedianHybridCrossingReduction.js +++ /dev/null @@ -1,674 +0,0 @@ -/** - * $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 <mxHierarchicalLayout>. - */ -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 deleted file mode 100644 index 4f18f62..0000000 --- a/src/js/layout/hierarchical/stage/mxMinimumCycleRemover.js +++ /dev/null @@ -1,131 +0,0 @@ -/** - * $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 <mxHierarchicalLayout>. - */ -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 deleted file mode 100644 index e3e6ec1..0000000 --- a/src/js/layout/mxCircleLayout.js +++ /dev/null @@ -1,203 +0,0 @@ -/** - * $Id: mxCircleLayout.js,v 1.25 2012-08-22 17:26:12 gaudenz Exp $ - * Copyright (c) 2006-2010, JGraph Ltd - */ -/** - * Class: mxCircleLayout - * - * Extends <mxGraphLayout> 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 - <mxGraph> 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 <x0> and <y0>. 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 <mxGraphLayout.execute>. - */ -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 - * <execute>. - */ -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 deleted file mode 100644 index db6324c..0000000 --- a/src/js/layout/mxCompactTreeLayout.js +++ /dev/null @@ -1,995 +0,0 @@ -/** - * $Id: mxCompactTreeLayout.js,v 1.57 2012-05-24 13:09:34 david Exp $ - * Copyright (c) 2006-2010, JGraph Ltd - */ -/** - * Class: mxCompactTreeLayout - * - * Extends <mxGraphLayout> to implement a compact tree (Moen) algorithm. This - * layout is suitable for graphs that have no cycles (trees). Vertices that are - * not connected to the tree will be ignored by this layout. - * - * Example: - * - * (code) - * var layout = new mxCompactTreeLayout(graph); - * layout.execute(graph.getDefaultParent()); - * (end) - * - * Constructor: mxCompactTreeLayout - * - * Constructs a new compact tree layout for the specified graph - * and orientation. - */ -function mxCompactTreeLayout(graph, horizontal, invert) -{ - mxGraphLayout.call(this, graph); - this.horizontal = (horizontal != null) ? horizontal : true; - this.invert = (invert != null) ? invert : false; -}; - -/** - * Extends mxGraphLayout. - */ -mxCompactTreeLayout.prototype = new mxGraphLayout(); -mxCompactTreeLayout.prototype.constructor = mxCompactTreeLayout; - -/** - * Variable: horizontal - * - * Specifies the orientation of the layout. Default is true. - */ -mxCompactTreeLayout.prototype.horizontal = null; - -/** - * Variable: invert - * - * Specifies if edge directions should be inverted. Default is false. - */ -mxCompactTreeLayout.prototype.invert = null; - -/** - * Variable: resizeParent - * - * If the parents should be resized to match the width/height of the - * children. Default is true. - */ -mxCompactTreeLayout.prototype.resizeParent = true; - -/** - * Variable: groupPadding - * - * Padding added to resized parents - */ -mxCompactTreeLayout.prototype.groupPadding = 10; - -/** - * Variable: parentsChanged - * - * A set of the parents that need updating based on children - * process as part of the layout - */ -mxCompactTreeLayout.prototype.parentsChanged = null; - -/** - * Variable: moveTree - * - * Specifies if the tree should be moved to the top, left corner - * if it is inside a top-level layer. Default is false. - */ -mxCompactTreeLayout.prototype.moveTree = false; - -/** - * Variable: levelDistance - * - * Holds the levelDistance. Default is 10. - */ -mxCompactTreeLayout.prototype.levelDistance = 10; - -/** - * Variable: nodeDistance - * - * Holds the nodeDistance. Default is 20. - */ -mxCompactTreeLayout.prototype.nodeDistance = 20; - -/** - * Variable: resetEdges - * - * Specifies if all edge points of traversed edges should be removed. - * Default is true. - */ -mxCompactTreeLayout.prototype.resetEdges = true; - -/** - * Variable: prefHozEdgeSep - * - * The preferred horizontal distance between edges exiting a vertex - */ -mxCompactTreeLayout.prototype.prefHozEdgeSep = 5; - -/** - * Variable: prefVertEdgeOff - * - * The preferred vertical offset between edges exiting a vertex - */ -mxCompactTreeLayout.prototype.prefVertEdgeOff = 4; - -/** - * Variable: minEdgeJetty - * - * The minimum distance for an edge jetty from a vertex - */ -mxCompactTreeLayout.prototype.minEdgeJetty = 8; - -/** - * Variable: channelBuffer - * - * The size of the vertical buffer in the center of inter-rank channels - * where edge control points should not be placed - */ -mxCompactTreeLayout.prototype.channelBuffer = 4; - -/** - * Variable: edgeRouting - * - * Whether or not to apply the internal tree edge routing - */ -mxCompactTreeLayout.prototype.edgeRouting = true; - -/** - * Function: isVertexIgnored - * - * Returns a boolean indicating if the given <mxCell> should be ignored as a - * vertex. This returns true if the cell has no connections. - * - * Parameters: - * - * vertex - <mxCell> whose ignored state should be returned. - */ -mxCompactTreeLayout.prototype.isVertexIgnored = function(vertex) -{ - return mxGraphLayout.prototype.isVertexIgnored.apply(this, arguments) || - this.graph.getConnections(vertex).length == 0; -}; - -/** - * Function: isHorizontal - * - * Returns <horizontal>. - */ -mxCompactTreeLayout.prototype.isHorizontal = function() -{ - return this.horizontal; -}; - -/** - * Function: execute - * - * Implements <mxGraphLayout.execute>. - * - * If the parent has any connected edges, then it is used as the root of - * the tree. Else, <mxGraph.findTreeRoots> will be used to find a suitable - * root node within the set of children of the given parent. - * - * Parameters: - * - * parent - <mxCell> whose children should be laid out. - * root - Optional <mxCell> that will be used as the root of the tree. - */ -mxCompactTreeLayout.prototype.execute = function(parent, root) -{ - this.parent = parent; - var model = this.graph.getModel(); - - if (root == null) - { - // Takes the parent as the root if it has outgoing edges - if (this.graph.getEdges(parent, model.getParent(parent), - this.invert, !this.invert, false).length > 0) - { - root = parent; - } - - // Tries to find a suitable root in the parent's - // children - else - { - var roots = this.graph.findTreeRoots(parent, true, this.invert); - - if (roots.length > 0) - { - for (var i = 0; i < roots.length; i++) - { - if (!this.isVertexIgnored(roots[i]) && - this.graph.getEdges(roots[i], null, - this.invert, !this.invert, false).length > 0) - { - root = roots[i]; - break; - } - } - } - } - } - - if (root != null) - { - if (this.resizeParent) - { - this.parentsChanged = new Object(); - } - else - { - this.parentsChanged = null; - } - - model.beginUpdate(); - - try - { - var node = this.dfs(root, parent); - - if (node != null) - { - this.layout(node); - var x0 = this.graph.gridSize; - var y0 = x0; - - if (!this.moveTree) - { - var g = this.getVertexBounds(root); - - if (g != null) - { - x0 = g.x; - y0 = g.y; - } - } - - var bounds = null; - - if (this.isHorizontal()) - { - bounds = this.horizontalLayout(node, x0, y0); - } - else - { - bounds = this.verticalLayout(node, null, x0, y0); - } - - if (bounds != null) - { - var dx = 0; - var dy = 0; - - if (bounds.x < 0) - { - dx = Math.abs(x0 - bounds.x); - } - - if (bounds.y < 0) - { - dy = Math.abs(y0 - bounds.y); - } - - if (dx != 0 || dy != 0) - { - this.moveNode(node, dx, dy); - } - - if (this.resizeParent) - { - this.adjustParents(); - } - - if (this.edgeRouting) - { - // Iterate through all edges setting their positions - this.localEdgeProcessing(node); - } - } - } - } - finally - { - model.endUpdate(); - } - } -}; - -/** - * Function: moveNode - * - * Moves the specified node and all of its children by the given amount. - */ -mxCompactTreeLayout.prototype.moveNode = function(node, dx, dy) -{ - node.x += dx; - node.y += dy; - this.apply(node); - - var child = node.child; - - while (child != null) - { - this.moveNode(child, dx, dy); - child = child.next; - } -}; - -/** - * Function: dfs - * - * Does a depth first search starting at the specified cell. - * Makes sure the specified parent is never left by the - * algorithm. - */ -mxCompactTreeLayout.prototype.dfs = function(cell, parent, visited) -{ - visited = (visited != null) ? visited : []; - - var id = mxCellPath.create(cell); - var node = null; - - if (cell != null && visited[id] == null && !this.isVertexIgnored(cell)) - { - visited[id] = cell; - node = this.createNode(cell); - - var model = this.graph.getModel(); - var prev = null; - var out = this.graph.getEdges(cell, parent, this.invert, !this.invert, false, true); - var view = this.graph.getView(); - - for (var i = 0; i < out.length; i++) - { - var edge = out[i]; - - if (!this.isEdgeIgnored(edge)) - { - // Resets the points on the traversed edge - if (this.resetEdges) - { - this.setEdgePoints(edge, null); - } - - if (this.edgeRouting) - { - this.setEdgeStyleEnabled(edge, false); - this.setEdgePoints(edge, null); - } - - // Checks if terminal in same swimlane - var state = view.getState(edge); - var target = (state != null) ? state.getVisibleTerminal(this.invert) : view.getVisibleTerminal(edge, this.invert); - var tmp = this.dfs(target, parent, visited); - - if (tmp != null && model.getGeometry(target) != null) - { - if (prev == null) - { - node.child = tmp; - } - else - { - prev.next = tmp; - } - - prev = tmp; - } - } - } - } - - return node; -}; - -/** - * Function: layout - * - * Starts the actual compact tree layout algorithm - * at the given node. - */ -mxCompactTreeLayout.prototype.layout = function(node) -{ - if (node != null) - { - var child = node.child; - - while (child != null) - { - this.layout(child); - child = child.next; - } - - if (node.child != null) - { - this.attachParent(node, this.join(node)); - } - else - { - this.layoutLeaf(node); - } - } -}; - -/** - * Function: horizontalLayout - */ -mxCompactTreeLayout.prototype.horizontalLayout = function(node, x0, y0, bounds) -{ - node.x += x0 + node.offsetX; - node.y += y0 + node.offsetY; - bounds = this.apply(node, bounds); - var child = node.child; - - if (child != null) - { - bounds = this.horizontalLayout(child, node.x, node.y, bounds); - var siblingOffset = node.y + child.offsetY; - var s = child.next; - - while (s != null) - { - bounds = this.horizontalLayout(s, node.x + child.offsetX, siblingOffset, bounds); - siblingOffset += s.offsetY; - s = s.next; - } - } - - return bounds; -}; - -/** - * Function: verticalLayout - */ -mxCompactTreeLayout.prototype.verticalLayout = function(node, parent, x0, y0, bounds) -{ - node.x += x0 + node.offsetY; - node.y += y0 + node.offsetX; - bounds = this.apply(node, bounds); - var child = node.child; - - if (child != null) - { - bounds = this.verticalLayout(child, node, node.x, node.y, bounds); - var siblingOffset = node.x + child.offsetY; - var s = child.next; - - while (s != null) - { - bounds = this.verticalLayout(s, node, siblingOffset, node.y + child.offsetX, bounds); - siblingOffset += s.offsetY; - s = s.next; - } - } - - return bounds; -}; - -/** - * Function: attachParent - */ -mxCompactTreeLayout.prototype.attachParent = function(node, height) -{ - var x = this.nodeDistance + this.levelDistance; - var y2 = (height - node.width) / 2 - this.nodeDistance; - var y1 = y2 + node.width + 2 * this.nodeDistance - height; - - node.child.offsetX = x + node.height; - node.child.offsetY = y1; - - node.contour.upperHead = this.createLine(node.height, 0, - this.createLine(x, y1, node.contour.upperHead)); - node.contour.lowerHead = this.createLine(node.height, 0, - this.createLine(x, y2, node.contour.lowerHead)); -}; - -/** - * Function: layoutLeaf - */ -mxCompactTreeLayout.prototype.layoutLeaf = function(node) -{ - var dist = 2 * this.nodeDistance; - - node.contour.upperTail = this.createLine( - node.height + dist, 0); - node.contour.upperHead = node.contour.upperTail; - node.contour.lowerTail = this.createLine( - 0, -node.width - dist); - node.contour.lowerHead = this.createLine( - node.height + dist, 0, node.contour.lowerTail); -}; - -/** - * Function: join - */ -mxCompactTreeLayout.prototype.join = function(node) -{ - var dist = 2 * this.nodeDistance; - - var child = node.child; - node.contour = child.contour; - var h = child.width + dist; - var sum = h; - child = child.next; - - while (child != null) - { - var d = this.merge(node.contour, child.contour); - child.offsetY = d + h; - child.offsetX = 0; - h = child.width + dist; - sum += d + h; - child = child.next; - } - - return sum; -}; - -/** - * Function: merge - */ -mxCompactTreeLayout.prototype.merge = function(p1, p2) -{ - var x = 0; - var y = 0; - var total = 0; - - var upper = p1.lowerHead; - var lower = p2.upperHead; - - while (lower != null && upper != null) - { - var d = this.offset(x, y, lower.dx, lower.dy, - upper.dx, upper.dy); - y += d; - total += d; - - if (x + lower.dx <= upper.dx) - { - x += lower.dx; - y += lower.dy; - lower = lower.next; - } - else - { - x -= upper.dx; - y -= upper.dy; - upper = upper.next; - } - } - - if (lower != null) - { - var b = this.bridge(p1.upperTail, 0, 0, lower, x, y); - p1.upperTail = (b.next != null) ? p2.upperTail : b; - p1.lowerTail = p2.lowerTail; - } - else - { - var b = this.bridge(p2.lowerTail, x, y, upper, 0, 0); - - if (b.next == null) - { - p1.lowerTail = b; - } - } - - p1.lowerHead = p2.lowerHead; - - return total; -}; - -/** - * Function: offset - */ -mxCompactTreeLayout.prototype.offset = function(p1, p2, a1, a2, b1, b2) -{ - var d = 0; - - if (b1 <= p1 || p1 + a1 <= 0) - { - return 0; - } - - var t = b1 * a2 - a1 * b2; - - if (t > 0) - { - if (p1 < 0) - { - var s = p1 * a2; - d = s / a1 - p2; - } - else if (p1 > 0) - { - var s = p1 * b2; - d = s / b1 - p2; - } - else - { - d = -p2; - } - } - else if (b1 < p1 + a1) - { - var s = (b1 - p1) * a2; - d = b2 - (p2 + s / a1); - } - else if (b1 > p1 + a1) - { - var s = (a1 + p1) * b2; - d = s / b1 - (p2 + a2); - } - else - { - d = b2 - (p2 + a2); - } - - if (d > 0) - { - return d; - } - else - { - return 0; - } -}; - -/** - * Function: bridge - */ -mxCompactTreeLayout.prototype.bridge = function(line1, x1, y1, line2, x2, y2) -{ - var dx = x2 + line2.dx - x1; - var dy = 0; - var s = 0; - - if (line2.dx == 0) - { - dy = line2.dy; - } - else - { - s = dx * line2.dy; - dy = s / line2.dx; - } - - var r = this.createLine(dx, dy, line2.next); - line1.next = this.createLine(0, y2 + line2.dy - dy - y1, r); - - return r; -}; - -/** - * Function: createNode - */ -mxCompactTreeLayout.prototype.createNode = function(cell) -{ - var node = new Object(); - node.cell = cell; - node.x = 0; - node.y = 0; - node.width = 0; - node.height = 0; - - var geo = this.getVertexBounds(cell); - - if (geo != null) - { - if (this.isHorizontal()) - { - node.width = geo.height; - node.height = geo.width; - } - else - { - node.width = geo.width; - node.height = geo.height; - } - } - - node.offsetX = 0; - node.offsetY = 0; - node.contour = new Object(); - - return node; -}; - -/** - * Function: apply - */ -mxCompactTreeLayout.prototype.apply = function(node, bounds) -{ - var model = this.graph.getModel(); - var cell = node.cell; - var g = model.getGeometry(cell); - - if (cell != null && g != null) - { - if (this.isVertexMovable(cell)) - { - g = this.setVertexLocation(cell, node.x, node.y); - - if (this.resizeParent) - { - var parent = model.getParent(cell); - var id = mxCellPath.create(parent); - - // Implements set semantic - if (this.parentsChanged[id] == null) - { - this.parentsChanged[id] = parent; - } - } - } - - if (bounds == null) - { - bounds = new mxRectangle(g.x, g.y, g.width, g.height); - } - else - { - bounds = new mxRectangle(Math.min(bounds.x, g.x), - Math.min(bounds.y, g.y), - Math.max(bounds.x + bounds.width, g.x + g.width), - Math.max(bounds.y + bounds.height, g.y + g.height)); - } - } - - return bounds; -}; - -/** - * Function: createLine - */ -mxCompactTreeLayout.prototype.createLine = function(dx, dy, next) -{ - var line = new Object(); - line.dx = dx; - line.dy = dy; - line.next = next; - - return line; -}; - -/** - * Function: adjustParents - * - * Adjust parent cells whose child geometries have changed. The default - * implementation adjusts the group to just fit around the children with - * a padding. - */ -mxCompactTreeLayout.prototype.adjustParents = function() -{ - var tmp = []; - - for (var id in this.parentsChanged) - { - tmp.push(this.parentsChanged[id]); - } - - this.arrangeGroups(mxUtils.sortCells(tmp, true), this.groupPadding); -}; - -/** - * Function: localEdgeProcessing - * - * Moves the specified node and all of its children by the given amount. - */ -mxCompactTreeLayout.prototype.localEdgeProcessing = function(node) -{ - this.processNodeOutgoing(node); - var child = node.child; - - while (child != null) - { - this.localEdgeProcessing(child); - child = child.next; - } -}; - -/** - * Function: localEdgeProcessing - * - * Separates the x position of edges as they connect to vertices - */ -mxCompactTreeLayout.prototype.processNodeOutgoing = function(node) -{ - var child = node.child; - var parentCell = node.cell; - - var childCount = 0; - var sortedCells = []; - - while (child != null) - { - childCount++; - - var sortingCriterion = child.x; - - if (this.horizontal) - { - sortingCriterion = child.y; - } - - sortedCells.push(new WeightedCellSorter(child, sortingCriterion)); - child = child.next; - } - - sortedCells.sort(WeightedCellSorter.prototype.compare); - - var availableWidth = node.width; - - var requiredWidth = (childCount + 1) * this.prefHozEdgeSep; - - // Add a buffer on the edges of the vertex if the edge count allows - if (availableWidth > requiredWidth + (2 * this.prefHozEdgeSep)) - { - availableWidth -= 2 * this.prefHozEdgeSep; - } - - var edgeSpacing = availableWidth / childCount; - - var currentXOffset = edgeSpacing / 2.0; - - if (availableWidth > requiredWidth + (2 * this.prefHozEdgeSep)) - { - currentXOffset += this.prefHozEdgeSep; - } - - var currentYOffset = this.minEdgeJetty - this.prefVertEdgeOff; - var maxYOffset = 0; - - var parentBounds = this.getVertexBounds(parentCell); - child = node.child; - - for (var j = 0; j < sortedCells.length; j++) - { - var childCell = sortedCells[j].cell.cell; - var childBounds = this.getVertexBounds(childCell); - - var edges = this.graph.getEdgesBetween(parentCell, - childCell, false); - - var newPoints = []; - var x = 0; - var y = 0; - - for (var i = 0; i < edges.length; i++) - { - if (this.horizontal) - { - // Use opposite co-ords, calculation was done for - // - x = parentBounds.x + parentBounds.width; - y = parentBounds.y + currentXOffset; - newPoints.push(new mxPoint(x, y)); - x = parentBounds.x + parentBounds.width - + currentYOffset; - newPoints.push(new mxPoint(x, y)); - y = childBounds.y + childBounds.height / 2.0; - newPoints.push(new mxPoint(x, y)); - this.setEdgePoints(edges[i], newPoints); - } - else - { - x = parentBounds.x + currentXOffset; - y = parentBounds.y + parentBounds.height; - newPoints.push(new mxPoint(x, y)); - y = parentBounds.y + parentBounds.height - + currentYOffset; - newPoints.push(new mxPoint(x, y)); - x = childBounds.x + childBounds.width / 2.0; - newPoints.push(new mxPoint(x, y)); - this.setEdgePoints(edges[i], newPoints); - } - } - - if (j < childCount / 2) - { - currentYOffset += this.prefVertEdgeOff; - } - else if (j > childCount / 2) - { - currentYOffset -= this.prefVertEdgeOff; - } - // Ignore the case if equals, this means the second of 2 - // jettys with the same y (even number of edges) - - // pos[k * 2] = currentX; - currentXOffset += edgeSpacing; - // pos[k * 2 + 1] = currentYOffset; - - maxYOffset = Math.max(maxYOffset, currentYOffset); - } -}; - -/** - * Class: WeightedCellSorter - * - * A utility class used to track cells whilst sorting occurs on the weighted - * sum of their connected edges. Does not violate (x.compareTo(y)==0) == - * (x.equals(y)) - * - * Constructor: WeightedCellSorter - * - * Constructs a new weighted cell sorted for the given cell and weight. - */ -function WeightedCellSorter(cell, weightedValue) -{ - this.cell = cell; - this.weightedValue = weightedValue; -}; - -/** - * Variable: weightedValue - * - * The weighted value of the cell stored. - */ -WeightedCellSorter.prototype.weightedValue = 0; - -/** - * Variable: nudge - * - * Whether or not to flip equal weight values. - */ -WeightedCellSorter.prototype.nudge = false; - -/** - * Variable: visited - * - * Whether or not this cell has been visited in the current assignment. - */ -WeightedCellSorter.prototype.visited = false; - -/** - * Variable: rankIndex - * - * The index this cell is in the model rank. - */ -WeightedCellSorter.prototype.rankIndex = null; - -/** - * Variable: cell - * - * The cell whose median value is being calculated. - */ -WeightedCellSorter.prototype.cell = null; - -/** - * Function: compare - * - * Compares two WeightedCellSorters. - */ -WeightedCellSorter.prototype.compare = function(a, b) -{ - if (a != null && b != null) - { - if (b.weightedValue > a.weightedValue) - { - return 1; - } - else if (b.weightedValue < a.weightedValue) - { - return -1; - } - else - { - if (b.nudge) - { - return 1; - } - else - { - return -1; - } - } - } - else - { - return 0; - } -};
\ No newline at end of file diff --git a/src/js/layout/mxCompositeLayout.js b/src/js/layout/mxCompositeLayout.js deleted file mode 100644 index 2ceb5f5..0000000 --- a/src/js/layout/mxCompositeLayout.js +++ /dev/null @@ -1,101 +0,0 @@ -/** - * $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 <layouts> should be used. The <master> layout is not executed as - * the code assumes that it is part of <layouts>. - * - * 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 <mxGraph>. - * layouts - Array of <mxGraphLayouts>. - * 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 <mxGraphLayouts> that this layout contains. - */ -mxCompositeLayout.prototype.layouts = null; - -/** - * Variable: layouts - * - * Reference to the <mxGraphLayouts> that handles moves. If this is null - * then the first layout in <layouts> is used. - */ -mxCompositeLayout.prototype.master = null; - -/** - * Function: moveCell - * - * Implements <mxGraphLayout.moveCell> by calling move on <master> or the first - * layout in <layouts>. - */ -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 <mxGraphLayout.execute> by executing all <layouts> 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 deleted file mode 100644 index 2bfb3c2..0000000 --- a/src/js/layout/mxEdgeLabelLayout.js +++ /dev/null @@ -1,165 +0,0 @@ -/** - * $Id: mxEdgeLabelLayout.js,v 1.8 2010-01-04 11:18:25 gaudenz Exp $ - * Copyright (c) 2006-2010, JGraph Ltd - */ -/** - * Class: mxEdgeLabelLayout - * - * Extends <mxGraphLayout> 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 - <mxGraph> 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 <mxGraphLayout.execute>. - */ -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 deleted file mode 100644 index d7d6b5d..0000000 --- a/src/js/layout/mxFastOrganicLayout.js +++ /dev/null @@ -1,591 +0,0 @@ -/** - * $Id: mxFastOrganicLayout.js,v 1.37 2011-04-28 13:14:55 david Exp $ - * Copyright (c) 2006-2010, JGraph Ltd - */ -/** - * Class: mxFastOrganicLayout - * - * Extends <mxGraphLayout> 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 <forceConstant>^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 <minDistanceLimit> 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 <mxCell> should be ignored as a - * vertex. This returns true if the cell has no connections. - * - * Parameters: - * - * vertex - <mxCell> whose ignored state should be returned. - */ -mxFastOrganicLayout.prototype.isVertexIgnored = function(vertex) -{ - return mxGraphLayout.prototype.isVertexIgnored.apply(this, arguments) || - this.graph.getConnections(vertex).length == 0; -}; - -/** - * Function: execute - * - * Implements <mxGraphLayout.execute>. This operates on all children of the - * given parent where <isVertexIgnored> 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 deleted file mode 100644 index c9f5f32..0000000 --- a/src/js/layout/mxGraphLayout.js +++ /dev/null @@ -1,503 +0,0 @@ -/** - * $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 - * <move> for handling a moved cell within a layouted parent, and <execute> for - * running the layout on a given parent cell. - * - * Known Subclasses: - * - * <mxCircleLayout>, <mxCompactTreeLayout>, <mxCompositeLayout>, - * <mxFastOrganicLayout>, <mxParallelEdgeLayout>, <mxPartitionLayout>, - * <mxStackLayout> - * - * 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 <mxGraph>. - */ -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 - <mxCell> 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 - <mxCell> 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 - <mxCell> whose constraint should be returned. - * edge - Optional <mxCell> 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 - <mxCell> 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 <mxCell> 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 <mxCell> is movable or - * bendable by the algorithm. This implementation returns true if the given - * cell is movable in the graph. - * - * Parameters: - * - * cell - <mxCell> 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 <mxCell> should be ignored by - * the algorithm. This implementation returns false for all vertices. - * - * Parameters: - * - * vertex - <mxCell> 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 <mxCell> should be ignored by - * the algorithm. This implementation returns false for all vertices. - * - * Parameters: - * - * cell - <mxCell> 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 <useBoundingBox> 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 - <mxCell> 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 <mxRectangle> that defines the bounds of the given cell or - * the bounding box if <useBoundingBox> 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 deleted file mode 100644 index e1ad57c..0000000 --- a/src/js/layout/mxParallelEdgeLayout.js +++ /dev/null @@ -1,198 +0,0 @@ -/** - * $Id: mxParallelEdgeLayout.js,v 1.24 2012-03-27 15:03:34 david Exp $ - * Copyright (c) 2006-2010, JGraph Ltd - */ -/** - * Class: mxParallelEdgeLayout - * - * Extends <mxGraphLayout> 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 <mxGraphLayout.execute>. - */ -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 deleted file mode 100644 index d3592f8..0000000 --- a/src/js/layout/mxPartitionLayout.js +++ /dev/null @@ -1,240 +0,0 @@ -/** - * $Id: mxPartitionLayout.js,v 1.25 2010-01-04 11:18:25 gaudenz Exp $ - * Copyright (c) 2006-2010, JGraph Ltd - */ -/** - * Class: mxPartitionLayout - * - * Extends <mxGraphLayout> 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 <horizontal>. - */ -mxPartitionLayout.prototype.isHorizontal = function() -{ - return this.horizontal; -}; - -/** - * Function: moveCell - * - * Implements <mxGraphLayout.moveCell>. - */ -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 <mxGraphLayout.execute>. All children where <isVertexIgnored> - * returns false and <isVertexMovable> 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 deleted file mode 100644 index 7f5cd47..0000000 --- a/src/js/layout/mxStackLayout.js +++ /dev/null @@ -1,381 +0,0 @@ -/** - * $Id: mxStackLayout.js,v 1.47 2012-12-14 08:54:34 gaudenz Exp $ - * Copyright (c) 2006-2010, JGraph Ltd - */ -/** - * Class: mxStackLayout - * - * Extends <mxGraphLayout> 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 <resizeParent> 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 <horizontal>. - */ -mxStackLayout.prototype.isHorizontal = function() -{ - return this.horizontal; -}; - -/** - * Function: moveCell - * - * Implements <mxGraphLayout.moveCell>. - */ -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 <mxGraphLayout.execute>. - * - * Only children where <isVertexIgnored> 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(); - } - } -}; |