| /** |
| * Copyright (c) 2006-2015, JGraph Ltd |
| * Copyright (c) 2006-2015, Gaudenz Alder |
| */ |
| /** |
| * 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 unseenNodesArray = model.vertexMapper.getValues(); |
| var unseenNodes = new Object(); |
| |
| for (var i = 0; i < unseenNodesArray.length; i++) |
| { |
| unseenNodes[unseenNodesArray[i].id] = unseenNodesArray[i]; |
| } |
| |
| // 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++) |
| { |
| rootsArray[i] = model.vertexMapper.get(modelRoots[i]); |
| } |
| } |
| |
| 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); |
| } |
| |
| seenNodes[node.id] = node; |
| delete unseenNodes[node.id]; |
| }, rootsArray, true, null); |
| |
| // 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); |
| } |
| |
| seenNodes[node.id] = node; |
| delete unseenNodes[node.id]; |
| }, unseenNodes, true, seenNodesCopy); |
| }; |