Brunobkr/llama.cpp_AlgMor24_github

1var LGraph;
2var LEdge = require('./LEdge');
3
4function LGraphManager(layout) {
5  LGraph = require('./LGraph'); // It may be better to initilize this out of this function but it gives an error (Right-hand side of 'instanceof' is not callable) now.
6  this.layout = layout;
7
8  this.graphs = [];
9  this.edges = [];
10}
11
12LGraphManager.prototype.addRoot = function ()
13{
14  var ngraph = this.layout.newGraph();
15  var nnode = this.layout.newNode(null);
16  var root = this.add(ngraph, nnode);
17  this.setRootGraph(root);
18  return this.rootGraph;
19};
20
21LGraphManager.prototype.add = function (newGraph, parentNode, newEdge, sourceNode, targetNode)
22{
23  //there are just 2 parameters are passed then it adds an LGraph else it adds an LEdge
24  if (newEdge == null && sourceNode == null && targetNode == null) {
25    if (newGraph == null) {
26      throw "Graph is null!";
27    }
28    if (parentNode == null) {
29      throw "Parent node is null!";
30    }
31    if (this.graphs.indexOf(newGraph) > -1) {
32      throw "Graph already in this graph mgr!";
33    }
34
35    this.graphs.push(newGraph);
36
37    if (newGraph.parent != null) {
38      throw "Already has a parent!";
39    }
40    if (parentNode.child != null) {
41      throw  "Already has a child!";
42    }
43
44    newGraph.parent = parentNode;
45    parentNode.child = newGraph;
46
47    return newGraph;
48  }
49  else {
50    //change the order of the parameters
51    targetNode = newEdge;
52    sourceNode = parentNode;
53    newEdge = newGraph;
54    var sourceGraph = sourceNode.getOwner();
55    var targetGraph = targetNode.getOwner();
56
57    if (!(sourceGraph != null && sourceGraph.getGraphManager() == this)) {
58      throw "Source not in this graph mgr!";
59    }
60    if (!(targetGraph != null && targetGraph.getGraphManager() == this)) {
61      throw "Target not in this graph mgr!";
62    }
63
64    if (sourceGraph == targetGraph)
65    {
66      newEdge.isInterGraph = false;
67      return sourceGraph.add(newEdge, sourceNode, targetNode);
68    }
69    else
70    {
71      newEdge.isInterGraph = true;
72
73      // set source and target
74      newEdge.source = sourceNode;
75      newEdge.target = targetNode;
76
77      // add edge to inter-graph edge list
78      if (this.edges.indexOf(newEdge) > -1) {
79        throw "Edge already in inter-graph edge list!";
80      }
81
82      this.edges.push(newEdge);
83
84      // add edge to source and target incidency lists
85      if (!(newEdge.source != null && newEdge.target != null)) {
86        throw "Edge source and/or target is null!";
87      }
88
89      if (!(newEdge.source.edges.indexOf(newEdge) == -1 && newEdge.target.edges.indexOf(newEdge) == -1)) {
90        throw "Edge already in source and/or target incidency list!";
91      }
92
93      newEdge.source.edges.push(newEdge);
94      newEdge.target.edges.push(newEdge);
95
96      return newEdge;
97    }
98  }
99};
100
101LGraphManager.prototype.remove = function (lObj) {
102  if (lObj instanceof LGraph) {
103    var graph = lObj;
104    if (graph.getGraphManager() != this) {
105      throw "Graph not in this graph mgr";
106    }
107    if (!(graph == this.rootGraph || (graph.parent != null && graph.parent.graphManager == this))) {
108      throw "Invalid parent node!";
109    }
110
111    // first the edges (make a copy to do it safely)
112    var edgesToBeRemoved = [];
113
114    edgesToBeRemoved = edgesToBeRemoved.concat(graph.getEdges());
115
116    var edge;
117    var s = edgesToBeRemoved.length;
118    for (var i = 0; i < s; i++)
119    {
120      edge = edgesToBeRemoved[i];
121      graph.remove(edge);
122    }
123
124    // then the nodes (make a copy to do it safely)
125    var nodesToBeRemoved = [];
126
127    nodesToBeRemoved = nodesToBeRemoved.concat(graph.getNodes());
128
129    var node;
130    s = nodesToBeRemoved.length;
131    for (var i = 0; i < s; i++)
132    {
133      node = nodesToBeRemoved[i];
134      graph.remove(node);
135    }
136
137    // check if graph is the root
138    if (graph == this.rootGraph)
139    {
140      this.setRootGraph(null);
141    }
142
143    // now remove the graph itself
144    var index = this.graphs.indexOf(graph);
145    this.graphs.splice(index, 1);
146
147    // also reset the parent of the graph
148    graph.parent = null;
149  }
150  else if (lObj instanceof LEdge) {
151    edge = lObj;
152    if (edge == null) {
153      throw "Edge is null!";
154    }
155    if (!edge.isInterGraph) {
156      throw "Not an inter-graph edge!";
157    }
158    if (!(edge.source != null && edge.target != null)) {
159      throw "Source and/or target is null!";
160    }
161
162    // remove edge from source and target nodes' incidency lists
163
164    if (!(edge.source.edges.indexOf(edge) != -1 && edge.target.edges.indexOf(edge) != -1)) {
165      throw "Source and/or target doesn't know this edge!";
166    }
167
168    var index = edge.source.edges.indexOf(edge);
169    edge.source.edges.splice(index, 1);
170    index = edge.target.edges.indexOf(edge);
171    edge.target.edges.splice(index, 1);
172
173    // remove edge from owner graph manager's inter-graph edge list
174
175    if (!(edge.source.owner != null && edge.source.owner.getGraphManager() != null)) {
176      throw "Edge owner graph or owner graph manager is null!";
177    }
178    if (edge.source.owner.getGraphManager().edges.indexOf(edge) == -1) {
179      throw "Not in owner graph manager's edge list!";
180    }
181
182    var index = edge.source.owner.getGraphManager().edges.indexOf(edge);
183    edge.source.owner.getGraphManager().edges.splice(index, 1);
184  }
185};
186
187LGraphManager.prototype.updateBounds = function ()
188{
189  this.rootGraph.updateBounds(true);
190};
191
192LGraphManager.prototype.getGraphs = function ()
193{
194  return this.graphs;
195};
196
197LGraphManager.prototype.getAllNodes = function ()
198{
199  if (this.allNodes == null)
200  {
201    var nodeList = [];
202    var graphs = this.getGraphs();
203    var s = graphs.length;
204    for (var i = 0; i < s; i++)
205    {
206      nodeList = nodeList.concat(graphs[i].getNodes());
207    }
208    this.allNodes = nodeList;
209  }
210  return this.allNodes;
211};
212
213LGraphManager.prototype.resetAllNodes = function ()
214{
215  this.allNodes = null;
216};
217
218LGraphManager.prototype.resetAllEdges = function ()
219{
220  this.allEdges = null;
221};
222
223LGraphManager.prototype.resetAllNodesToApplyGravitation = function ()
224{
225  this.allNodesToApplyGravitation = null;
226};
227
228LGraphManager.prototype.getAllEdges = function ()
229{
230  if (this.allEdges == null)
231  {
232    var edgeList = [];
233    var graphs = this.getGraphs();
234    var s = graphs.length;
235    for (var i = 0; i < graphs.length; i++)
236    {
237      edgeList = edgeList.concat(graphs[i].getEdges());
238    }
239
240    edgeList = edgeList.concat(this.edges);
241
242    this.allEdges = edgeList;
243  }
244  return this.allEdges;
245};
246
247LGraphManager.prototype.getAllNodesToApplyGravitation = function ()
248{
249  return this.allNodesToApplyGravitation;
250};
251
252LGraphManager.prototype.setAllNodesToApplyGravitation = function (nodeList)
253{
254  if (this.allNodesToApplyGravitation != null) {
255    throw "assert failed";
256  }
257
258  this.allNodesToApplyGravitation = nodeList;
259};
260
261LGraphManager.prototype.getRoot = function ()
262{
263  return this.rootGraph;
264};
265
266LGraphManager.prototype.setRootGraph = function (graph)
267{
268  if (graph.getGraphManager() != this) {
269    throw "Root not in this graph mgr!";
270  }
271
272  this.rootGraph = graph;
273  // root graph must have a root node associated with it for convenience
274  if (graph.parent == null)
275  {
276    graph.parent = this.layout.newNode("Root node");
277  }
278};
279
280LGraphManager.prototype.getLayout = function ()
281{
282  return this.layout;
283};
284
285LGraphManager.prototype.isOneAncestorOfOther = function (firstNode, secondNode)
286{
287  if (!(firstNode != null && secondNode != null)) {
288    throw "assert failed";
289  }
290
291  if (firstNode == secondNode)
292  {
293    return true;
294  }
295  // Is second node an ancestor of the first one?
296  var ownerGraph = firstNode.getOwner();
297  var parentNode;
298
299  do
300  {
301    parentNode = ownerGraph.getParent();
302
303    if (parentNode == null)
304    {
305      break;
306    }
307
308    if (parentNode == secondNode)
309    {
310      return true;
311    }
312
313    ownerGraph = parentNode.getOwner();
314    if (ownerGraph == null)
315    {
316      break;
317    }
318  } while (true);
319  // Is first node an ancestor of the second one?
320  ownerGraph = secondNode.getOwner();
321
322  do
323  {
324    parentNode = ownerGraph.getParent();
325
326    if (parentNode == null)
327    {
328      break;
329    }
330
331    if (parentNode == firstNode)
332    {
333      return true;
334    }
335
336    ownerGraph = parentNode.getOwner();
337    if (ownerGraph == null)
338    {
339      break;
340    }
341  } while (true);
342
343  return false;
344};
345
346LGraphManager.prototype.calcLowestCommonAncestors = function ()
347{
348  var edge;
349  var sourceNode;
350  var targetNode;
351  var sourceAncestorGraph;
352  var targetAncestorGraph;
353
354  var edges = this.getAllEdges();
355  var s = edges.length;
356  for (var i = 0; i < s; i++)
357  {
358    edge = edges[i];
359
360    sourceNode = edge.source;
361    targetNode = edge.target;
362    edge.lca = null;
363    edge.sourceInLca = sourceNode;
364    edge.targetInLca = targetNode;
365
366    if (sourceNode == targetNode)
367    {
368      edge.lca = sourceNode.getOwner();
369      continue;
370    }
371
372    sourceAncestorGraph = sourceNode.getOwner();
373
374    while (edge.lca == null)
375    {
376      edge.targetInLca = targetNode;  
377      targetAncestorGraph = targetNode.getOwner();
378
379      while (edge.lca == null)
380      {
381        if (targetAncestorGraph == sourceAncestorGraph)
382        {
383          edge.lca = targetAncestorGraph;
384          break;
385        }
386
387        if (targetAncestorGraph == this.rootGraph)
388        {
389          break;
390        }
391
392        if (edge.lca != null) {
393          throw "assert failed";
394        }
395        edge.targetInLca = targetAncestorGraph.getParent();
396        targetAncestorGraph = edge.targetInLca.getOwner();
397      }
398
399      if (sourceAncestorGraph == this.rootGraph)
400      {
401        break;
402      }
403
404      if (edge.lca == null)
405      {
406        edge.sourceInLca = sourceAncestorGraph.getParent();
407        sourceAncestorGraph = edge.sourceInLca.getOwner();
408      }
409    }
410
411    if (edge.lca == null) {
412      throw "assert failed";
413    }
414  }
415};
416
417LGraphManager.prototype.calcLowestCommonAncestor = function (firstNode, secondNode)
418{
419  if (firstNode == secondNode)
420  {
421    return firstNode.getOwner();
422  }
423  var firstOwnerGraph = firstNode.getOwner();
424
425  do
426  {
427    if (firstOwnerGraph == null)
428    {
429      break;
430    }
431    var secondOwnerGraph = secondNode.getOwner();
432
433    do
434    {
435      if (secondOwnerGraph == null)
436      {
437        break;
438      }
439
440      if (secondOwnerGraph == firstOwnerGraph)
441      {
442        return secondOwnerGraph;
443      }
444      secondOwnerGraph = secondOwnerGraph.getParent().getOwner();
445    } while (true);
446
447    firstOwnerGraph = firstOwnerGraph.getParent().getOwner();
448  } while (true);
449
450  return firstOwnerGraph;
451};
452
453LGraphManager.prototype.calcInclusionTreeDepths = function (graph, depth) {
454  if (graph == null && depth == null) {
455    graph = this.rootGraph;
456    depth = 1;
457  }
458  var node;
459
460  var nodes = graph.getNodes();
461  var s = nodes.length;
462  for (var i = 0; i < s; i++)
463  {
464    node = nodes[i];
465    node.inclusionTreeDepth = depth;
466
467    if (node.child != null)
468    {
469      this.calcInclusionTreeDepths(node.child, depth + 1);
470    }
471  }
472};
473
474LGraphManager.prototype.includesInvalidEdge = function ()
475{
476  var edge;
477
478  var s = this.edges.length;
479  for (var i = 0; i < s; i++)
480  {
481    edge = this.edges[i];
482
483    if (this.isOneAncestorOfOther(edge.source, edge.target))
484    {
485      return true;
486    }
487  }
488  return false;
489};
490
491module.exports = LGraphManager;
492