layouts.js 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506
  1. /**
  2. * Networkgraph series
  3. *
  4. * (c) 2010-2019 Paweł Fus
  5. *
  6. * License: www.highcharts.com/license
  7. */
  8. 'use strict';
  9. import H from '../../parts/Globals.js';
  10. var pick = H.pick;
  11. H.layouts = {
  12. 'reingold-fruchterman': function (options) {
  13. this.options = options;
  14. this.nodes = [];
  15. this.links = [];
  16. this.series = [];
  17. this.box = {
  18. x: 0,
  19. y: 0,
  20. width: 0,
  21. height: 0
  22. };
  23. this.setInitialRendering(true);
  24. }
  25. };
  26. H.extend(
  27. /**
  28. * Reingold-Fruchterman algorithm from
  29. * "Graph Drawing by Force-directed Placement" paper.
  30. */
  31. H.layouts['reingold-fruchterman'].prototype,
  32. {
  33. run: function () {
  34. var layout = this,
  35. series = this.series,
  36. options = this.options;
  37. if (layout.initialRendering) {
  38. layout.initPositions();
  39. // Render elements in initial positions:
  40. series.forEach(function (s) {
  41. s.render();
  42. });
  43. }
  44. // Algorithm:
  45. function localLayout() {
  46. // Barycenter forces:
  47. layout.applyBarycenterForces();
  48. // Repulsive forces:
  49. layout.applyRepulsiveForces();
  50. // Attractive forces:
  51. layout.applyAttractiveForces();
  52. // Limit to the plotting area and cool down:
  53. layout.applyLimits(layout.temperature);
  54. // Cool down:
  55. layout.temperature -= layout.diffTemperature;
  56. layout.prevSystemTemperature = layout.systemTemperature;
  57. layout.systemTemperature = layout.getSystemTemperature();
  58. if (options.enableSimulation) {
  59. series.forEach(function (s) {
  60. s.render();
  61. });
  62. if (
  63. layout.maxIterations-- &&
  64. !layout.isStable()
  65. ) {
  66. layout.simulation = H.win.requestAnimationFrame(
  67. localLayout
  68. );
  69. } else {
  70. layout.simulation = false;
  71. }
  72. }
  73. }
  74. layout.setK();
  75. layout.resetSimulation(options);
  76. if (options.enableSimulation) {
  77. // Animate it:
  78. layout.simulation = H.win.requestAnimationFrame(localLayout);
  79. } else {
  80. // Synchronous rendering:
  81. while (
  82. layout.maxIterations-- &&
  83. !layout.isStable()
  84. ) {
  85. localLayout();
  86. }
  87. series.forEach(function (s) {
  88. s.render();
  89. });
  90. }
  91. },
  92. stop: function () {
  93. if (this.simulation) {
  94. H.win.cancelAnimationFrame(this.simulation);
  95. }
  96. },
  97. setArea: function (x, y, w, h) {
  98. this.box = {
  99. left: x,
  100. top: y,
  101. width: w,
  102. height: h
  103. };
  104. },
  105. setK: function () {
  106. // Optimal distance between nodes,
  107. // available space around the node:
  108. this.k = this.options.linkLength ||
  109. Math.pow(
  110. this.box.width * this.box.height / this.nodes.length,
  111. 0.4
  112. );
  113. },
  114. addNodes: function (nodes) {
  115. nodes.forEach(function (node) {
  116. if (this.nodes.indexOf(node) === -1) {
  117. this.nodes.push(node);
  118. }
  119. }, this);
  120. },
  121. removeNode: function (node) {
  122. var index = this.nodes.indexOf(node);
  123. if (index !== -1) {
  124. this.nodes.splice(index, 1);
  125. }
  126. },
  127. removeLink: function (link) {
  128. var index = this.links.indexOf(link);
  129. if (index !== -1) {
  130. this.links.splice(index, 1);
  131. }
  132. },
  133. addLinks: function (links) {
  134. links.forEach(function (link) {
  135. if (this.links.indexOf(link) === -1) {
  136. this.links.push(link);
  137. }
  138. }, this);
  139. },
  140. addSeries: function (series) {
  141. if (this.series.indexOf(series) === -1) {
  142. this.series.push(series);
  143. }
  144. },
  145. clear: function () {
  146. this.nodes.length = 0;
  147. this.links.length = 0;
  148. this.series.length = 0;
  149. this.resetSimulation();
  150. },
  151. resetSimulation: function () {
  152. this.forcedStop = false;
  153. this.systemTemperature = 0;
  154. this.setMaxIterations();
  155. this.setTemperature();
  156. this.setDiffTemperature();
  157. },
  158. setMaxIterations: function (maxIterations) {
  159. this.maxIterations = pick(
  160. maxIterations,
  161. this.options.maxIterations
  162. );
  163. },
  164. setTemperature: function () {
  165. this.temperature = Math.sqrt(this.nodes.length);
  166. },
  167. setDiffTemperature: function () {
  168. this.diffTemperature = this.temperature /
  169. (this.options.maxIterations + 1);
  170. },
  171. setInitialRendering: function (enable) {
  172. this.initialRendering = enable;
  173. },
  174. initPositions: function () {
  175. var initialPositions = this.options.initialPositions;
  176. if (H.isFunction(initialPositions)) {
  177. initialPositions.call(this);
  178. } else if (initialPositions === 'circle') {
  179. this.setCircularPositions();
  180. } else {
  181. this.setRandomPositions();
  182. }
  183. },
  184. setCircularPositions: function () {
  185. var box = this.box,
  186. nodes = this.nodes,
  187. nodesLength = nodes.length + 1,
  188. angle = 2 * Math.PI / nodesLength,
  189. rootNodes = nodes.filter(function (node) {
  190. return node.linksTo.length === 0;
  191. }),
  192. sortedNodes = [],
  193. visitedNodes = {};
  194. function addToNodes(node) {
  195. node.linksFrom.forEach(function (link) {
  196. if (!visitedNodes[link.toNode.id]) {
  197. visitedNodes[link.toNode.id] = true;
  198. sortedNodes.push(link.toNode);
  199. addToNodes(link.toNode);
  200. }
  201. });
  202. }
  203. // Start with identified root nodes an sort the nodes by their
  204. // hierarchy. In trees, this ensures that branches don't cross
  205. // eachother.
  206. rootNodes.forEach(function (rootNode) {
  207. sortedNodes.push(rootNode);
  208. addToNodes(rootNode);
  209. });
  210. // Cyclic tree, no root node found
  211. if (!sortedNodes.length) {
  212. sortedNodes = nodes;
  213. // Dangling, cyclic trees
  214. } else {
  215. nodes.forEach(function (node) {
  216. if (sortedNodes.indexOf(node) === -1) {
  217. sortedNodes.push(node);
  218. }
  219. });
  220. }
  221. // Initial positions are laid out along a small circle, appearing
  222. // as a cluster in the middle
  223. sortedNodes.forEach(function (node, index) {
  224. node.plotX = pick(
  225. node.plotX,
  226. box.width / 2 + Math.cos(index * angle)
  227. );
  228. node.plotY = pick(
  229. node.plotY,
  230. box.height / 2 + Math.sin(index * angle)
  231. );
  232. node.dispX = 0;
  233. node.dispY = 0;
  234. });
  235. },
  236. setRandomPositions: function () {
  237. var box = this.box,
  238. nodes = this.nodes,
  239. nodesLength = nodes.length + 1;
  240. // Return a repeatable, quasi-random number based on an integer
  241. // input. For the initial positions
  242. function unrandom(n) {
  243. var rand = n * n / Math.PI;
  244. rand = rand - Math.floor(rand);
  245. return rand;
  246. }
  247. // Initial positions:
  248. nodes.forEach(
  249. function (node, index) {
  250. node.plotX = pick(
  251. node.plotX,
  252. box.width * unrandom(index)
  253. );
  254. node.plotY = pick(
  255. node.plotY,
  256. box.height * unrandom(nodesLength + index)
  257. );
  258. node.dispX = 0;
  259. node.dispY = 0;
  260. }
  261. );
  262. },
  263. applyBarycenterForces: function () {
  264. var nodesLength = this.nodes.length,
  265. gravitationalConstant = this.options.gravitationalConstant,
  266. cx = 0,
  267. cy = 0;
  268. // Calculate center:
  269. this.nodes.forEach(function (node) {
  270. cx += node.plotX;
  271. cy += node.plotY;
  272. });
  273. this.barycenter = {
  274. x: cx,
  275. y: cy
  276. };
  277. // Apply forces:
  278. this.nodes.forEach(function (node) {
  279. var degree = node.getDegree(),
  280. phi = degree * (1 + degree / 2);
  281. node.dispX = (cx / nodesLength - node.plotX) *
  282. gravitationalConstant * phi;
  283. node.dispY = (cy / nodesLength - node.plotY) *
  284. gravitationalConstant * phi;
  285. });
  286. },
  287. applyRepulsiveForces: function () {
  288. var layout = this,
  289. nodes = layout.nodes,
  290. options = layout.options,
  291. k = this.k;
  292. nodes.forEach(function (node) {
  293. nodes.forEach(function (repNode) {
  294. var force,
  295. distanceR,
  296. distanceXY;
  297. if (
  298. // Node can not repulse itself:
  299. node !== repNode &&
  300. // Only close nodes affect each other:
  301. /* layout.getDistR(node, repNode) < 2 * k && */
  302. // Not dragged:
  303. !node.fixedPosition
  304. ) {
  305. distanceXY = layout.getDistXY(node, repNode);
  306. distanceR = layout.vectorLength(distanceXY);
  307. if (distanceR !== 0) {
  308. force = options.repulsiveForce.call(
  309. layout, distanceR, k
  310. );
  311. node.dispX += (distanceXY.x / distanceR) * force;
  312. node.dispY += (distanceXY.y / distanceR) * force;
  313. }
  314. }
  315. });
  316. });
  317. },
  318. applyAttractiveForces: function () {
  319. var layout = this,
  320. links = layout.links,
  321. options = this.options,
  322. k = this.k;
  323. links.forEach(function (link) {
  324. if (link.fromNode && link.toNode) {
  325. var distanceXY = layout.getDistXY(
  326. link.fromNode,
  327. link.toNode
  328. ),
  329. distanceR = layout.vectorLength(distanceXY),
  330. force = options.attractiveForce.call(
  331. layout, distanceR, k
  332. );
  333. if (distanceR !== 0) {
  334. if (!link.fromNode.fixedPosition) {
  335. link.fromNode.dispX -= (distanceXY.x / distanceR) *
  336. force;
  337. link.fromNode.dispY -= (distanceXY.y / distanceR) *
  338. force;
  339. }
  340. if (!link.toNode.fixedPosition) {
  341. link.toNode.dispX += (distanceXY.x / distanceR) *
  342. force;
  343. link.toNode.dispY += (distanceXY.y / distanceR) *
  344. force;
  345. }
  346. }
  347. }
  348. });
  349. },
  350. applyLimits: function (temperature) {
  351. var layout = this,
  352. options = layout.options,
  353. nodes = layout.nodes,
  354. box = layout.box,
  355. distanceR;
  356. nodes.forEach(function (node) {
  357. if (node.fixedPosition) {
  358. return;
  359. }
  360. // Friction:
  361. node.dispX += options.friction * node.dispX;
  362. node.dispY += options.friction * node.dispY;
  363. distanceR = node.temperature = layout.vectorLength({
  364. x: node.dispX,
  365. y: node.dispY
  366. });
  367. // Place nodes:
  368. if (distanceR !== 0) {
  369. node.plotX += node.dispX / distanceR *
  370. Math.min(Math.abs(node.dispX), temperature);
  371. node.plotY += node.dispY / distanceR *
  372. Math.min(Math.abs(node.dispY), temperature);
  373. }
  374. /*
  375. TO DO: Consider elastic collision instead of stopping.
  376. o' means end position when hitting plotting area edge:
  377. - "inealstic":
  378. o
  379. \
  380. ______
  381. | o'
  382. | \
  383. | \
  384. - "elastic"/"bounced":
  385. o
  386. \
  387. ______
  388. | ^
  389. | / \
  390. |o' \
  391. */
  392. // Limit X-coordinates:
  393. node.plotX = Math.round(
  394. Math.max(
  395. Math.min(
  396. node.plotX,
  397. box.width
  398. ),
  399. box.left
  400. )
  401. );
  402. // Limit Y-coordinates:
  403. node.plotY = Math.round(
  404. Math.max(
  405. Math.min(
  406. node.plotY,
  407. box.height
  408. ),
  409. box.top
  410. )
  411. );
  412. // Reset displacement:
  413. node.dispX = 0;
  414. node.dispY = 0;
  415. });
  416. },
  417. isStable: function () {
  418. return Math.abs(
  419. this.systemTemperature -
  420. this.prevSystemTemperature
  421. ) === 0;
  422. },
  423. getSystemTemperature: function () {
  424. return this.nodes.reduce(function (value, node) {
  425. return value + node.temperature;
  426. }, 0);
  427. },
  428. vectorLength: function (vector) {
  429. return Math.sqrt(vector.x * vector.x + vector.y * vector.y);
  430. },
  431. getDistR: function (nodeA, nodeB) {
  432. var distance = this.getDistXY(nodeA, nodeB);
  433. return Math.sqrt(
  434. distance.x * distance.x +
  435. distance.y * distance.y
  436. );
  437. },
  438. getDistXY: function (nodeA, nodeB) {
  439. var xDist = nodeA.plotX - nodeB.plotX,
  440. yDist = nodeA.plotY - nodeB.plotY;
  441. return {
  442. x: xDist,
  443. y: yDist,
  444. absX: Math.abs(xDist),
  445. absY: Math.abs(yDist)
  446. };
  447. }
  448. }
  449. );