Brunobkr/llama.cpp_AlgMor24_github

1var LayoutConstants = require('./LayoutConstants');
2var LGraphManager = require('./LGraphManager');
3var LNode = require('./LNode');
4var LEdge = require('./LEdge');
5var LGraph = require('./LGraph');
6var PointD = require('./util/PointD');
7var Transform = require('./util/Transform');
8var Emitter = require('./util/Emitter');
9
10function Layout(isRemoteUse) {
11  Emitter.call( this );
12
13  //Layout Quality: 0:draft, 1:default, 2:proof
14  this.layoutQuality = LayoutConstants.QUALITY;
15  //Whether layout should create bendpoints as needed or not
16  this.createBendsAsNeeded =
17          LayoutConstants.DEFAULT_CREATE_BENDS_AS_NEEDED;
18  //Whether layout should be incremental or not
19  this.incremental = LayoutConstants.DEFAULT_INCREMENTAL;
20  //Whether we animate from before to after layout node positions
21  this.animationOnLayout =
22          LayoutConstants.DEFAULT_ANIMATION_ON_LAYOUT;
23  //Whether we animate the layout process or not
24  this.animationDuringLayout = LayoutConstants.DEFAULT_ANIMATION_DURING_LAYOUT;
25  //Number iterations that should be done between two successive animations
26  this.animationPeriod = LayoutConstants.DEFAULT_ANIMATION_PERIOD;
27  /**
28   * Whether or not leaf nodes (non-compound nodes) are of uniform sizes. When
29   * they are, both spring and repulsion forces between two leaf nodes can be
30   * calculated without the expensive clipping point calculations, resulting
31   * in major speed-up.
32   */
33  this.uniformLeafNodeSizes =
34          LayoutConstants.DEFAULT_UNIFORM_LEAF_NODE_SIZES;
35  /**
36   * This is used for creation of bendpoints by using dummy nodes and edges.
37   * Maps an LEdge to its dummy bendpoint path.
38   */
39  this.edgeToDummyNodes = new Map();
40  this.graphManager = new LGraphManager(this);
41  this.isLayoutFinished = false;
42  this.isSubLayout = false;
43  this.isRemoteUse = false;
44
45  if (isRemoteUse != null) {
46    this.isRemoteUse = isRemoteUse;
47  }
48}
49
50Layout.RANDOM_SEED = 1;
51
52Layout.prototype = Object.create( Emitter.prototype );
53
54Layout.prototype.getGraphManager = function () {
55  return this.graphManager;
56};
57
58Layout.prototype.getAllNodes = function () {
59  return this.graphManager.getAllNodes();
60};
61
62Layout.prototype.getAllEdges = function () {
63  return this.graphManager.getAllEdges();
64};
65
66Layout.prototype.getAllNodesToApplyGravitation = function () {
67  return this.graphManager.getAllNodesToApplyGravitation();
68};
69
70Layout.prototype.newGraphManager = function () {
71  var gm = new LGraphManager(this);
72  this.graphManager = gm;
73  return gm;
74};
75
76Layout.prototype.newGraph = function (vGraph)
77{
78  return new LGraph(null, this.graphManager, vGraph);
79};
80
81Layout.prototype.newNode = function (vNode)
82{
83  return new LNode(this.graphManager, vNode);
84};
85
86Layout.prototype.newEdge = function (vEdge)
87{
88  return new LEdge(null, null, vEdge);
89};
90
91Layout.prototype.checkLayoutSuccess = function() {
92  return (this.graphManager.getRoot() == null)
93          || this.graphManager.getRoot().getNodes().length == 0
94          || this.graphManager.includesInvalidEdge();
95};
96
97Layout.prototype.runLayout = function ()
98{
99  this.isLayoutFinished = false;
100  
101  if (this.tilingPreLayout) {
102    this.tilingPreLayout();
103  }
104
105  this.initParameters();
106  var isLayoutSuccessfull;
107
108  if (this.checkLayoutSuccess())
109  {
110    isLayoutSuccessfull = false;
111  }
112  else
113  {
114    isLayoutSuccessfull = this.layout();
115  }
116  
117  if (LayoutConstants.ANIMATE === 'during') {
118    // If this is a 'during' layout animation. Layout is not finished yet. 
119    // We need to perform these in index.js when layout is really finished.
120    return false;
121  }
122  
123  if (isLayoutSuccessfull)
124  {
125    if (!this.isSubLayout)
126    {
127      this.doPostLayout();
128    }
129  }
130
131  if (this.tilingPostLayout) {
132    this.tilingPostLayout();
133  }
134
135  this.isLayoutFinished = true;
136
137  return isLayoutSuccessfull;
138};
139
140/**
141 * This method performs the operations required after layout.
142 */
143Layout.prototype.doPostLayout = function ()
144{
145  //assert !isSubLayout : "Should not be called on sub-layout!";
146  // Propagate geometric changes to v-level objects
147  if(!this.incremental){
148    this.transform();
149  }
150  this.update();
151};
152
153/**
154 * This method updates the geometry of the target graph according to
155 * calculated layout.
156 */
157Layout.prototype.update2 = function () {
158  // update bend points
159  if (this.createBendsAsNeeded)
160  {
161    this.createBendpointsFromDummyNodes();
162
163    // reset all edges, since the topology has changed
164    this.graphManager.resetAllEdges();
165  }
166
167  // perform edge, node and root updates if layout is not called
168  // remotely
169  if (!this.isRemoteUse)
170  {
171    // update all edges
172    var edge;
173    var allEdges = this.graphManager.getAllEdges();
174    for (var i = 0; i < allEdges.length; i++)
175    {
176      edge = allEdges[i];
177//      this.update(edge);
178    }
179
180    // recursively update nodes
181    var node;
182    var nodes = this.graphManager.getRoot().getNodes();
183    for (var i = 0; i < nodes.length; i++)
184    {
185      node = nodes[i];
186//      this.update(node);
187    }
188
189    // update root graph
190    this.update(this.graphManager.getRoot());
191  }
192};
193
194Layout.prototype.update = function (obj) {
195  if (obj == null) {
196    this.update2();
197  }
198  else if (obj instanceof LNode) {
199    var node = obj;
200    if (node.getChild() != null)
201    {
202      // since node is compound, recursively update child nodes
203      var nodes = node.getChild().getNodes();
204      for (var i = 0; i < nodes.length; i++)
205      {
206        update(nodes[i]);
207      }
208    }
209
210    // if the l-level node is associated with a v-level graph object,
211    // then it is assumed that the v-level node implements the
212    // interface Updatable.
213    if (node.vGraphObject != null)
214    {
215      // cast to Updatable without any type check
216      var vNode = node.vGraphObject;
217
218      // call the update method of the interface
219      vNode.update(node);
220    }
221  }
222  else if (obj instanceof LEdge) {
223    var edge = obj;
224    // if the l-level edge is associated with a v-level graph object,
225    // then it is assumed that the v-level edge implements the
226    // interface Updatable.
227
228    if (edge.vGraphObject != null)
229    {
230      // cast to Updatable without any type check
231      var vEdge = edge.vGraphObject;
232
233      // call the update method of the interface
234      vEdge.update(edge);
235    }
236  }
237  else if (obj instanceof LGraph) {
238    var graph = obj;
239    // if the l-level graph is associated with a v-level graph object,
240    // then it is assumed that the v-level object implements the
241    // interface Updatable.
242
243    if (graph.vGraphObject != null)
244    {
245      // cast to Updatable without any type check
246      var vGraph = graph.vGraphObject;
247
248      // call the update method of the interface
249      vGraph.update(graph);
250    }
251  }
252};
253
254/**
255 * This method is used to set all layout parameters to default values
256 * determined at compile time.
257 */
258Layout.prototype.initParameters = function () {
259  if (!this.isSubLayout)
260  {
261    this.layoutQuality = LayoutConstants.QUALITY;
262    this.animationDuringLayout = LayoutConstants.DEFAULT_ANIMATION_DURING_LAYOUT;
263    this.animationPeriod = LayoutConstants.DEFAULT_ANIMATION_PERIOD;
264    this.animationOnLayout = LayoutConstants.DEFAULT_ANIMATION_ON_LAYOUT;
265    this.incremental = LayoutConstants.DEFAULT_INCREMENTAL;
266    this.createBendsAsNeeded = LayoutConstants.DEFAULT_CREATE_BENDS_AS_NEEDED;
267    this.uniformLeafNodeSizes = LayoutConstants.DEFAULT_UNIFORM_LEAF_NODE_SIZES;
268  }
269
270  if (this.animationDuringLayout)
271  {
272    this.animationOnLayout = false;
273  }
274};
275
276Layout.prototype.transform = function (newLeftTop) {
277  if (newLeftTop == undefined) {
278    this.transform(new PointD(0, 0));
279  }
280  else {
281    // create a transformation object (from Eclipse to layout). When an
282    // inverse transform is applied, we get upper-left coordinate of the
283    // drawing or the root graph at given input coordinate (some margins
284    // already included in calculation of left-top).
285
286    var trans = new Transform();
287    var leftTop = this.graphManager.getRoot().updateLeftTop();
288
289    if (leftTop != null)
290    {
291      trans.setWorldOrgX(newLeftTop.x);
292      trans.setWorldOrgY(newLeftTop.y);
293
294      trans.setDeviceOrgX(leftTop.x);
295      trans.setDeviceOrgY(leftTop.y);
296
297      var nodes = this.getAllNodes();
298      var node;
299
300      for (var i = 0; i < nodes.length; i++)
301      {
302        node = nodes[i];
303        node.transform(trans);
304      }
305    }
306  }
307};
308
309Layout.prototype.positionNodesRandomly = function (graph) {
310
311  if (graph == undefined) {
312    //assert !this.incremental;
313    this.positionNodesRandomly(this.getGraphManager().getRoot());
314    this.getGraphManager().getRoot().updateBounds(true);
315  }
316  else {
317    var lNode;
318    var childGraph;
319
320    var nodes = graph.getNodes();
321    for (var i = 0; i < nodes.length; i++)
322    {
323      lNode = nodes[i];
324      childGraph = lNode.getChild();
325
326      if (childGraph == null)
327      {
328        lNode.scatter();
329      }
330      else if (childGraph.getNodes().length == 0)
331      {
332        lNode.scatter();
333      }
334      else
335      {
336        this.positionNodesRandomly(childGraph);
337        lNode.updateBounds();
338      }
339    }
340  }
341};
342
343/**
344 * This method returns a list of trees where each tree is represented as a
345 * list of l-nodes. The method returns a list of size 0 when:
346 * - The graph is not flat or
347 * - One of the component(s) of the graph is not a tree.
348 */
349Layout.prototype.getFlatForest = function ()
350{
351  var flatForest = [];
352  var isForest = true;
353
354  // Quick reference for all nodes in the graph manager associated with
355  // this layout. The list should not be changed.
356  var allNodes = this.graphManager.getRoot().getNodes();
357
358  // First be sure that the graph is flat
359  var isFlat = true;
360
361  for (var i = 0; i < allNodes.length; i++)
362  {
363    if (allNodes[i].getChild() != null)
364    {
365      isFlat = false;
366    }
367  }
368
369  // Return empty forest if the graph is not flat.
370  if (!isFlat)
371  {
372    return flatForest;
373  }
374
375  // Run BFS for each component of the graph.
376
377  var visited = new Set();
378  var toBeVisited = [];
379  var parents = new Map();
380  var unProcessedNodes = [];
381
382  unProcessedNodes = unProcessedNodes.concat(allNodes);
383
384  // Each iteration of this loop finds a component of the graph and
385  // decides whether it is a tree or not. If it is a tree, adds it to the
386  // forest and continued with the next component.
387
388  while (unProcessedNodes.length > 0 && isForest)
389  {
390    toBeVisited.push(unProcessedNodes[0]);
391
392    // Start the BFS. Each iteration of this loop visits a node in a
393    // BFS manner.
394    while (toBeVisited.length > 0 && isForest)
395    {
396      //pool operation
397      var currentNode = toBeVisited[0];
398      toBeVisited.splice(0, 1);
399      visited.add(currentNode);
400
401      // Traverse all neighbors of this node
402      var neighborEdges = currentNode.getEdges();
403
404      for (var i = 0; i < neighborEdges.length; i++)
405      {
406        var currentNeighbor =
407                neighborEdges[i].getOtherEnd(currentNode);
408
409        // If BFS is not growing from this neighbor.
410        if (parents.get(currentNode) != currentNeighbor)
411        {
412          // We haven't previously visited this neighbor.
413          if (!visited.has(currentNeighbor))
414          {
415            toBeVisited.push(currentNeighbor);
416            parents.set(currentNeighbor, currentNode);
417          }
418          // Since we have previously visited this neighbor and
419          // this neighbor is not parent of currentNode, given
420          // graph contains a component that is not tree, hence
421          // it is not a forest.
422          else
423          {
424            isForest = false;
425            break;
426          }
427        }
428      }
429    }
430
431    // The graph contains a component that is not a tree. Empty
432    // previously found trees. The method will end.
433    if (!isForest)
434    {
435      flatForest = [];
436    }
437    // Save currently visited nodes as a tree in our forest. Reset
438    // visited and parents lists. Continue with the next component of
439    // the graph, if any.
440    else
441    {
442      var temp = [...visited];
443      flatForest.push(temp);
444      //flatForest = flatForest.concat(temp);
445      //unProcessedNodes.removeAll(visited);
446      for (var i = 0; i < temp.length; i++) {
447        var value = temp[i];
448        var index = unProcessedNodes.indexOf(value);
449        if (index > -1) {
450          unProcessedNodes.splice(index, 1);
451        }
452      }
453      visited = new Set();
454      parents = new Map();
455    }
456  }
457
458  return flatForest;
459};
460
461/**
462 * This method creates dummy nodes (an l-level node with minimal dimensions)
463 * for the given edge (one per bendpoint). The existing l-level structure
464 * is updated accordingly.
465 */
466Layout.prototype.createDummyNodesForBendpoints = function (edge)
467{
468  var dummyNodes = [];
469  var prev = edge.source;
470
471  var graph = this.graphManager.calcLowestCommonAncestor(edge.source, edge.target);
472
473  for (var i = 0; i < edge.bendpoints.length; i++)
474  {
475    // create new dummy node
476    var dummyNode = this.newNode(null);
477    dummyNode.setRect(new Point(0, 0), new Dimension(1, 1));
478
479    graph.add(dummyNode);
480
481    // create new dummy edge between prev and dummy node
482    var dummyEdge = this.newEdge(null);
483    this.graphManager.add(dummyEdge, prev, dummyNode);
484
485    dummyNodes.add(dummyNode);
486    prev = dummyNode;
487  }
488
489  var dummyEdge = this.newEdge(null);
490  this.graphManager.add(dummyEdge, prev, edge.target);
491
492  this.edgeToDummyNodes.set(edge, dummyNodes);
493
494  // remove real edge from graph manager if it is inter-graph
495  if (edge.isInterGraph())
496  {
497    this.graphManager.remove(edge);
498  }
499  // else, remove the edge from the current graph
500  else
501  {
502    graph.remove(edge);
503  }
504
505  return dummyNodes;
506};
507
508/**
509 * This method creates bendpoints for edges from the dummy nodes
510 * at l-level.
511 */
512Layout.prototype.createBendpointsFromDummyNodes = function ()
513{
514  var edges = [];
515  edges = edges.concat(this.graphManager.getAllEdges());
516  edges = [...this.edgeToDummyNodes.keys()].concat(edges);
517
518  for (var k = 0; k < edges.length; k++)
519  {
520    var lEdge = edges[k];
521
522    if (lEdge.bendpoints.length > 0)
523    {
524      var path = this.edgeToDummyNodes.get(lEdge);
525
526      for (var i = 0; i < path.length; i++)
527      {
528        var dummyNode = path[i];
529        var p = new PointD(dummyNode.getCenterX(),
530                dummyNode.getCenterY());
531
532        // update bendpoint's location according to dummy node
533        var ebp = lEdge.bendpoints.get(i);
534        ebp.x = p.x;
535        ebp.y = p.y;
536
537        // remove the dummy node, dummy edges incident with this
538        // dummy node is also removed (within the remove method)
539        dummyNode.getOwner().remove(dummyNode);
540      }
541
542      // add the real edge to graph
543      this.graphManager.add(lEdge, lEdge.source, lEdge.target);
544    }
545  }
546};
547
548Layout.transform = function (sliderValue, defaultValue, minDiv, maxMul) {
549  if (minDiv != undefined && maxMul != undefined) {
550    var value = defaultValue;
551
552    if (sliderValue <= 50)
553    {
554      var minValue = defaultValue / minDiv;
555      value -= ((defaultValue - minValue) / 50) * (50 - sliderValue);
556    }
557    else
558    {
559      var maxValue = defaultValue * maxMul;
560      value += ((maxValue - defaultValue) / 50) * (sliderValue - 50);
561    }
562
563    return value;
564  }
565  else {
566    var a, b;
567
568    if (sliderValue <= 50)
569    {
570      a = 9.0 * defaultValue / 500.0;
571      b = defaultValue / 10.0;
572    }
573    else
574    {
575      a = 9.0 * defaultValue / 50.0;
576      b = -8 * defaultValue;
577    }
578
579    return (a * sliderValue + b);
580  }
581};
582
583/**
584 * This method finds and returns the center of the given nodes, assuming
585 * that the given nodes form a tree in themselves.
586 */
587Layout.findCenterOfTree = function (nodes)
588{
589  var list = [];
590  list = list.concat(nodes);
591
592  var removedNodes = [];
593  var remainingDegrees = new Map();
594  var foundCenter = false;
595  var centerNode = null;
596
597  if (list.length == 1 || list.length == 2)
598  {
599    foundCenter = true;
600    centerNode = list[0];
601  }
602
603  for (var i = 0; i < list.length; i++)
604  {
605    var node = list[i];
606    var degree = node.getNeighborsList().size;
607    remainingDegrees.set(node, node.getNeighborsList().size);
608
609    if (degree == 1)
610    {
611      removedNodes.push(node);
612    }
613  }
614
615  var tempList = [];
616  tempList = tempList.concat(removedNodes);
617
618  while (!foundCenter)
619  {
620    var tempList2 = [];
621    tempList2 = tempList2.concat(tempList);
622    tempList = [];
623
624    for (var i = 0; i < list.length; i++)
625    {
626      var node = list[i];
627
628      var index = list.indexOf(node);
629      if (index >= 0) {
630        list.splice(index, 1);
631      }
632
633      var neighbours = node.getNeighborsList();
634
635      neighbours.forEach(function(neighbour) {
636        if (removedNodes.indexOf(neighbour) < 0)
637        {
638          var otherDegree = remainingDegrees.get(neighbour);
639          var newDegree = otherDegree - 1;
640
641          if (newDegree == 1)
642          {
643            tempList.push(neighbour);
644          }
645
646          remainingDegrees.set(neighbour, newDegree);
647        }
648      });
649    }
650
651    removedNodes = removedNodes.concat(tempList);
652
653    if (list.length == 1 || list.length == 2)
654    {
655      foundCenter = true;
656      centerNode = list[0];
657    }
658  }
659
660  return centerNode;
661};
662
663/**
664 * During the coarsening process, this layout may be referenced by two graph managers
665 * this setter function grants access to change the currently being used graph manager
666 */
667Layout.prototype.setGraphManager = function (gm)
668{
669  this.graphManager = gm;
670};
671
672module.exports = Layout;
673