| /** |
| * Copyright (c) 2006-2015, JGraph Ltd |
| * Copyright (c) 2006-2015, Gaudenz Alder |
| */ |
| /** |
| * 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; |
| }; |
| |
| var mxHierarchicalEdgeStyle = |
| { |
| ORTHOGONAL: 1, |
| POLYLINE: 2, |
| STRAIGHT: 3, |
| CURVE: 4 |
| }; |
| |
| /** |
| * Extends mxGraphLayout. |
| */ |
| mxHierarchicalLayout.prototype = new mxGraphLayout(); |
| mxHierarchicalLayout.prototype.constructor = mxHierarchicalLayout; |
| |
| /** |
| * Variable: roots |
| * |
| * Holds the array of <mxCell> 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: maintainParentLocation |
| * |
| * Specifies if the parent location should be maintained, so that the |
| * top, left corner stays the same before and after execution of |
| * the layout. Default is false for backwards compatibility. |
| */ |
| mxHierarchicalLayout.prototype.maintainParentLocation = 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 = 100; |
| |
| /** |
| * 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: traverseAncestors |
| * |
| * Whether or not to drill into child cells and layout in reverse |
| * group order. This also cause the layout 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; |
| |
| /** |
| * Variable: edgesSet |
| * |
| * A cache of edges whose source terminal is the key |
| */ |
| mxHierarchicalLayout.prototype.edgesCache = null; |
| |
| /** |
| * Variable: edgesSet |
| * |
| * A cache of edges whose source terminal is the key |
| */ |
| mxHierarchicalLayout.prototype.edgeSourceTermCache = null; |
| |
| /** |
| * Variable: edgesSet |
| * |
| * A cache of edges whose source terminal is the key |
| */ |
| mxHierarchicalLayout.prototype.edgesTargetTermCache = null; |
| |
| /** |
| * Variable: edgeStyle |
| * |
| * The style to apply between cell layers to edge segments |
| */ |
| mxHierarchicalLayout.prototype.edgeStyle = mxHierarchicalEdgeStyle.POLYLINE; |
| |
| /** |
| * 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; |
| this.edgesCache = new mxDictionary(); |
| this.edgeSourceTermCache = new mxDictionary(); |
| this.edgesTargetTermCache = new mxDictionary(); |
| |
| if (roots != null && !(roots instanceof Array)) |
| { |
| roots = [roots]; |
| } |
| |
| // 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; |
| } |
| |
| // Maintaining parent location |
| this.parentX = null; |
| this.parentY = null; |
| |
| if (parent != this.root && model.isVertex(parent) != null && this.maintainParentLocation) |
| { |
| var geo = this.graph.getCellGeometry(parent); |
| |
| if (geo != null) |
| { |
| this.parentX = geo.x; |
| this.parentY = geo.y; |
| } |
| } |
| |
| if (roots != null) |
| { |
| var rootsCopy = []; |
| |
| for (var i = 0; i < roots.length; i++) |
| { |
| var ancestor = parent != null ? model.isAncestor(parent, roots[i]) : true; |
| |
| if (ancestor && model.isVertex(roots[i])) |
| { |
| rootsCopy.push(roots[i]); |
| } |
| } |
| |
| this.roots = rootsCopy; |
| } |
| |
| model.beginUpdate(); |
| try |
| { |
| this.run(parent); |
| |
| if (this.resizeParent && !this.graph.isCellCollapsed(parent)) |
| { |
| this.graph.updateGroupBounds([parent], this.parentBorder, this.moveParent); |
| } |
| |
| // Maintaining parent location |
| if (this.parentX != null && this.parentY != null) |
| { |
| var geo = this.graph.getCellGeometry(parent); |
| |
| if (geo != null) |
| { |
| geo = geo.clone(); |
| geo.x = this.parentX; |
| geo.y = this.parentY; |
| model.setGeometry(parent, geo); |
| } |
| } |
| } |
| 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.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 cachedEdges = this.edgesCache.get(cell); |
| |
| if (cachedEdges != null) |
| { |
| return cachedEdges; |
| } |
| |
| 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 (this.isPort(child)) |
| { |
| edges = edges.concat(model.getEdges(child, true, true)); |
| } |
| else 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 source = this.getVisibleTerminal(edges[i], true); |
| var target = this.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]); |
| } |
| } |
| |
| this.edgesCache.put(cell, result); |
| |
| return result; |
| }; |
| |
| /** |
| * Function: getVisibleTerminal |
| * |
| * Helper function to return visible terminal for edge allowing for ports |
| * |
| * Parameters: |
| * |
| * edge - <mxCell> whose edges should be returned. |
| * source - Boolean that specifies whether the source or target terminal is to be returned |
| */ |
| mxHierarchicalLayout.prototype.getVisibleTerminal = function(edge, source) |
| { |
| var terminalCache = this.edgesTargetTermCache; |
| |
| if (source) |
| { |
| terminalCache = this.edgeSourceTermCache; |
| } |
| |
| var term = terminalCache.get(edge); |
| |
| if (term != null) |
| { |
| return term; |
| } |
| |
| var state = this.graph.view.getState(edge); |
| |
| var terminal = (state != null) ? state.getVisibleTerminal(source) : this.graph.view.getVisibleTerminal(edge, source); |
| |
| if (terminal == null) |
| { |
| terminal = (state != null) ? state.getVisibleTerminal(source) : this.graph.view.getVisibleTerminal(edge, source); |
| } |
| |
| if (terminal != null) |
| { |
| if (this.isPort(terminal)) |
| { |
| terminal = this.graph.model.getParent(terminal); |
| } |
| |
| terminalCache.put(edge, terminal); |
| } |
| |
| return terminal; |
| }; |
| |
| /** |
| * 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 = Object(); |
| this.filterDescendants(parent, filledVertexSet); |
| |
| 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); |
| |
| // If the candidate root is an unconnected group cell, remove it from |
| // the layout. We may need a custom set that holds such groups and forces |
| // them to be processed for resizing and/or moving. |
| |
| |
| for (var i = 0; i < candidateRoots.length; i++) |
| { |
| var vertexSet = Object(); |
| 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 < this.roots.length; i++) |
| { |
| var vertexSet = Object(); |
| hierarchyVertices.push(vertexSet); |
| |
| this.traverse(this.roots[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, result) |
| { |
| var model = this.graph.model; |
| |
| if (model.isVertex(cell) && cell != this.parent && this.graph.isCellVisible(cell)) |
| { |
| result[mxObjectIdentity.get(cell)] = 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); |
| |
| // Ignore ports in the layout vertex list, they are dealt with |
| // in the traversal mechanisms |
| if (!this.isPort(child)) |
| { |
| this.filterDescendants(child, result); |
| } |
| } |
| } |
| }; |
| |
| /** |
| * Function: isPort |
| * |
| * Returns true if the given cell is a "port", that is, when connecting to |
| * it, its parent is the connecting vertex in terms of graph traversal |
| * |
| * Parameters: |
| * |
| * cell - <mxCell> that represents the port. |
| */ |
| mxHierarchicalLayout.prototype.isPort = function(cell) |
| { |
| if (cell.geometry.relative) |
| { |
| return true; |
| } |
| |
| return false; |
| }; |
| |
| /** |
| * Function: getEdgesBetween |
| * |
| * Returns the edges between the given source and target. This takes into |
| * account collapsed and invisible cells and ports. |
| * |
| * Parameters: |
| * |
| * source - |
| * target - |
| * directed - |
| */ |
| mxHierarchicalLayout.prototype.getEdgesBetween = function(source, target, directed) |
| { |
| directed = (directed != null) ? directed : false; |
| var edges = this.getEdges(source); |
| var result = []; |
| |
| // Checks if the edge is connected to the correct |
| // cell and returns the first match |
| for (var i = 0; i < edges.length; i++) |
| { |
| var src = this.getVisibleTerminal(edges[i], true); |
| var trg = this.getVisibleTerminal(edges[i], false); |
| |
| if ((src == source && trg == target) || (!directed && src == target && trg == source)) |
| { |
| result.push(edges[i]); |
| } |
| } |
| |
| 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) |
| { |
| 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 = mxObjectIdentity.get(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; |
| } |
| |
| if (filledVertexSet !== null) |
| { |
| delete filledVertexSet[vertexID]; |
| } |
| |
| var edges = this.getEdges(vertex); |
| var edgeIsSource = []; |
| |
| for (var i = 0; i < edges.length; i++) |
| { |
| edgeIsSource[i] = (this.getVisibleTerminal(edges[i], true) == vertex); |
| } |
| |
| for (var i = 0; i < edges.length; i++) |
| { |
| if (!directed || edgeIsSource[i]) |
| { |
| var next = this.getVisibleTerminal(edges[i], !edgeIsSource[i]); |
| |
| // Check whether there are more edges incoming from the target vertex than outgoing |
| // The hierarchical model treats bi-directional parallel edges as being sourced |
| // from the more "sourced" terminal. If the directions are equal in number, the direction |
| // is that of the natural direction from the roots of the layout. |
| // The checks below are slightly more verbose than need be for performance reasons |
| var netCount = 1; |
| |
| for (var j = 0; j < edges.length; j++) |
| { |
| if (j == i) |
| { |
| continue; |
| } |
| else |
| { |
| var isSource2 = edgeIsSource[j]; |
| var otherTerm = this.getVisibleTerminal(edges[j], !isSource2); |
| |
| if (otherTerm == next) |
| { |
| if (isSource2) |
| { |
| netCount++; |
| } |
| else |
| { |
| netCount--; |
| } |
| } |
| } |
| } |
| |
| if (netCount >= 0) |
| { |
| currentComp = this.traverse(next, directed, edges[i], 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 comp) |
| { |
| currentComp[key] = comp[key]; |
| } |
| |
| // Remove the current component from the hierarchy set |
| hierarchyVertices.splice(i, 1); |
| return currentComp; |
| } |
| } |
| } |
| } |
| } |
| |
| 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; |
| }; |