diff options
Diffstat (limited to 'src/js/layout/hierarchical/model/mxGraphHierarchyModel.js')
| -rw-r--r-- | src/js/layout/hierarchical/model/mxGraphHierarchyModel.js | 685 |
1 files changed, 685 insertions, 0 deletions
diff --git a/src/js/layout/hierarchical/model/mxGraphHierarchyModel.js b/src/js/layout/hierarchical/model/mxGraphHierarchyModel.js new file mode 100644 index 0000000..ca2ba30 --- /dev/null +++ b/src/js/layout/hierarchical/model/mxGraphHierarchyModel.js @@ -0,0 +1,685 @@ +/** + * $Id: mxGraphHierarchyModel.js,v 1.33 2012-12-18 13:16:43 david Exp $ + * Copyright (c) 2006-2012, JGraph Ltd + */ +/** + * Class: mxGraphHierarchyModel + * + * Internal model of a hierarchical graph. This model stores nodes and edges + * equivalent to the real graph nodes and edges, but also stores the rank of the + * cells, the order within the ranks and the new candidate locations of cells. + * The internal model also reverses edge direction were appropriate , ignores + * self-loop and groups parallels together under one edge object. + * + * Constructor: mxGraphHierarchyModel + * + * Creates an internal ordered graph model using the vertices passed in. If + * there are any, leftward edge need to be inverted in the internal model + * + * Arguments: + * + * graph - the facade describing the graph to be operated on + * vertices - the vertices for this hierarchy + * ordered - whether or not the vertices are already ordered + * deterministic - whether or not this layout should be deterministic on each + * tightenToSource - whether or not to tighten vertices towards the sources + * scanRanksFromSinks - Whether rank assignment is from the sinks or sources. + * usage + */ +function mxGraphHierarchyModel(layout, vertices, roots, parent, tightenToSource) +{ + var graph = layout.getGraph(); + this.tightenToSource = tightenToSource; + this.roots = roots; + this.parent = parent; + + // map of cells to internal cell needed for second run through + // to setup the sink of edges correctly + this.vertexMapper = new Object(); + this.edgeMapper = new Object(); + this.maxRank = 0; + var internalVertices = []; + + if (vertices == null) + { + vertices = this.graph.getChildVertices(parent); + } + + this.maxRank = this.SOURCESCANSTARTRANK; + // map of cells to internal cell needed for second run through + // to setup the sink of edges correctly. Guess size by number + // of edges is roughly same as number of vertices. + this.createInternalCells(layout, vertices, internalVertices); + + // Go through edges set their sink values. Also check the + // ordering if and invert edges if necessary + for (var i = 0; i < vertices.length; i++) + { + var edges = internalVertices[i].connectsAsSource; + + for (var j = 0; j < edges.length; j++) + { + var internalEdge = edges[j]; + var realEdges = internalEdge.edges; + + // Only need to process the first real edge, since + // all the edges connect to the same other vertex + if (realEdges != null && realEdges.length > 0) + { + var realEdge = realEdges[0]; + var targetCell = graph.getView().getVisibleTerminal( + realEdge, false); + var targetCellId = mxCellPath.create(targetCell); + var internalTargetCell = this.vertexMapper[targetCellId]; + + if (internalVertices[i] == internalTargetCell) + { + // The real edge is reversed relative to the internal edge + targetCell = graph.getView().getVisibleTerminal( + realEdge, true); + targetCellId = mxCellPath.create(targetCell); + internalTargetCell = this.vertexMapper[targetCellId]; + } + + if (internalTargetCell != null + && internalVertices[i] != internalTargetCell) + { + internalEdge.target = internalTargetCell; + + if (internalTargetCell.connectsAsTarget.length == 0) + { + internalTargetCell.connectsAsTarget = []; + } + + if (mxUtils.indexOf(internalTargetCell.connectsAsTarget, internalEdge) < 0) + { + internalTargetCell.connectsAsTarget.push(internalEdge); + } + } + } + } + + // Use the temp variable in the internal nodes to mark this + // internal vertex as having been visited. + internalVertices[i].temp[0] = 1; + } +}; + +/** + * Variable: maxRank + * + * Stores the largest rank number allocated + */ +mxGraphHierarchyModel.prototype.maxRank = null; + +/** + * Variable: vertexMapper + * + * Map from graph vertices to internal model nodes. + */ +mxGraphHierarchyModel.prototype.vertexMapper = null; + +/** + * Variable: edgeMapper + * + * Map from graph edges to internal model edges + */ +mxGraphHierarchyModel.prototype.edgeMapper = null; + +/** + * Variable: ranks + * + * Mapping from rank number to actual rank + */ +mxGraphHierarchyModel.prototype.ranks = null; + +/** + * Variable: roots + * + * Store of roots of this hierarchy model, these are real graph cells, not + * internal cells + */ +mxGraphHierarchyModel.prototype.roots = null; + +/** + * Variable: parent + * + * The parent cell whose children are being laid out + */ +mxGraphHierarchyModel.prototype.parent = null; + +/** + * Variable: dfsCount + * + * Count of the number of times the ancestor dfs has been used. + */ +mxGraphHierarchyModel.prototype.dfsCount = 0; + +/** + * Variable: SOURCESCANSTARTRANK + * + * High value to start source layering scan rank value from. + */ +mxGraphHierarchyModel.prototype.SOURCESCANSTARTRANK = 100000000; + +/** + * Variable: tightenToSource + * + * Whether or not to tighten the assigned ranks of vertices up towards + * the source cells. + */ +mxGraphHierarchyModel.prototype.tightenToSource = false; + +/** + * Function: createInternalCells + * + * Creates all edges in the internal model + * + * Parameters: + * + * layout - Reference to the <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); + } + } +}; |