vis.js is a dynamic, browser-based visualization library
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

705 lines
24 KiB

9 years ago
9 years ago
  1. let util = require("../../util");
  2. import Cluster from './components/nodes/Cluster'
  3. class ClusterEngine {
  4. constructor(body) {
  5. this.body = body;
  6. this.clusteredNodes = {};
  7. this.options = {};
  8. this.defaultOptions = {};
  9. util.extend(this.options, this.defaultOptions);
  10. this.body.emitter.on('_resetData', () => {this.clusteredNodes = {};})
  11. }
  12. setOptions(options) {
  13. if (options !== undefined) {
  14. }
  15. }
  16. /**
  17. *
  18. * @param hubsize
  19. * @param options
  20. */
  21. clusterByHubsize(hubsize, options) {
  22. if (hubsize === undefined) {
  23. hubsize = this._getHubSize();
  24. }
  25. else if (typeof(hubsize) === "object") {
  26. options = this._checkOptions(hubsize);
  27. hubsize = this._getHubSize();
  28. }
  29. let nodesToCluster = [];
  30. for (let i = 0; i < this.body.nodeIndices.length; i++) {
  31. let node = this.body.nodes[this.body.nodeIndices[i]];
  32. if (node.edges.length >= hubsize) {
  33. nodesToCluster.push(node.id);
  34. }
  35. }
  36. for (let i = 0; i < nodesToCluster.length; i++) {
  37. this.clusterByConnection(nodesToCluster[i],options,false);
  38. }
  39. this.body.emitter.emit('_dataChanged');
  40. }
  41. /**
  42. * loop over all nodes, check if they adhere to the condition and cluster if needed.
  43. * @param options
  44. * @param refreshData
  45. */
  46. cluster(options = {}, refreshData = true) {
  47. if (options.joinCondition === undefined) {throw new Error("Cannot call clusterByNodeData without a joinCondition function in the options.");}
  48. // check if the options object is fine, append if needed
  49. options = this._checkOptions(options);
  50. let childNodesObj = {};
  51. let childEdgesObj = {};
  52. // collect the nodes that will be in the cluster
  53. for (let i = 0; i < this.body.nodeIndices.length; i++) {
  54. let nodeId = this.body.nodeIndices[i];
  55. let node = this.body.nodes[nodeId];
  56. let clonedOptions = this._cloneOptions(node);
  57. if (options.joinCondition(clonedOptions) === true) {
  58. childNodesObj[nodeId] = this.body.nodes[nodeId];
  59. // collect the nodes that will be in the cluster
  60. for (let i = 0; i < node.edges.length; i++) {
  61. let edge = node.edges[i];
  62. childEdgesObj[edge.id] = edge;
  63. }
  64. }
  65. }
  66. this._cluster(childNodesObj, childEdgesObj, options, refreshData);
  67. }
  68. /**
  69. * Cluster all nodes in the network that have only 1 edge
  70. * @param options
  71. * @param refreshData
  72. */
  73. clusterOutliers(options, refreshData = true) {
  74. options = this._checkOptions(options);
  75. let clusters = [];
  76. // collect the nodes that will be in the cluster
  77. for (let i = 0; i < this.body.nodeIndices.length; i++) {
  78. let childNodesObj = {};
  79. let childEdgesObj = {};
  80. let nodeId = this.body.nodeIndices[i];
  81. let visibleEdges = 0;
  82. let edge;
  83. for (let j = 0; j < this.body.nodes[nodeId].edges.length; j++) {
  84. if (this.body.nodes[nodeId].edges[j].options.hidden === false) {
  85. visibleEdges++;
  86. edge = this.body.nodes[nodeId].edges[j];
  87. }
  88. }
  89. if (visibleEdges === 1) {
  90. // this is an outlier
  91. let childNodeId = this._getConnectedId(edge, nodeId);
  92. if (childNodeId !== nodeId) {
  93. if (options.joinCondition === undefined) {
  94. if (this._checkIfUsed(clusters,nodeId,edge.id) === false && this._checkIfUsed(clusters,childNodeId,edge.id) === false) {
  95. childEdgesObj[edge.id] = edge;
  96. childNodesObj[nodeId] = this.body.nodes[nodeId];
  97. childNodesObj[childNodeId] = this.body.nodes[childNodeId];
  98. }
  99. }
  100. else {
  101. let clonedOptions = this._cloneOptions(this.body.nodes[nodeId]);
  102. if (options.joinCondition(clonedOptions) === true && this._checkIfUsed(clusters,nodeId,edge.id) === false) {
  103. childEdgesObj[edge.id] = edge;
  104. childNodesObj[nodeId] = this.body.nodes[nodeId];
  105. }
  106. clonedOptions = this._cloneOptions(this.body.nodes[childNodeId]);
  107. if (options.joinCondition(clonedOptions) === true && this._checkIfUsed(clusters,nodeId,edge.id) === false) {
  108. childEdgesObj[edge.id] = edge;
  109. childNodesObj[childNodeId] = this.body.nodes[childNodeId];
  110. }
  111. }
  112. if (Object.keys(childNodesObj).length > 0 && Object.keys(childEdgesObj).length > 0) {
  113. clusters.push({nodes: childNodesObj, edges: childEdgesObj})
  114. }
  115. }
  116. }
  117. }
  118. for (let i = 0; i < clusters.length; i++) {
  119. this._cluster(clusters[i].nodes, clusters[i].edges, options, false)
  120. }
  121. if (refreshData === true) {
  122. this.body.emitter.emit('_dataChanged');
  123. }
  124. }
  125. _checkIfUsed(clusters, nodeId, edgeId) {
  126. for (let i = 0; i < clusters.length; i++) {
  127. let cluster = clusters[i];
  128. if (cluster.nodes[nodeId] !== undefined || cluster.edges[edgeId] !== undefined) {
  129. return true;
  130. }
  131. }
  132. return false;
  133. }
  134. /**
  135. * suck all connected nodes of a node into the node.
  136. * @param nodeId
  137. * @param options
  138. * @param refreshData
  139. */
  140. clusterByConnection(nodeId, options, refreshData = true) {
  141. // kill conditions
  142. if (nodeId === undefined) {throw new Error("No nodeId supplied to clusterByConnection!");}
  143. if (this.body.nodes[nodeId] === undefined) {throw new Error("The nodeId given to clusterByConnection does not exist!");}
  144. let node = this.body.nodes[nodeId];
  145. options = this._checkOptions(options, node);
  146. if (options.clusterNodeProperties.x === undefined) {options.clusterNodeProperties.x = node.x;}
  147. if (options.clusterNodeProperties.y === undefined) {options.clusterNodeProperties.y = node.y;}
  148. if (options.clusterNodeProperties.fixed === undefined) {
  149. options.clusterNodeProperties.fixed = {};
  150. options.clusterNodeProperties.fixed.x = node.options.fixed.x;
  151. options.clusterNodeProperties.fixed.y = node.options.fixed.y;
  152. }
  153. let childNodesObj = {};
  154. let childEdgesObj = {};
  155. let parentNodeId = node.id;
  156. let parentClonedOptions = this._cloneOptions(node);
  157. childNodesObj[parentNodeId] = node;
  158. // collect the nodes that will be in the cluster
  159. for (let i = 0; i < node.edges.length; i++) {
  160. let edge = node.edges[i];
  161. let childNodeId = this._getConnectedId(edge, parentNodeId);
  162. if (childNodeId !== parentNodeId) {
  163. if (options.joinCondition === undefined) {
  164. childEdgesObj[edge.id] = edge;
  165. childNodesObj[childNodeId] = this.body.nodes[childNodeId];
  166. }
  167. else {
  168. // clone the options and insert some additional parameters that could be interesting.
  169. let childClonedOptions = this._cloneOptions(this.body.nodes[childNodeId]);
  170. if (options.joinCondition(parentClonedOptions, childClonedOptions) === true) {
  171. childEdgesObj[edge.id] = edge;
  172. childNodesObj[childNodeId] = this.body.nodes[childNodeId];
  173. }
  174. }
  175. }
  176. else {
  177. childEdgesObj[edge.id] = edge;
  178. }
  179. }
  180. this._cluster(childNodesObj, childEdgesObj, options, refreshData);
  181. }
  182. /**
  183. * This returns a clone of the options or options of the edge or node to be used for construction of new edges or check functions for new nodes.
  184. * @param objId
  185. * @param type
  186. * @returns {{}}
  187. * @private
  188. */
  189. _cloneOptions(item, type) {
  190. let clonedOptions = {};
  191. if (type === undefined || type === 'node') {
  192. util.deepExtend(clonedOptions, item.options, true);
  193. clonedOptions.x = item.x;
  194. clonedOptions.y = item.y;
  195. clonedOptions.amountOfConnections = item.edges.length;
  196. }
  197. else {
  198. util.deepExtend(clonedOptions, item.options, true);
  199. }
  200. return clonedOptions;
  201. }
  202. /**
  203. * This function creates the edges that will be attached to the cluster.
  204. *
  205. * @param childNodesObj
  206. * @param childEdgesObj
  207. * @param newEdges
  208. * @param options
  209. * @private
  210. */
  211. _createClusterEdges (childNodesObj, childEdgesObj, newEdges, clusterNodeProperties, clusterEdgeProperties) {
  212. let edge, childNodeId, childNode, toId, fromId, otherNodeId;
  213. let childKeys = Object.keys(childNodesObj);
  214. for (let i = 0; i < childKeys.length; i++) {
  215. childNodeId = childKeys[i];
  216. childNode = childNodesObj[childNodeId];
  217. // construct new edges from the cluster to others
  218. for (let j = 0; j < childNode.edges.length; j++) {
  219. edge = childNode.edges[j];
  220. childEdgesObj[edge.id] = edge;
  221. // childNodeId position will be replaced by the cluster.
  222. if (edge.toId == childNodeId) { // this is a double equals because ints and strings can be interchanged here.
  223. toId = clusterNodeProperties.id;
  224. fromId = edge.fromId;
  225. otherNodeId = fromId;
  226. }
  227. else {
  228. toId = edge.toId;
  229. fromId = clusterNodeProperties.id;
  230. otherNodeId = toId;
  231. }
  232. // if the node connected to the cluster is also in the cluster we do not need a new edge.
  233. if (childNodesObj[otherNodeId] === undefined) {
  234. let clonedOptions = this._cloneOptions(edge, 'edge');
  235. util.deepExtend(clonedOptions, clusterEdgeProperties);
  236. clonedOptions.from = fromId;
  237. clonedOptions.to = toId;
  238. clonedOptions.id = 'clusterEdge:' + util.randomUUID();
  239. newEdges.push(this.body.functions.createEdge(clonedOptions));
  240. }
  241. }
  242. }
  243. }
  244. /**
  245. * This function checks the options that can be supplied to the different cluster functions
  246. * for certain fields and inserts defaults if needed
  247. * @param options
  248. * @returns {*}
  249. * @private
  250. */
  251. _checkOptions(options = {}) {
  252. if (options.clusterEdgeProperties === undefined) {options.clusterEdgeProperties = {};}
  253. if (options.clusterNodeProperties === undefined) {options.clusterNodeProperties = {};}
  254. return options;
  255. }
  256. /**
  257. *
  258. * @param {Object} childNodesObj | object with node objects, id as keys, same as childNodes except it also contains a source node
  259. * @param {Object} childEdgesObj | object with edge objects, id as keys
  260. * @param {Array} options | object with {clusterNodeProperties, clusterEdgeProperties, processProperties}
  261. * @param {Boolean} refreshData | when true, do not wrap up
  262. * @private
  263. */
  264. _cluster(childNodesObj, childEdgesObj, options, refreshData = true) {
  265. // kill condition: no children so cant cluster
  266. if (Object.keys(childNodesObj).length === 0) {return;}
  267. let clusterNodeProperties = util.deepExtend({},options.clusterNodeProperties);
  268. // construct the clusterNodeProperties
  269. if (options.processProperties !== undefined) {
  270. // get the childNode options
  271. let childNodesOptions = [];
  272. for (let nodeId in childNodesObj) {
  273. let clonedOptions = this._cloneOptions(childNodesObj[nodeId]);
  274. childNodesOptions.push(clonedOptions);
  275. }
  276. // get clusterproperties based on childNodes
  277. let childEdgesOptions = [];
  278. for (let edgeId in childEdgesObj) {
  279. // these cluster edges will be removed on creation of the cluster.
  280. if (edgeId.substr(0,12) !== "clusterEdge:") {
  281. let clonedOptions = this._cloneOptions(childEdgesObj[edgeId], 'edge');
  282. childEdgesOptions.push(clonedOptions);
  283. }
  284. }
  285. clusterNodeProperties = options.processProperties(clusterNodeProperties, childNodesOptions, childEdgesOptions);
  286. if (!clusterNodeProperties) {
  287. throw new Error("The processProperties function does not return properties!");
  288. }
  289. }
  290. // check if we have an unique id;
  291. if (clusterNodeProperties.id === undefined) {clusterNodeProperties.id = 'cluster:' + util.randomUUID();}
  292. let clusterId = clusterNodeProperties.id;
  293. if (clusterNodeProperties.label === undefined) {
  294. clusterNodeProperties.label = 'cluster';
  295. }
  296. // give the clusterNode a postion if it does not have one.
  297. let pos = undefined;
  298. if (clusterNodeProperties.x === undefined) {
  299. pos = this._getClusterPosition(childNodesObj);
  300. clusterNodeProperties.x = pos.x;
  301. }
  302. if (clusterNodeProperties.y === undefined) {
  303. if (pos === undefined) {
  304. pos = this._getClusterPosition(childNodesObj);
  305. }
  306. clusterNodeProperties.y = pos.y;
  307. }
  308. // force the ID to remain the same
  309. clusterNodeProperties.id = clusterId;
  310. // create the clusterNode
  311. let clusterNode = this.body.functions.createNode(clusterNodeProperties, Cluster);
  312. clusterNode.isCluster = true;
  313. clusterNode.containedNodes = childNodesObj;
  314. clusterNode.containedEdges = childEdgesObj;
  315. // cache a copy from the cluster edge properties if we have to reconnect others later on
  316. clusterNode.clusterEdgeProperties = options.clusterEdgeProperties;
  317. // finally put the cluster node into global
  318. this.body.nodes[clusterNodeProperties.id] = clusterNode;
  319. // create the new edges that will connect to the cluster
  320. let newEdges = [];
  321. this._createClusterEdges(childNodesObj, childEdgesObj, newEdges, clusterNodeProperties, options.clusterEdgeProperties);
  322. // disable the childEdges
  323. for (let edgeId in childEdgesObj) {
  324. if (childEdgesObj.hasOwnProperty(edgeId)) {
  325. if (this.body.edges[edgeId] !== undefined) {
  326. let edge = this.body.edges[edgeId];
  327. // if this is a cluster edge that is fully encompassed in the cluster, we want to delete it
  328. // this check verifies that both of the connected nodes are in this cluster
  329. if (edgeId.substr(0,12) === "clusterEdge:" && childNodesObj[edge.fromId] !== undefined && childNodesObj[edge.toId] !== undefined) {
  330. edge.cleanup();
  331. // this removes the edge from node.edges, which is why edgeIds is formed
  332. edge.disconnect();
  333. delete childEdgesObj[edgeId];
  334. delete this.body.edges[edgeId];
  335. }
  336. else {
  337. edge.setOptions({physics:false, hidden:true});
  338. //edge.options.hidden = true;
  339. }
  340. }
  341. }
  342. }
  343. // disable the childNodes
  344. for (let nodeId in childNodesObj) {
  345. if (childNodesObj.hasOwnProperty(nodeId)) {
  346. this.clusteredNodes[nodeId] = {clusterId:clusterNodeProperties.id, node: this.body.nodes[nodeId]};
  347. this.body.nodes[nodeId].setOptions({hidden:true, physics:false});
  348. }
  349. }
  350. // push new edges to global
  351. for (let i = 0; i < newEdges.length; i++) {
  352. this.body.edges[newEdges[i].id] = newEdges[i];
  353. this.body.edges[newEdges[i].id].connect();
  354. }
  355. // set ID to undefined so no duplicates arise
  356. clusterNodeProperties.id = undefined;
  357. // wrap up
  358. if (refreshData === true) {
  359. this.body.emitter.emit('_dataChanged');
  360. }
  361. }
  362. /**
  363. * Check if a node is a cluster.
  364. * @param nodeId
  365. * @returns {*}
  366. */
  367. isCluster(nodeId) {
  368. if (this.body.nodes[nodeId] !== undefined) {
  369. return this.body.nodes[nodeId].isCluster === true;
  370. }
  371. else {
  372. console.log("Node does not exist.");
  373. return false;
  374. }
  375. }
  376. /**
  377. * get the position of the cluster node based on what's inside
  378. * @param {object} childNodesObj | object with node objects, id as keys
  379. * @returns {{x: number, y: number}}
  380. * @private
  381. */
  382. _getClusterPosition(childNodesObj) {
  383. let childKeys = Object.keys(childNodesObj);
  384. let minX = childNodesObj[childKeys[0]].x;
  385. let maxX = childNodesObj[childKeys[0]].x;
  386. let minY = childNodesObj[childKeys[0]].y;
  387. let maxY = childNodesObj[childKeys[0]].y;
  388. let node;
  389. for (let i = 1; i < childKeys.length; i++) {
  390. node = childNodesObj[childKeys[i]];
  391. minX = node.x < minX ? node.x : minX;
  392. maxX = node.x > maxX ? node.x : maxX;
  393. minY = node.y < minY ? node.y : minY;
  394. maxY = node.y > maxY ? node.y : maxY;
  395. }
  396. return {x: 0.5*(minX + maxX), y: 0.5*(minY + maxY)};
  397. }
  398. /**
  399. * Open a cluster by calling this function.
  400. * @param {String} clusterNodeId | the ID of the cluster node
  401. * @param {Boolean} refreshData | wrap up afterwards if not true
  402. */
  403. openCluster(clusterNodeId, options, refreshData = true) {
  404. // kill conditions
  405. if (clusterNodeId === undefined) {throw new Error("No clusterNodeId supplied to openCluster.");}
  406. if (this.body.nodes[clusterNodeId] === undefined) {throw new Error("The clusterNodeId supplied to openCluster does not exist.");}
  407. if (this.body.nodes[clusterNodeId].containedNodes === undefined) {
  408. console.log("The node:" + clusterNodeId + " is not a cluster.");
  409. return
  410. }
  411. let clusterNode = this.body.nodes[clusterNodeId];
  412. let containedNodes = clusterNode.containedNodes;
  413. let containedEdges = clusterNode.containedEdges;
  414. // allow the user to position the nodes after release.
  415. if (options !== undefined && options.releaseFunction !== undefined && typeof options.releaseFunction === 'function') {
  416. let positions = {};
  417. let clusterPosition = {x:clusterNode.x, y:clusterNode.y};
  418. for (let nodeId in containedNodes) {
  419. if (containedNodes.hasOwnProperty(nodeId)) {
  420. let containedNode = this.body.nodes[nodeId];
  421. positions[nodeId] = {x: containedNode.x, y: containedNode.y};
  422. }
  423. }
  424. let newPositions = options.releaseFunction(clusterPosition, positions);
  425. for (let nodeId in containedNodes) {
  426. if (containedNodes.hasOwnProperty(nodeId)) {
  427. let containedNode = this.body.nodes[nodeId];
  428. if (newPositions[nodeId] !== undefined) {
  429. containedNode.x = newPositions[nodeId].x || clusterNode.x;
  430. containedNode.y = newPositions[nodeId].y || clusterNode.y;
  431. }
  432. }
  433. }
  434. }
  435. else {
  436. // copy the position from the cluster
  437. for (let nodeId in containedNodes) {
  438. if (containedNodes.hasOwnProperty(nodeId)) {
  439. let containedNode = this.body.nodes[nodeId];
  440. containedNode = containedNodes[nodeId];
  441. // inherit position
  442. containedNode.x = clusterNode.x;
  443. containedNode.y = clusterNode.y;
  444. }
  445. }
  446. }
  447. // release nodes
  448. for (let nodeId in containedNodes) {
  449. if (containedNodes.hasOwnProperty(nodeId)) {
  450. let containedNode = this.body.nodes[nodeId];
  451. // inherit speed
  452. containedNode.vx = clusterNode.vx;
  453. containedNode.vy = clusterNode.vy;
  454. // we use these methods to avoid reinstantiating the shape, which happens with setOptions.
  455. //containedNode.toggleHidden(false);
  456. //containedNode.togglePhysics(true);
  457. containedNode.setOptions({hidden:false, physics:true});
  458. delete this.clusteredNodes[nodeId];
  459. }
  460. }
  461. // release edges
  462. for (let edgeId in containedEdges) {
  463. if (containedEdges.hasOwnProperty(edgeId)) {
  464. let edge = containedEdges[edgeId];
  465. // if this edge was a temporary edge and it's connected nodes do not exist anymore, we remove it from the data
  466. if (this.body.nodes[edge.fromId] === undefined || this.body.nodes[edge.toId] === undefined || edge.toId == clusterNodeId || edge.fromId == clusterNodeId) {
  467. edge.cleanup();
  468. // this removes the edge from node.edges, which is why edgeIds is formed
  469. edge.disconnect();
  470. delete this.body.edges[edgeId];
  471. }
  472. else {
  473. // one of the nodes connected to this edge is in a cluster. We give the edge to that cluster so it will be released when that cluster is opened.
  474. if (this.clusteredNodes[edge.fromId] !== undefined || this.clusteredNodes[edge.toId] !== undefined) {
  475. let fromId, toId;
  476. let clusteredNode = this.clusteredNodes[edge.fromId] || this.clusteredNodes[edge.toId];
  477. let clusterId = clusteredNode.clusterId;
  478. let clusterNode = this.body.nodes[clusterId];
  479. clusterNode.containedEdges[edgeId] = edge;
  480. if (this.clusteredNodes[edge.fromId] !== undefined) {
  481. fromId = clusterId;
  482. toId = edge.toId;
  483. }
  484. else {
  485. fromId = edge.fromId;
  486. toId = clusterId;
  487. }
  488. // if both from and to nodes are visible, we create a new temporary edge
  489. if (this.body.nodes[fromId].options.hidden !== true && this.body.nodes[toId].options.hidden !== true) {
  490. let clonedOptions = this._cloneOptions(edge, 'edge');
  491. let id = 'clusterEdge:' + util.randomUUID();
  492. util.deepExtend(clonedOptions, clusterNode.clusterEdgeProperties);
  493. util.deepExtend(clonedOptions, {from: fromId, to: toId, hidden: false, physics: true, id: id});
  494. let newEdge = this.body.functions.createEdge(clonedOptions);
  495. this.body.edges[id] = newEdge;
  496. this.body.edges[id].connect();
  497. }
  498. }
  499. else {
  500. edge.setOptions({physics:true, hidden:false});
  501. //edge.options.hidden = false;
  502. //edge.togglePhysics(true);
  503. }
  504. }
  505. }
  506. }
  507. // remove all temporary edges, make an array of ids so we don't remove from the list we're iterating over.
  508. let removeIds = [];
  509. for (let i = 0; i < clusterNode.edges.length; i++) {
  510. let edgeId = clusterNode.edges[i].id;
  511. removeIds.push(edgeId);
  512. }
  513. // actually removing the edges
  514. for (let i = 0; i < removeIds.length; i++) {
  515. let edgeId = removeIds[i];
  516. this.body.edges[edgeId].cleanup();
  517. // this removes the edge from node.edges, which is why edgeIds is formed
  518. this.body.edges[edgeId].disconnect();
  519. delete this.body.edges[edgeId];
  520. }
  521. // remove clusterNode
  522. this.body.nodes[clusterNodeId].cleanup();
  523. delete this.body.nodes[clusterNodeId];
  524. if (refreshData === true) {
  525. this.body.emitter.emit('_dataChanged');
  526. }
  527. }
  528. getNodesInCluster(clusterId) {
  529. let nodesArray = []
  530. if (this.isCluster(clusterId) === true) {
  531. let containedNodes = this.body.nodes[clusterId].containedNodes;
  532. for (let nodeId in containedNodes) {
  533. if (containedNodes.hasOwnProperty(nodeId)) {
  534. nodesArray.push(nodeId)
  535. }
  536. }
  537. }
  538. return nodesArray;
  539. }
  540. /**
  541. * Get the stack clusterId's that a certain node resides in. cluster A -> cluster B -> cluster C -> node
  542. * @param nodeId
  543. * @returns {Array}
  544. * @private
  545. */
  546. findNode(nodeId) {
  547. let stack = [];
  548. let max = 100;
  549. let counter = 0;
  550. while (this.clusteredNodes[nodeId] !== undefined && counter < max) {
  551. stack.push(this.clusteredNodes[nodeId].node);
  552. nodeId = this.clusteredNodes[nodeId].clusterId;
  553. counter++;
  554. }
  555. stack.push(this.body.nodes[nodeId]);
  556. return stack;
  557. }
  558. /**
  559. * Get the Id the node is connected to
  560. * @param edge
  561. * @param nodeId
  562. * @returns {*}
  563. * @private
  564. */
  565. _getConnectedId(edge, nodeId) {
  566. if (edge.toId != nodeId) {
  567. return edge.toId;
  568. }
  569. else if (edge.fromId != nodeId) {
  570. return edge.fromId;
  571. }
  572. else {
  573. return edge.fromId;
  574. }
  575. }
  576. /**
  577. * We determine how many connections denote an important hub.
  578. * We take the mean + 2*std as the important hub size. (Assuming a normal distribution of data, ~2.2%)
  579. *
  580. * @private
  581. */
  582. _getHubSize() {
  583. let average = 0;
  584. let averageSquared = 0;
  585. let hubCounter = 0;
  586. let largestHub = 0;
  587. for (let i = 0; i < this.body.nodeIndices.length; i++) {
  588. let node = this.body.nodes[this.body.nodeIndices[i]];
  589. if (node.edges.length > largestHub) {
  590. largestHub = node.edges.length;
  591. }
  592. average += node.edges.length;
  593. averageSquared += Math.pow(node.edges.length,2);
  594. hubCounter += 1;
  595. }
  596. average = average / hubCounter;
  597. averageSquared = averageSquared / hubCounter;
  598. let variance = averageSquared - Math.pow(average,2);
  599. let standardDeviation = Math.sqrt(variance);
  600. let hubThreshold = Math.floor(average + 2*standardDeviation);
  601. // always have at least one to cluster
  602. if (hubThreshold > largestHub) {
  603. hubThreshold = largestHub;
  604. }
  605. return hubThreshold;
  606. };
  607. }
  608. export default ClusterEngine;