diff options
Diffstat (limited to 'src/js/layout/hierarchical')
9 files changed, 0 insertions, 4564 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); - } - } - } -}; |