basant307/AI_Governance_Project
048
1var FDLayout = require('layout-base').FDLayout;2var CoSEGraphManager = require('./CoSEGraphManager');3var CoSEGraph = require('./CoSEGraph');4var CoSENode = require('./CoSENode');5var CoSEEdge = require('./CoSEEdge');6var CoSEConstants = require('./CoSEConstants');7var FDLayoutConstants = require('layout-base').FDLayoutConstants;8var LayoutConstants = require('layout-base').LayoutConstants;9var Point = require('layout-base').Point;10var PointD = require('layout-base').PointD;11var Layout = require('layout-base').Layout;12var Integer = require('layout-base').Integer;13var IGeometry = require('layout-base').IGeometry;14var LGraph = require('layout-base').LGraph;15var Transform = require('layout-base').Transform;16 17function CoSELayout() {18 FDLayout.call(this);19 20 this.toBeTiled = {}; // Memorize if a node is to be tiled or is tiled21}22 23CoSELayout.prototype = Object.create(FDLayout.prototype);24 25for (var prop in FDLayout) {26 CoSELayout[prop] = FDLayout[prop];27}28 29CoSELayout.prototype.newGraphManager = function () {30 var gm = new CoSEGraphManager(this);31 this.graphManager = gm;32 return gm;33};34 35CoSELayout.prototype.newGraph = function (vGraph) {36 return new CoSEGraph(null, this.graphManager, vGraph);37};38 39CoSELayout.prototype.newNode = function (vNode) {40 return new CoSENode(this.graphManager, vNode);41};42 43CoSELayout.prototype.newEdge = function (vEdge) {44 return new CoSEEdge(null, null, vEdge);45};46 47CoSELayout.prototype.initParameters = function () {48 FDLayout.prototype.initParameters.call(this, arguments);49 if (!this.isSubLayout) {50 if (CoSEConstants.DEFAULT_EDGE_LENGTH < 10)51 {52 this.idealEdgeLength = 10;53 }54 else55 {56 this.idealEdgeLength = CoSEConstants.DEFAULT_EDGE_LENGTH;57 }58 59 this.useSmartIdealEdgeLengthCalculation =60 CoSEConstants.DEFAULT_USE_SMART_IDEAL_EDGE_LENGTH_CALCULATION;61 this.springConstant =62 FDLayoutConstants.DEFAULT_SPRING_STRENGTH;63 this.repulsionConstant =64 FDLayoutConstants.DEFAULT_REPULSION_STRENGTH;65 this.gravityConstant =66 FDLayoutConstants.DEFAULT_GRAVITY_STRENGTH;67 this.compoundGravityConstant =68 FDLayoutConstants.DEFAULT_COMPOUND_GRAVITY_STRENGTH;69 this.gravityRangeFactor =70 FDLayoutConstants.DEFAULT_GRAVITY_RANGE_FACTOR;71 this.compoundGravityRangeFactor =72 FDLayoutConstants.DEFAULT_COMPOUND_GRAVITY_RANGE_FACTOR;73 74 // variables for tree reduction support75 this.prunedNodesAll = [];76 this.growTreeIterations = 0;77 this.afterGrowthIterations = 0;78 this.isTreeGrowing = false;79 this.isGrowthFinished = false;80 81 // variables for cooling82 this.coolingCycle = 0;83 this.maxCoolingCycle = this.maxIterations/FDLayoutConstants.CONVERGENCE_CHECK_PERIOD;84 this.finalTemperature = FDLayoutConstants.CONVERGENCE_CHECK_PERIOD/this.maxIterations;85 this.coolingAdjuster = 1; 86 }87};88 89CoSELayout.prototype.layout = function () {90 var createBendsAsNeeded = LayoutConstants.DEFAULT_CREATE_BENDS_AS_NEEDED;91 if (createBendsAsNeeded)92 {93 this.createBendpoints();94 this.graphManager.resetAllEdges();95 }96 97 this.level = 0;98 return this.classicLayout();99};100 101CoSELayout.prototype.classicLayout = function () {102 this.nodesWithGravity = this.calculateNodesToApplyGravitationTo();103 this.graphManager.setAllNodesToApplyGravitation(this.nodesWithGravity);104 this.calcNoOfChildrenForAllNodes();105 this.graphManager.calcLowestCommonAncestors();106 this.graphManager.calcInclusionTreeDepths();107 this.graphManager.getRoot().calcEstimatedSize();108 this.calcIdealEdgeLengths();109 110 if (!this.incremental)111 {112 var forest = this.getFlatForest();113 114 // The graph associated with this layout is flat and a forest115 if (forest.length > 0)116 {117 this.positionNodesRadially(forest);118 }119 // The graph associated with this layout is not flat or a forest120 else121 {122 // Reduce the trees when incremental mode is not enabled and graph is not a forest 123 this.reduceTrees();124 // Update nodes that gravity will be applied125 this.graphManager.resetAllNodesToApplyGravitation();126 var allNodes = new Set(this.getAllNodes());127 var intersection = this.nodesWithGravity.filter(x => allNodes.has(x));128 this.graphManager.setAllNodesToApplyGravitation(intersection);129 130 this.positionNodesRandomly();131 }132 }133 else {134 if(CoSEConstants.TREE_REDUCTION_ON_INCREMENTAL){135 // Reduce the trees in incremental mode if only this constant is set to true 136 this.reduceTrees();137 // Update nodes that gravity will be applied138 this.graphManager.resetAllNodesToApplyGravitation();139 var allNodes = new Set(this.getAllNodes());140 var intersection = this.nodesWithGravity.filter(x => allNodes.has(x));141 this.graphManager.setAllNodesToApplyGravitation(intersection); 142 }143 }144 145 this.initSpringEmbedder();146 this.runSpringEmbedder();147 148 return true;149};150 151CoSELayout.prototype.tick = function() {152 this.totalIterations++;153 154 if (this.totalIterations === this.maxIterations && !this.isTreeGrowing && !this.isGrowthFinished) {155 if(this.prunedNodesAll.length > 0){156 this.isTreeGrowing = true;157 }158 else {159 return true; 160 }161 }162 163 if (this.totalIterations % FDLayoutConstants.CONVERGENCE_CHECK_PERIOD == 0 && !this.isTreeGrowing && !this.isGrowthFinished)164 {165 if (this.isConverged())166 {167 if(this.prunedNodesAll.length > 0){168 this.isTreeGrowing = true;169 }170 else {171 return true; 172 } 173 }174 175 this.coolingCycle++;176 177 if(this.layoutQuality == 0) { 178 // quality - "draft"179 this.coolingAdjuster = this.coolingCycle;180 }181 else if(this.layoutQuality == 1) { 182 // quality - "default"183 this.coolingAdjuster = this.coolingCycle / 3;184 } 185 186 // cooling schedule is based on http://www.btluke.com/simanf1.html -> cooling schedule 3187 this.coolingFactor = Math.max(this.initialCoolingFactor - Math.pow(this.coolingCycle, Math.log(100 * (this.initialCoolingFactor - this.finalTemperature)) / Math.log(this.maxCoolingCycle))/100 * this.coolingAdjuster, this.finalTemperature);188 this.animationPeriod = Math.ceil(this.initialAnimationPeriod * Math.sqrt(this.coolingFactor));189 }190 // Operations while tree is growing again 191 if(this.isTreeGrowing){192 if(this.growTreeIterations % 10 == 0){193 if(this.prunedNodesAll.length > 0) {194 this.graphManager.updateBounds();195 this.updateGrid();196 this.growTree(this.prunedNodesAll);197 // Update nodes that gravity will be applied198 this.graphManager.resetAllNodesToApplyGravitation();199 var allNodes = new Set(this.getAllNodes());200 var intersection = this.nodesWithGravity.filter(x => allNodes.has(x));201 this.graphManager.setAllNodesToApplyGravitation(intersection);202 203 this.graphManager.updateBounds();204 this.updateGrid(); 205 this.coolingFactor = FDLayoutConstants.DEFAULT_COOLING_FACTOR_INCREMENTAL; 206 }207 else {208 this.isTreeGrowing = false; 209 this.isGrowthFinished = true; 210 }211 }212 this.growTreeIterations++;213 }214 // Operations after growth is finished215 if(this.isGrowthFinished){216 if (this.isConverged())217 {218 return true; 219 }220 if(this.afterGrowthIterations % 10 == 0){221 this.graphManager.updateBounds();222 this.updateGrid(); 223 }224 this.coolingFactor = FDLayoutConstants.DEFAULT_COOLING_FACTOR_INCREMENTAL * ((100 - this.afterGrowthIterations) / 100);225 this.afterGrowthIterations++;226 }227 228 var gridUpdateAllowed = !this.isTreeGrowing && !this.isGrowthFinished;229 var forceToNodeSurroundingUpdate = (this.growTreeIterations % 10 == 1 && this.isTreeGrowing) || (this.afterGrowthIterations % 10 == 1 && this.isGrowthFinished);230 231 this.totalDisplacement = 0;232 this.graphManager.updateBounds();233 this.calcSpringForces();234 this.calcRepulsionForces(gridUpdateAllowed, forceToNodeSurroundingUpdate);235 this.calcGravitationalForces();236 this.moveNodes();237 this.animate();238 239 return false; // Layout is not ended yet return false240};241 242CoSELayout.prototype.getPositionsData = function() {243 var allNodes = this.graphManager.getAllNodes();244 var pData = {};245 for (var i = 0; i < allNodes.length; i++) {246 var rect = allNodes[i].rect;247 var id = allNodes[i].id;248 pData[id] = {249 id: id,250 x: rect.getCenterX(),251 y: rect.getCenterY(),252 w: rect.width,253 h: rect.height254 };255 }256 257 return pData;258};259 260CoSELayout.prototype.runSpringEmbedder = function () {261 this.initialAnimationPeriod = 25;262 this.animationPeriod = this.initialAnimationPeriod;263 var layoutEnded = false;264 265 // If aminate option is 'during' signal that layout is supposed to start iterating266 if ( FDLayoutConstants.ANIMATE === 'during' ) {267 this.emit('layoutstarted');268 }269 else {270 // If aminate option is 'during' tick() function will be called on index.js271 while (!layoutEnded) {272 layoutEnded = this.tick();273 }274 275 this.graphManager.updateBounds();276 }277};278 279CoSELayout.prototype.calculateNodesToApplyGravitationTo = function () {280 var nodeList = [];281 var graph;282 283 var graphs = this.graphManager.getGraphs();284 var size = graphs.length;285 var i;286 for (i = 0; i < size; i++)287 {288 graph = graphs[i];289 290 graph.updateConnected();291 292 if (!graph.isConnected)293 {294 nodeList = nodeList.concat(graph.getNodes());295 }296 }297 298 return nodeList;299};300 301CoSELayout.prototype.createBendpoints = function () {302 var edges = [];303 edges = edges.concat(this.graphManager.getAllEdges());304 var visited = new Set();305 var i;306 for (i = 0; i < edges.length; i++)307 {308 var edge = edges[i];309 310 if (!visited.has(edge))311 {312 var source = edge.getSource();313 var target = edge.getTarget();314 315 if (source == target)316 {317 edge.getBendpoints().push(new PointD());318 edge.getBendpoints().push(new PointD());319 this.createDummyNodesForBendpoints(edge);320 visited.add(edge);321 }322 else323 {324 var edgeList = [];325 326 edgeList = edgeList.concat(source.getEdgeListToNode(target));327 edgeList = edgeList.concat(target.getEdgeListToNode(source));328 329 if (!visited.has(edgeList[0]))330 {331 if (edgeList.length > 1)332 {333 var k;334 for (k = 0; k < edgeList.length; k++)335 {336 var multiEdge = edgeList[k];337 multiEdge.getBendpoints().push(new PointD());338 this.createDummyNodesForBendpoints(multiEdge);339 }340 }341 edgeList.forEach(function(edge){342 visited.add(edge);343 });344 }345 }346 }347 348 if (visited.size == edges.length)349 {350 break;351 }352 }353};354 355CoSELayout.prototype.positionNodesRadially = function (forest) {356 // We tile the trees to a grid row by row; first tree starts at (0,0)357 var currentStartingPoint = new Point(0, 0);358 var numberOfColumns = Math.ceil(Math.sqrt(forest.length));359 var height = 0;360 var currentY = 0;361 var currentX = 0;362 var point = new PointD(0, 0);363 364 for (var i = 0; i < forest.length; i++)365 {366 if (i % numberOfColumns == 0)367 {368 // Start of a new row, make the x coordinate 0, increment the369 // y coordinate with the max height of the previous row370 currentX = 0;371 currentY = height;372 373 if (i != 0)374 {375 currentY += CoSEConstants.DEFAULT_COMPONENT_SEPERATION;376 }377 378 height = 0;379 }380 381 var tree = forest[i];382 383 // Find the center of the tree384 var centerNode = Layout.findCenterOfTree(tree);385 386 // Set the staring point of the next tree387 currentStartingPoint.x = currentX;388 currentStartingPoint.y = currentY;389 390 // Do a radial layout starting with the center391 point =392 CoSELayout.radialLayout(tree, centerNode, currentStartingPoint);393 394 if (point.y > height)395 {396 height = Math.floor(point.y);397 }398 399 currentX = Math.floor(point.x + CoSEConstants.DEFAULT_COMPONENT_SEPERATION);400 }401 402 this.transform(403 new PointD(LayoutConstants.WORLD_CENTER_X - point.x / 2,404 LayoutConstants.WORLD_CENTER_Y - point.y / 2));405};406 407CoSELayout.radialLayout = function (tree, centerNode, startingPoint) {408 var radialSep = Math.max(this.maxDiagonalInTree(tree),409 CoSEConstants.DEFAULT_RADIAL_SEPARATION);410 CoSELayout.branchRadialLayout(centerNode, null, 0, 359, 0, radialSep);411 var bounds = LGraph.calculateBounds(tree);412 413 var transform = new Transform();414 transform.setDeviceOrgX(bounds.getMinX());415 transform.setDeviceOrgY(bounds.getMinY());416 transform.setWorldOrgX(startingPoint.x);417 transform.setWorldOrgY(startingPoint.y);418 419 for (var i = 0; i < tree.length; i++)420 {421 var node = tree[i];422 node.transform(transform);423 }424 425 var bottomRight =426 new PointD(bounds.getMaxX(), bounds.getMaxY());427 428 return transform.inverseTransformPoint(bottomRight);429};430 431CoSELayout.branchRadialLayout = function (node, parentOfNode, startAngle, endAngle, distance, radialSeparation) {432 // First, position this node by finding its angle.433 var halfInterval = ((endAngle - startAngle) + 1) / 2;434 435 if (halfInterval < 0)436 {437 halfInterval += 180;438 }439 440 var nodeAngle = (halfInterval + startAngle) % 360;441 var teta = (nodeAngle * IGeometry.TWO_PI) / 360;442 443 // Make polar to java cordinate conversion.444 var cos_teta = Math.cos(teta);445 var x_ = distance * Math.cos(teta);446 var y_ = distance * Math.sin(teta);447 448 node.setCenter(x_, y_);449 450 // Traverse all neighbors of this node and recursively call this451 // function.452 var neighborEdges = [];453 neighborEdges = neighborEdges.concat(node.getEdges());454 var childCount = neighborEdges.length;455 456 if (parentOfNode != null)457 {458 childCount--;459 }460 461 var branchCount = 0;462 463 var incEdgesCount = neighborEdges.length;464 var startIndex;465 466 var edges = node.getEdgesBetween(parentOfNode);467 468 // If there are multiple edges, prune them until there remains only one469 // edge.470 while (edges.length > 1)471 {472 //neighborEdges.remove(edges.remove(0));473 var temp = edges[0];474 edges.splice(0, 1);475 var index = neighborEdges.indexOf(temp);476 if (index >= 0) {477 neighborEdges.splice(index, 1);478 }479 incEdgesCount--;480 childCount--;481 }482 483 if (parentOfNode != null)484 {485 //assert edges.length == 1;486 startIndex = (neighborEdges.indexOf(edges[0]) + 1) % incEdgesCount;487 }488 else489 {490 startIndex = 0;491 }492 493 var stepAngle = Math.abs(endAngle - startAngle) / childCount;494 495 for (var i = startIndex;496 branchCount != childCount;497 i = (++i) % incEdgesCount)498 {499 var currentNeighbor =500 neighborEdges[i].getOtherEnd(node);501 502 // Don't back traverse to root node in current tree.503 if (currentNeighbor == parentOfNode)504 {505 continue;506 }507 508 var childStartAngle =509 (startAngle + branchCount * stepAngle) % 360;510 var childEndAngle = (childStartAngle + stepAngle) % 360;511 512 CoSELayout.branchRadialLayout(currentNeighbor,513 node,514 childStartAngle, childEndAngle,515 distance + radialSeparation, radialSeparation);516 517 branchCount++;518 }519};520 521CoSELayout.maxDiagonalInTree = function (tree) {522 var maxDiagonal = Integer.MIN_VALUE;523 524 for (var i = 0; i < tree.length; i++)525 {526 var node = tree[i];527 var diagonal = node.getDiagonal();528 529 if (diagonal > maxDiagonal)530 {531 maxDiagonal = diagonal;532 }533 }534 535 return maxDiagonal;536};537 538CoSELayout.prototype.calcRepulsionRange = function () {539 // formula is 2 x (level + 1) x idealEdgeLength540 return (2 * (this.level + 1) * this.idealEdgeLength);541};542 543// Tiling methods544 545// Group zero degree members whose parents are not to be tiled, create dummy parents where needed and fill memberGroups by their dummp parent id's546CoSELayout.prototype.groupZeroDegreeMembers = function () {547 var self = this;548 // array of [parent_id x oneDegreeNode_id]549 var tempMemberGroups = {}; // A temporary map of parent node and its zero degree members550 this.memberGroups = {}; // A map of dummy parent node and its zero degree members whose parents are not to be tiled551 this.idToDummyNode = {}; // A map of id to dummy node 552 553 var zeroDegree = []; // List of zero degree nodes whose parents are not to be tiled554 var allNodes = this.graphManager.getAllNodes();555 556 // Fill zero degree list557 for (var i = 0; i < allNodes.length; i++) {558 var node = allNodes[i];559 var parent = node.getParent();560 // If a node has zero degree and its parent is not to be tiled if exists add that node to zeroDegres list561 if (this.getNodeDegreeWithChildren(node) === 0 && ( parent.id == undefined || !this.getToBeTiled(parent) ) ) {562 zeroDegree.push(node);563 }564 }565 566 // Create a map of parent node and its zero degree members567 for (var i = 0; i < zeroDegree.length; i++)568 {569 var node = zeroDegree[i]; // Zero degree node itself570 var p_id = node.getParent().id; // Parent id571 572 if (typeof tempMemberGroups[p_id] === "undefined")573 tempMemberGroups[p_id] = [];574 575 tempMemberGroups[p_id] = tempMemberGroups[p_id].concat(node); // Push node to the list belongs to its parent in tempMemberGroups576 }577 578 // If there are at least two nodes at a level, create a dummy compound for them579 Object.keys(tempMemberGroups).forEach(function(p_id) {580 if (tempMemberGroups[p_id].length > 1) {581 var dummyCompoundId = "DummyCompound_" + p_id; // The id of dummy compound which will be created soon582 self.memberGroups[dummyCompoundId] = tempMemberGroups[p_id]; // Add dummy compound to memberGroups583 584 var parent = tempMemberGroups[p_id][0].getParent(); // The parent of zero degree nodes will be the parent of new dummy compound585 586 // Create a dummy compound with calculated id587 var dummyCompound = new CoSENode(self.graphManager);588 dummyCompound.id = dummyCompoundId;589 dummyCompound.paddingLeft = parent.paddingLeft || 0;590 dummyCompound.paddingRight = parent.paddingRight || 0;591 dummyCompound.paddingBottom = parent.paddingBottom || 0;592 dummyCompound.paddingTop = parent.paddingTop || 0;593 594 self.idToDummyNode[dummyCompoundId] = dummyCompound;595 596 var dummyParentGraph = self.getGraphManager().add(self.newGraph(), dummyCompound);597 var parentGraph = parent.getChild();598 599 // Add dummy compound to parent the graph600 parentGraph.add(dummyCompound);601 602 // For each zero degree node in this level remove it from its parent graph and add it to the graph of dummy parent603 for (var i = 0; i < tempMemberGroups[p_id].length; i++) {604 var node = tempMemberGroups[p_id][i];605 606 parentGraph.remove(node);607 dummyParentGraph.add(node);608 }609 }610 });611};612 613CoSELayout.prototype.clearCompounds = function () {614 var childGraphMap = {};615 var idToNode = {};616 617 // Get compound ordering by finding the inner one first618 this.performDFSOnCompounds();619 620 for (var i = 0; i < this.compoundOrder.length; i++) {621 622 idToNode[this.compoundOrder[i].id] = this.compoundOrder[i];623 childGraphMap[this.compoundOrder[i].id] = [].concat(this.compoundOrder[i].getChild().getNodes());624 625 // Remove children of compounds626 this.graphManager.remove(this.compoundOrder[i].getChild());627 this.compoundOrder[i].child = null;628 }629 630 this.graphManager.resetAllNodes();631 632 // Tile the removed children633 this.tileCompoundMembers(childGraphMap, idToNode);634};635 636CoSELayout.prototype.clearZeroDegreeMembers = function () {637 var self = this;638 var tiledZeroDegreePack = this.tiledZeroDegreePack = [];639 640 Object.keys(this.memberGroups).forEach(function(id) {641 var compoundNode = self.idToDummyNode[id]; // Get the dummy compound642 643 tiledZeroDegreePack[id] = self.tileNodes(self.memberGroups[id], compoundNode.paddingLeft + compoundNode.paddingRight);644 645 // Set the width and height of the dummy compound as calculated646 compoundNode.rect.width = tiledZeroDegreePack[id].width;647 compoundNode.rect.height = tiledZeroDegreePack[id].height;648 });649};650 651CoSELayout.prototype.repopulateCompounds = function () {652 for (var i = this.compoundOrder.length - 1; i >= 0; i--) {653 var lCompoundNode = this.compoundOrder[i];654 var id = lCompoundNode.id;655 var horizontalMargin = lCompoundNode.paddingLeft;656 var verticalMargin = lCompoundNode.paddingTop;657 658 this.adjustLocations(this.tiledMemberPack[id], lCompoundNode.rect.x, lCompoundNode.rect.y, horizontalMargin, verticalMargin);659 }660};661 662CoSELayout.prototype.repopulateZeroDegreeMembers = function () {663 var self = this;664 var tiledPack = this.tiledZeroDegreePack;665 666 Object.keys(tiledPack).forEach(function(id) {667 var compoundNode = self.idToDummyNode[id]; // Get the dummy compound by its id668 var horizontalMargin = compoundNode.paddingLeft;669 var verticalMargin = compoundNode.paddingTop;670 671 // Adjust the positions of nodes wrt its compound672 self.adjustLocations(tiledPack[id], compoundNode.rect.x, compoundNode.rect.y, horizontalMargin, verticalMargin);673 });674};675 676CoSELayout.prototype.getToBeTiled = function (node) {677 var id = node.id;678 //firstly check the previous results679 if (this.toBeTiled[id] != null) {680 return this.toBeTiled[id];681 }682 683 //only compound nodes are to be tiled684 var childGraph = node.getChild();685 if (childGraph == null) {686 this.toBeTiled[id] = false;687 return false;688 }689 690 var children = childGraph.getNodes(); // Get the children nodes691 692 //a compound node is not to be tiled if all of its compound children are not to be tiled693 for (var i = 0; i < children.length; i++) {694 var theChild = children[i];695 696 if (this.getNodeDegree(theChild) > 0) {697 this.toBeTiled[id] = false;698 return false;699 }700 701 //pass the children not having the compound structure702 if (theChild.getChild() == null) {703 this.toBeTiled[theChild.id] = false;704 continue;705 }706 707 if (!this.getToBeTiled(theChild)) {708 this.toBeTiled[id] = false;709 return false;710 }711 }712 this.toBeTiled[id] = true;713 return true;714};715 716// Get degree of a node depending of its edges and independent of its children717CoSELayout.prototype.getNodeDegree = function (node) {718 var id = node.id;719 var edges = node.getEdges();720 var degree = 0;721 722 // For the edges connected723 for (var i = 0; i < edges.length; i++) {724 var edge = edges[i];725 if (edge.getSource().id !== edge.getTarget().id) {726 degree = degree + 1;727 }728 }729 return degree;730};731 732// Get degree of a node with its children733CoSELayout.prototype.getNodeDegreeWithChildren = function (node) {734 var degree = this.getNodeDegree(node);735 if (node.getChild() == null) {736 return degree;737 }738 var children = node.getChild().getNodes();739 for (var i = 0; i < children.length; i++) {740 var child = children[i];741 degree += this.getNodeDegreeWithChildren(child);742 }743 return degree;744};745 746CoSELayout.prototype.performDFSOnCompounds = function () {747 this.compoundOrder = [];748 this.fillCompexOrderByDFS(this.graphManager.getRoot().getNodes());749};750 751CoSELayout.prototype.fillCompexOrderByDFS = function (children) {752 for (var i = 0; i < children.length; i++) {753 var child = children[i];754 if (child.getChild() != null) {755 this.fillCompexOrderByDFS(child.getChild().getNodes());756 }757 if (this.getToBeTiled(child)) {758 this.compoundOrder.push(child);759 }760 }761};762 763/**764* This method places each zero degree member wrt given (x,y) coordinates (top left).765*/766CoSELayout.prototype.adjustLocations = function (organization, x, y, compoundHorizontalMargin, compoundVerticalMargin) {767 x += compoundHorizontalMargin;768 y += compoundVerticalMargin;769 770 var left = x;771 772 for (var i = 0; i < organization.rows.length; i++) {773 var row = organization.rows[i];774 x = left;775 var maxHeight = 0;776 777 for (var j = 0; j < row.length; j++) {778 var lnode = row[j];779 780 lnode.rect.x = x;// + lnode.rect.width / 2;781 lnode.rect.y = y;// + lnode.rect.height / 2;782 783 x += lnode.rect.width + organization.horizontalPadding;784 785 if (lnode.rect.height > maxHeight)786 maxHeight = lnode.rect.height;787 }788 789 y += maxHeight + organization.verticalPadding;790 }791};792 793CoSELayout.prototype.tileCompoundMembers = function (childGraphMap, idToNode) {794 var self = this;795 this.tiledMemberPack = [];796 797 Object.keys(childGraphMap).forEach(function(id) {798 // Get the compound node799 var compoundNode = idToNode[id];800 801 self.tiledMemberPack[id] = self.tileNodes(childGraphMap[id], compoundNode.paddingLeft + compoundNode.paddingRight);802 803 compoundNode.rect.width = self.tiledMemberPack[id].width;804 compoundNode.rect.height = self.tiledMemberPack[id].height;805 });806};807 808CoSELayout.prototype.tileNodes = function (nodes, minWidth) {809 var verticalPadding = CoSEConstants.TILING_PADDING_VERTICAL;810 var horizontalPadding = CoSEConstants.TILING_PADDING_HORIZONTAL;811 var organization = {812 rows: [],813 rowWidth: [],814 rowHeight: [],815 width: 0,816 height: minWidth, // assume minHeight equals to minWidth817 verticalPadding: verticalPadding,818 horizontalPadding: horizontalPadding819 };820 821 // Sort the nodes in ascending order of their areas822 nodes.sort(function (n1, n2) {823 if (n1.rect.width * n1.rect.height > n2.rect.width * n2.rect.height)824 return -1;825 if (n1.rect.width * n1.rect.height < n2.rect.width * n2.rect.height)826 return 1;827 return 0;828 });829 830 // Create the organization -> tile members831 for (var i = 0; i < nodes.length; i++) {832 var lNode = nodes[i];833 834 if (organization.rows.length == 0) {835 this.insertNodeToRow(organization, lNode, 0, minWidth);836 }837 else if (this.canAddHorizontal(organization, lNode.rect.width, lNode.rect.height)) {838 this.insertNodeToRow(organization, lNode, this.getShortestRowIndex(organization), minWidth);839 }840 else {841 this.insertNodeToRow(organization, lNode, organization.rows.length, minWidth);842 }843 844 this.shiftToLastRow(organization);845 }846 847 return organization;848};849 850CoSELayout.prototype.insertNodeToRow = function (organization, node, rowIndex, minWidth) {851 var minCompoundSize = minWidth;852 853 // Add new row if needed854 if (rowIndex == organization.rows.length) {855 var secondDimension = [];856 857 organization.rows.push(secondDimension);858 organization.rowWidth.push(minCompoundSize);859 organization.rowHeight.push(0);860 }861 862 // Update row width863 var w = organization.rowWidth[rowIndex] + node.rect.width;864 865 if (organization.rows[rowIndex].length > 0) {866 w += organization.horizontalPadding;867 }868 869 organization.rowWidth[rowIndex] = w;870 // Update compound width871 if (organization.width < w) {872 organization.width = w;873 }874 875 // Update height876 var h = node.rect.height;877 if (rowIndex > 0)878 h += organization.verticalPadding;879 880 var extraHeight = 0;881 if (h > organization.rowHeight[rowIndex]) {882 extraHeight = organization.rowHeight[rowIndex];883 organization.rowHeight[rowIndex] = h;884 extraHeight = organization.rowHeight[rowIndex] - extraHeight;885 }886 887 organization.height += extraHeight;888 889 // Insert node890 organization.rows[rowIndex].push(node);891};892 893//Scans the rows of an organization and returns the one with the min width894CoSELayout.prototype.getShortestRowIndex = function (organization) {895 var r = -1;896 var min = Number.MAX_VALUE;897 898 for (var i = 0; i < organization.rows.length; i++) {899 if (organization.rowWidth[i] < min) {900 r = i;901 min = organization.rowWidth[i];902 }903 }904 return r;905};906 907//Scans the rows of an organization and returns the one with the max width908CoSELayout.prototype.getLongestRowIndex = function (organization) {909 var r = -1;910 var max = Number.MIN_VALUE;911 912 for (var i = 0; i < organization.rows.length; i++) {913 914 if (organization.rowWidth[i] > max) {915 r = i;916 max = organization.rowWidth[i];917 }918 }919 920 return r;921};922 923/**924* This method checks whether adding extra width to the organization violates925* the aspect ratio(1) or not.926*/927CoSELayout.prototype.canAddHorizontal = function (organization, extraWidth, extraHeight) {928 929 var sri = this.getShortestRowIndex(organization);930 931 if (sri < 0) {932 return true;933 }934 935 var min = organization.rowWidth[sri];936 937 if (min + organization.horizontalPadding + extraWidth <= organization.width)938 return true;939 940 var hDiff = 0;941 942 // Adding to an existing row943 if (organization.rowHeight[sri] < extraHeight) {944 if (sri > 0)945 hDiff = extraHeight + organization.verticalPadding - organization.rowHeight[sri];946 }947 948 var add_to_row_ratio;949 if (organization.width - min >= extraWidth + organization.horizontalPadding) {950 add_to_row_ratio = (organization.height + hDiff) / (min + extraWidth + organization.horizontalPadding);951 } else {952 add_to_row_ratio = (organization.height + hDiff) / organization.width;953 }954 955 // Adding a new row for this node956 hDiff = extraHeight + organization.verticalPadding;957 var add_new_row_ratio;958 if (organization.width < extraWidth) {959 add_new_row_ratio = (organization.height + hDiff) / extraWidth;960 } else {961 add_new_row_ratio = (organization.height + hDiff) / organization.width;962 }963 964 if (add_new_row_ratio < 1)965 add_new_row_ratio = 1 / add_new_row_ratio;966 967 if (add_to_row_ratio < 1)968 add_to_row_ratio = 1 / add_to_row_ratio;969 970 return add_to_row_ratio < add_new_row_ratio;971};972 973//If moving the last node from the longest row and adding it to the last974//row makes the bounding box smaller, do it.975CoSELayout.prototype.shiftToLastRow = function (organization) {976 var longest = this.getLongestRowIndex(organization);977 var last = organization.rowWidth.length - 1;978 var row = organization.rows[longest];979 var node = row[row.length - 1];980 981 var diff = node.width + organization.horizontalPadding;982 983 // Check if there is enough space on the last row984 if (organization.width - organization.rowWidth[last] > diff && longest != last) {985 // Remove the last element of the longest row986 row.splice(-1, 1);987 988 // Push it to the last row989 organization.rows[last].push(node);990 991 organization.rowWidth[longest] = organization.rowWidth[longest] - diff;992 organization.rowWidth[last] = organization.rowWidth[last] + diff;993 organization.width = organization.rowWidth[instance.getLongestRowIndex(organization)];994 995 // Update heights of the organization996 var maxHeight = Number.MIN_VALUE;997 for (var i = 0; i < row.length; i++) {998 if (row[i].height > maxHeight)999 maxHeight = row[i].height;1000 }1001 if (longest > 0)1002 maxHeight += organization.verticalPadding;1003 1004 var prevTotal = organization.rowHeight[longest] + organization.rowHeight[last];1005 1006 organization.rowHeight[longest] = maxHeight;1007 if (organization.rowHeight[last] < node.height + organization.verticalPadding)1008 organization.rowHeight[last] = node.height + organization.verticalPadding;1009 1010 var finalTotal = organization.rowHeight[longest] + organization.rowHeight[last];1011 organization.height += (finalTotal - prevTotal);1012 1013 this.shiftToLastRow(organization);1014 }1015};1016 1017CoSELayout.prototype.tilingPreLayout = function() {1018 if (CoSEConstants.TILE) {1019 // Find zero degree nodes and create a compound for each level1020 this.groupZeroDegreeMembers();1021 // Tile and clear children of each compound1022 this.clearCompounds();1023 // Separately tile and clear zero degree nodes for each level1024 this.clearZeroDegreeMembers();1025 }1026};1027 1028CoSELayout.prototype.tilingPostLayout = function() {1029 if (CoSEConstants.TILE) {1030 this.repopulateZeroDegreeMembers();1031 this.repopulateCompounds();1032 }1033};1034 1035// -----------------------------------------------------------------------------1036// Section: Tree Reduction methods1037// -----------------------------------------------------------------------------1038// Reduce trees 1039CoSELayout.prototype.reduceTrees = function ()1040{1041 var prunedNodesAll = [];1042 var containsLeaf = true;1043 var node;1044 1045 while(containsLeaf) {1046 var allNodes = this.graphManager.getAllNodes();1047 var prunedNodesInStepTemp = [];1048 containsLeaf = false;1049 1050 for (var i = 0; i < allNodes.length; i++) {1051 node = allNodes[i];1052 if(node.getEdges().length == 1 && !node.getEdges()[0].isInterGraph && node.getChild() == null){1053 prunedNodesInStepTemp.push([node, node.getEdges()[0], node.getOwner()]);1054 containsLeaf = true;1055 } 1056 }1057 if(containsLeaf == true){1058 var prunedNodesInStep = [];1059 for(var j = 0; j < prunedNodesInStepTemp.length; j++){1060 if(prunedNodesInStepTemp[j][0].getEdges().length == 1){1061 prunedNodesInStep.push(prunedNodesInStepTemp[j]); 1062 prunedNodesInStepTemp[j][0].getOwner().remove(prunedNodesInStepTemp[j][0]);1063 }1064 }1065 prunedNodesAll.push(prunedNodesInStep);1066 this.graphManager.resetAllNodes();1067 this.graphManager.resetAllEdges();1068 }1069 }1070 this.prunedNodesAll = prunedNodesAll;1071};1072 1073// Grow tree one step 1074CoSELayout.prototype.growTree = function(prunedNodesAll)1075{1076 var lengthOfPrunedNodesInStep = prunedNodesAll.length; 1077 var prunedNodesInStep = prunedNodesAll[lengthOfPrunedNodesInStep - 1]; 1078 1079 var nodeData; 1080 for(var i = 0; i < prunedNodesInStep.length; i++){1081 nodeData = prunedNodesInStep[i];1082 1083 this.findPlaceforPrunedNode(nodeData);1084 1085 nodeData[2].add(nodeData[0]);1086 nodeData[2].add(nodeData[1], nodeData[1].source, nodeData[1].target);1087 }1088 1089 prunedNodesAll.splice(prunedNodesAll.length-1, 1);1090 this.graphManager.resetAllNodes();1091 this.graphManager.resetAllEdges();1092};1093 1094// Find an appropriate position to replace pruned node, this method can be improved1095CoSELayout.prototype.findPlaceforPrunedNode = function(nodeData){1096 1097 var gridForPrunedNode; 1098 var nodeToConnect;1099 var prunedNode = nodeData[0];1100 if(prunedNode == nodeData[1].source){1101 nodeToConnect = nodeData[1].target;1102 }1103 else {1104 nodeToConnect = nodeData[1].source; 1105 }1106 var startGridX = nodeToConnect.startX;1107 var finishGridX = nodeToConnect.finishX;1108 var startGridY = nodeToConnect.startY;1109 var finishGridY = nodeToConnect.finishY; 1110 1111 var upNodeCount = 0;1112 var downNodeCount = 0;1113 var rightNodeCount = 0;1114 var leftNodeCount = 0;1115 var controlRegions = [upNodeCount, rightNodeCount, downNodeCount, leftNodeCount]1116 1117 if(startGridY > 0){1118 for(var i = startGridX; i <= finishGridX; i++ ){1119 controlRegions[0] += (this.grid[i][startGridY - 1].length + this.grid[i][startGridY].length - 1); 1120 }1121 }1122 if(finishGridX < this.grid.length - 1){1123 for(var i = startGridY; i <= finishGridY; i++ ){1124 controlRegions[1] += (this.grid[finishGridX + 1][i].length + this.grid[finishGridX][i].length - 1); 1125 }1126 }1127 if(finishGridY < this.grid[0].length - 1){1128 for(var i = startGridX; i <= finishGridX; i++ ){1129 controlRegions[2] += (this.grid[i][finishGridY + 1].length + this.grid[i][finishGridY].length - 1); 1130 }1131 }1132 if(startGridX > 0){1133 for(var i = startGridY; i <= finishGridY; i++ ){1134 controlRegions[3] += (this.grid[startGridX - 1][i].length + this.grid[startGridX][i].length - 1); 1135 }1136 }1137 var min = Integer.MAX_VALUE;1138 var minCount;1139 var minIndex;1140 for(var j = 0; j < controlRegions.length; j++){1141 if(controlRegions[j] < min){1142 min = controlRegions[j];1143 minCount = 1;1144 minIndex = j;1145 } 1146 else if(controlRegions[j] == min){1147 minCount++; 1148 }1149 }1150 1151 if(minCount == 3 && min == 0){1152 if(controlRegions[0] == 0 && controlRegions[1] == 0 && controlRegions[2] == 0){1153 gridForPrunedNode = 1; 1154 }1155 else if(controlRegions[0] == 0 && controlRegions[1] == 0 && controlRegions[3] == 0){1156 gridForPrunedNode = 0; 1157 }1158 else if(controlRegions[0] == 0 && controlRegions[2] == 0 && controlRegions[3] == 0){1159 gridForPrunedNode = 3; 1160 }1161 else if(controlRegions[1] == 0 && controlRegions[2] == 0 && controlRegions[3] == 0){1162 gridForPrunedNode = 2; 1163 }1164 }1165 else if(minCount == 2 && min == 0){1166 var random = Math.floor(Math.random() * 2);1167 if(controlRegions[0] == 0 && controlRegions[1] == 0){;1168 if(random == 0){1169 gridForPrunedNode = 0;1170 }1171 else{1172 gridForPrunedNode = 1;1173 }1174 }1175 else if(controlRegions[0] == 0 && controlRegions[2] == 0){1176 if(random == 0){1177 gridForPrunedNode = 0;1178 }1179 else{1180 gridForPrunedNode = 2;1181 }1182 }1183 else if(controlRegions[0] == 0 && controlRegions[3] == 0){1184 if(random == 0){1185 gridForPrunedNode = 0;1186 }1187 else{1188 gridForPrunedNode = 3;1189 }1190 }1191 else if(controlRegions[1] == 0 && controlRegions[2] == 0){1192 if(random == 0){1193 gridForPrunedNode = 1;1194 }1195 else{1196 gridForPrunedNode = 2;1197 }1198 }1199 else if(controlRegions[1] == 0 && controlRegions[3] == 0){1200 if(random == 0){