Brunobkr/llama.cpp_AlgMor24_github

1var LGraphObject = require('./LGraphObject');
2var Integer = require('./util/Integer');
3var LayoutConstants = require('./LayoutConstants');
4var LGraphManager = require('./LGraphManager');
5var LNode = require('./LNode');
6var LEdge = require('./LEdge');
7var RectangleD = require('./util/RectangleD');
8var Point = require('./util/Point');
9var LinkedList = require('./util/LinkedList');
10
11function LGraph(parent, obj2, vGraph) {
12  LGraphObject.call(this, vGraph);
13  this.estimatedSize = Integer.MIN_VALUE;
14  this.margin = LayoutConstants.DEFAULT_GRAPH_MARGIN;
15  this.edges = [];
16  this.nodes = [];
17  this.isConnected = false;
18  this.parent = parent;
19
20  if (obj2 != null && obj2 instanceof LGraphManager) {
21    this.graphManager = obj2;
22  }
23  else if (obj2 != null && obj2 instanceof Layout) {
24    this.graphManager = obj2.graphManager;
25  }
26}
27
28LGraph.prototype = Object.create(LGraphObject.prototype);
29for (var prop in LGraphObject) {
30  LGraph[prop] = LGraphObject[prop];
31}
32
33LGraph.prototype.getNodes = function () {
34  return this.nodes;
35};
36
37LGraph.prototype.getEdges = function () {
38  return this.edges;
39};
40
41LGraph.prototype.getGraphManager = function ()
42{
43  return this.graphManager;
44};
45
46LGraph.prototype.getParent = function ()
47{
48  return this.parent;
49};
50
51LGraph.prototype.getLeft = function ()
52{
53  return this.left;
54};
55
56LGraph.prototype.getRight = function ()
57{
58  return this.right;
59};
60
61LGraph.prototype.getTop = function ()
62{
63  return this.top;
64};
65
66LGraph.prototype.getBottom = function ()
67{
68  return this.bottom;
69};
70
71LGraph.prototype.isConnected = function ()
72{
73  return this.isConnected;
74};
75
76LGraph.prototype.add = function (obj1, sourceNode, targetNode) {
77  if (sourceNode == null && targetNode == null) {
78    var newNode = obj1;
79    if (this.graphManager == null) {
80      throw "Graph has no graph mgr!";
81    }
82    if (this.getNodes().indexOf(newNode) > -1) {
83      throw "Node already in graph!";
84    }
85    newNode.owner = this;
86    this.getNodes().push(newNode);
87
88    return newNode;
89  }
90  else {
91    var newEdge = obj1;
92    if (!(this.getNodes().indexOf(sourceNode) > -1 && (this.getNodes().indexOf(targetNode)) > -1)) {
93      throw "Source or target not in graph!";
94    }
95
96    if (!(sourceNode.owner == targetNode.owner && sourceNode.owner == this)) {
97      throw "Both owners must be this graph!";
98    }
99
100    if (sourceNode.owner != targetNode.owner)
101    {
102      return null;
103    }
104
105    // set source and target
106    newEdge.source = sourceNode;
107    newEdge.target = targetNode;
108
109    // set as intra-graph edge
110    newEdge.isInterGraph = false;
111
112    // add to graph edge list
113    this.getEdges().push(newEdge);
114
115    // add to incidency lists
116    sourceNode.edges.push(newEdge);
117
118    if (targetNode != sourceNode)
119    {
120      targetNode.edges.push(newEdge);
121    }
122
123    return newEdge;
124  }
125};
126
127LGraph.prototype.remove = function (obj) {
128  var node = obj;
129  if (obj instanceof LNode) {
130    if (node == null) {
131      throw "Node is null!";
132    }
133    if (!(node.owner != null && node.owner == this)) {
134      throw "Owner graph is invalid!";
135    }
136    if (this.graphManager == null) {
137      throw "Owner graph manager is invalid!";
138    }
139    // remove incident edges first (make a copy to do it safely)
140    var edgesToBeRemoved = node.edges.slice();
141    var edge;
142    var s = edgesToBeRemoved.length;
143    for (var i = 0; i < s; i++)
144    {
145      edge = edgesToBeRemoved[i];
146
147      if (edge.isInterGraph)
148      {
149        this.graphManager.remove(edge);
150      }
151      else
152      {
153        edge.source.owner.remove(edge);
154      }
155    }
156
157    // now the node itself
158    var index = this.nodes.indexOf(node);
159    if (index == -1) {
160      throw "Node not in owner node list!";
161    }
162
163    this.nodes.splice(index, 1);
164  }
165  else if (obj instanceof LEdge) {
166    var edge = obj;
167    if (edge == null) {
168      throw "Edge is null!";
169    }
170    if (!(edge.source != null && edge.target != null)) {
171      throw "Source and/or target is null!";
172    }
173    if (!(edge.source.owner != null && edge.target.owner != null &&
174            edge.source.owner == this && edge.target.owner == this)) {
175      throw "Source and/or target owner is invalid!";
176    }
177
178    var sourceIndex = edge.source.edges.indexOf(edge);
179    var targetIndex = edge.target.edges.indexOf(edge);
180    if (!(sourceIndex > -1 && targetIndex > -1)) {
181      throw "Source and/or target doesn't know this edge!";
182    }
183
184    edge.source.edges.splice(sourceIndex, 1);
185
186    if (edge.target != edge.source)
187    {
188      edge.target.edges.splice(targetIndex, 1);
189    }
190
191    var index = edge.source.owner.getEdges().indexOf(edge);
192    if (index == -1) {
193      throw "Not in owner's edge list!";
194    }
195
196    edge.source.owner.getEdges().splice(index, 1);
197  }
198};
199
200LGraph.prototype.updateLeftTop = function ()
201{
202  var top = Integer.MAX_VALUE;
203  var left = Integer.MAX_VALUE;
204  var nodeTop;
205  var nodeLeft;
206  var margin;
207
208  var nodes = this.getNodes();
209  var s = nodes.length;
210
211  for (var i = 0; i < s; i++)
212  {
213    var lNode = nodes[i];
214    nodeTop = lNode.getTop();
215    nodeLeft = lNode.getLeft();
216
217    if (top > nodeTop)
218    {
219      top = nodeTop;
220    }
221
222    if (left > nodeLeft)
223    {
224      left = nodeLeft;
225    }
226  }
227
228  // Do we have any nodes in this graph?
229  if (top == Integer.MAX_VALUE)
230  {
231    return null;
232  }
233
234  if(nodes[0].getParent().paddingLeft != undefined){
235    margin = nodes[0].getParent().paddingLeft;
236  }
237  else{
238    margin = this.margin;
239  }
240
241  this.left = left - margin;
242  this.top = top - margin;
243
244  // Apply the margins and return the result
245  return new Point(this.left, this.top);
246};
247
248LGraph.prototype.updateBounds = function (recursive)
249{
250  // calculate bounds
251  var left = Integer.MAX_VALUE;
252  var right = -Integer.MAX_VALUE;
253  var top = Integer.MAX_VALUE;
254  var bottom = -Integer.MAX_VALUE;
255  var nodeLeft;
256  var nodeRight;
257  var nodeTop;
258  var nodeBottom;
259  var margin;
260
261  var nodes = this.nodes;
262  var s = nodes.length;
263  for (var i = 0; i < s; i++)
264  {
265    var lNode = nodes[i];
266
267    if (recursive && lNode.child != null)
268    {
269      lNode.updateBounds();
270    }
271    nodeLeft = lNode.getLeft();
272    nodeRight = lNode.getRight();
273    nodeTop = lNode.getTop();
274    nodeBottom = lNode.getBottom();
275
276    if (left > nodeLeft)
277    {
278      left = nodeLeft;
279    }
280
281    if (right < nodeRight)
282    {
283      right = nodeRight;
284    }
285
286    if (top > nodeTop)
287    {
288      top = nodeTop;
289    }
290
291    if (bottom < nodeBottom)
292    {
293      bottom = nodeBottom;
294    }
295  }
296
297  var boundingRect = new RectangleD(left, top, right - left, bottom - top);
298  if (left == Integer.MAX_VALUE)
299  {
300    this.left = this.parent.getLeft();
301    this.right = this.parent.getRight();
302    this.top = this.parent.getTop();
303    this.bottom = this.parent.getBottom();
304  }
305
306  if(nodes[0].getParent().paddingLeft != undefined){
307    margin = nodes[0].getParent().paddingLeft;
308  }
309  else{
310    margin = this.margin;
311  }
312
313  this.left = boundingRect.x - margin;
314  this.right = boundingRect.x + boundingRect.width + margin;
315  this.top = boundingRect.y - margin;
316  this.bottom = boundingRect.y + boundingRect.height + margin;
317};
318
319LGraph.calculateBounds = function (nodes)
320{
321  var left = Integer.MAX_VALUE;
322  var right = -Integer.MAX_VALUE;
323  var top = Integer.MAX_VALUE;
324  var bottom = -Integer.MAX_VALUE;
325  var nodeLeft;
326  var nodeRight;
327  var nodeTop;
328  var nodeBottom;
329
330  var s = nodes.length;
331
332  for (var i = 0; i < s; i++)
333  {
334    var lNode = nodes[i];
335    nodeLeft = lNode.getLeft();
336    nodeRight = lNode.getRight();
337    nodeTop = lNode.getTop();
338    nodeBottom = lNode.getBottom();
339
340    if (left > nodeLeft)
341    {
342      left = nodeLeft;
343    }
344
345    if (right < nodeRight)
346    {
347      right = nodeRight;
348    }
349
350    if (top > nodeTop)
351    {
352      top = nodeTop;
353    }
354
355    if (bottom < nodeBottom)
356    {
357      bottom = nodeBottom;
358    }
359  }
360
361  var boundingRect = new RectangleD(left, top, right - left, bottom - top);
362
363  return boundingRect;
364};
365
366LGraph.prototype.getInclusionTreeDepth = function ()
367{
368  if (this == this.graphManager.getRoot())
369  {
370    return 1;
371  }
372  else
373  {
374    return this.parent.getInclusionTreeDepth();
375  }
376};
377
378LGraph.prototype.getEstimatedSize = function ()
379{
380  if (this.estimatedSize == Integer.MIN_VALUE) {
381    throw "assert failed";
382  }
383  return this.estimatedSize;
384};
385
386LGraph.prototype.calcEstimatedSize = function ()
387{
388  var size = 0;
389  var nodes = this.nodes;
390  var s = nodes.length;
391
392  for (var i = 0; i < s; i++)
393  {
394    var lNode = nodes[i];
395    size += lNode.calcEstimatedSize();
396  }
397
398  if (size == 0)
399  {
400    this.estimatedSize = LayoutConstants.EMPTY_COMPOUND_NODE_SIZE;
401  }
402  else
403  {
404    this.estimatedSize = size / Math.sqrt(this.nodes.length);
405  }
406
407  return this.estimatedSize;
408};
409
410LGraph.prototype.updateConnected = function ()
411{
412  var self = this;
413  if (this.nodes.length == 0)
414  {
415    this.isConnected = true;
416    return;
417  }
418
419  var queue = new LinkedList();
420  var visited = new Set();
421  var currentNode = this.nodes[0];
422  var neighborEdges;
423  var currentNeighbor;
424  var childrenOfNode = currentNode.withChildren();
425  childrenOfNode.forEach(function(node) {
426    queue.push(node);
427    visited.add(node);
428  });
429
430  while (queue.length !== 0)
431  {
432    currentNode = queue.shift();
433
434    // Traverse all neighbors of this node
435    neighborEdges = currentNode.getEdges();
436    var size = neighborEdges.length;
437    for (var i = 0; i < size; i++)
438    {
439      var neighborEdge = neighborEdges[i];
440      currentNeighbor =
441              neighborEdge.getOtherEndInGraph(currentNode, this);
442
443      // Add unvisited neighbors to the list to visit
444      if (currentNeighbor != null &&
445              !visited.has(currentNeighbor))
446      {
447        var childrenOfNeighbor = currentNeighbor.withChildren();
448
449        childrenOfNeighbor.forEach(function(node) {
450          queue.push(node);
451          visited.add(node);
452        });
453      }
454    }
455  }
456
457  this.isConnected = false;
458
459  if (visited.size >= this.nodes.length)
460  {
461    var noOfVisitedInThisGraph = 0;
462
463    visited.forEach(function(visitedNode) {
464      if (visitedNode.owner == self)
465      {
466        noOfVisitedInThisGraph++;
467      }
468    });
469
470    if (noOfVisitedInThisGraph == this.nodes.length)
471    {
472      this.isConnected = true;
473    }
474  }
475};
476
477module.exports = LGraph;
478