2b:null 2c:["$","title",null,{"children":"Force-Directed Graph - WebGL & Canvas with PIXI.js | Jan Žák | Observable"}] 31:T598,md`# Force-Directed Graph - WebGL & Canvas with PIXI.js Fork of original [D3 Force-Directed Graph](https://observablehq.com/@d3/force-directed-graph), with performance optimizations for large graphs: - [PIXI.js](https://github.com/pixijs/pixi.js) renderer instead of SVG - using prerendered textures where possible for best performance - PIXI.js v5 bundle includes WebGL renderer only, import from *pixi.js-legacy* for automatic fallback to Canvas renderer - multiple graphs and layouts to compare performance and quality - layout readability score computed with [Greadability.js](https://github.com/rpgove/greadability) - layout running in separate WebWorker thread, so that it doesn’t block user from interacting with UI - *warning:* layout quality can be affected by chosen layout parameters UI features: - node label - node font icon - node & link hover effect - node drag - zoom & drag viewport - levels of detail by zoom level Blog posts: - [Scale up your D3 graph visualisation – WebGL & Canvas with PIXI.js](https://medium.com/neo4j/scale-up-your-d3-graph-visualisation-webgl-canvas-with-pixi-js-63f119d96a28) - [Scale up your D3 graph visualisation, part 2 – WebWorker layout and PIXI.js rendering performance improvements](https://medium.com/neo4j/scale-up-your-d3-graph-visualisation-part-2-2726a57301ec) **The latest code is released as [pixi-graph](https://github.com/zakjan/pixi-graph) library.**`32:T448,viewof config = inputsForm([ { name: 'graph', element: select({ options: Object.entries(graphs).map(([name, graph]) => ({ value: name, label: `${name} (nodes: ${formatInt(graph.nodes.length)}, links: ${formatInt(graph.links.length)})`})), value: 'Les Misérables', title: 'Graph', }), }, { name: 'multiply', element: select({ options: [1, 2, 3, 4, 5, 6, 7, 8], value: 1, title: 'Multiply', description: 'Generate separate graph components', }), }, { name: 'hyper', element: select({ options: [0, 1, 2, 3, 4, 5, 6, 7, 8], value: 0, title: 'Hyper', description: 'Increase dimension (point -> line -> cube -> hypercube)
Warning: Layout of larger graphs takes longer to compute, start with smaller graphs first', }), }, { name: 'layout', element: select({ options: layouts, value: layouts[0], title: 'Layout', }), }, { name: 'showFpsMeter', element: checkbox({ options: [{ value: 'true', label: 'Show FPS meter' }], }), }, ]);33:T4be9,chart = { // config const SCREEN_WIDTH = width; const SCREEN_HEIGHT = height; const RESOLUTION = window.devicePixelRatio; const NODE_RADIUS = 15; const NODE_BORDER_WIDTH = 2; const NODE_BORDER_COLOR = 0xffffff; const NODE_BORDER_RADIUS = NODE_RADIUS + NODE_BORDER_WIDTH; const NODE_HIT_WIDTH = 5; const NODE_HIT_RADIUS = NODE_RADIUS + NODE_HIT_WIDTH; const NODE_HOVER_BORDER_COLOR = 0x000000; const ICON_FONT_FAMILY = 'Material Icons'; const ICON_FONT_SIZE = NODE_RADIUS / Math.SQRT2 * 2; const ICON_COLOR = 0xffffff; const ICON_TEXT = nodeData => typeof nodeData.id === 'number' || typeof nodeData.id === 'string' && (!isNaN(parseInt(nodeData.id[0], 10)) || nodeData.id[0] === '(') ? 'star' : 'person'; const LABEL_FONT_FAMILY = 'HelveticaRegular'; const LABEL_FONT_SIZE = 12; const LABEL_COLOR = 0x333333; const LABEL_TEXT = nodeData => `${nodeData.id}`; const LABEL_PADDING = 4; const LABEL_BACKGROUND_COLOR = 0xffffff; const LABEL_BACKGROUND_ALPHA = 0.5; const LABEL_HOVER_BACKGROUND_COLOR = 0xeeeeee; const LABEL_HOVER_BACKGROUND_ALPHA = 1; const LINK_SIZE = linkData => Math.log((linkData.value || 1) + 1); const LINK_COLOR = 0xcccccc; const LINK_HOVER_COLOR = 0x999999; const TEXTURE_COLOR = 0xffffff; const CIRCLE = 'CIRCLE'; const CIRCLE_BORDER = 'CIRCLE_BORDER'; const ICON = 'ICON'; const LABEL = 'LABEL'; const LABEL_BACKGROUND = 'LABEL_BACKGROUND'; const LINE = 'LINE'; // compute static layout yield html`

Computing layout...

`; const { positions, layoutTime } = await runLayout(graph, config.layout); const { nodes, links } = graph; nodes.forEach(nodeData => { const position = positions[nodeData.id]; nodeData.x = position.x; nodeData.y = position.y; }); // normalize node positions yield html`

Rendering...

`; const minNodeX = Math.min(...nodes.map(nodeData => nodeData.x)); const maxNodeX = Math.max(...nodes.map(nodeData => nodeData.x)); const minNodeY = Math.min(...nodes.map(nodeData => nodeData.y)); const maxNodeY = Math.max(...nodes.map(nodeData => nodeData.y)); const graphWidth = Math.abs(maxNodeX - minNodeX); const graphHeight = Math.abs(maxNodeY - minNodeY); const WORLD_WIDTH = Math.max(SCREEN_WIDTH * 2, graphWidth * 1.1); const WORLD_HEIGHT = Math.max(SCREEN_HEIGHT * 2, graphHeight * 1.1); nodes.forEach(nodeData => { nodeData.x = nodeData.x - minNodeX - graphWidth / 2 + WORLD_WIDTH / 2; nodeData.y = nodeData.y - minNodeY - graphHeight / 2 + WORLD_HEIGHT / 2; }); // create PIXI application console.log(SCREEN_WIDTH, SCREEN_HEIGHT, WORLD_WIDTH, WORLD_HEIGHT, RESOLUTION); const app = new PIXI.Application({ width: SCREEN_WIDTH, height: SCREEN_HEIGHT, resolution: RESOLUTION, transparent: true, antialias: true, autoDensity: true, autoStart: false // disable automatic rendering by ticker, render manually instead, only when needed }); app.view.style.width = `${SCREEN_WIDTH}px`; // preload fonts await new Promise(resolve => { app.loader.add(LABEL_FONT_FAMILY, 'https://gist.githubusercontent.com/zakjan/b61c0a26d297edf0c09a066712680f37/raw/8cdda3c21ba3668c3dd022efac6d7f740c9f1e18/HelveticaRegular.fnt').load(resolve); }); await new FontFaceObserver(ICON_FONT_FAMILY).load(); // manual rendering // app.renderer.on('postrender', () => { console.log('render'); }); let renderRequestId = undefined; const requestRender = () => { if (renderRequestId) { return; } renderRequestId = window.requestAnimationFrame(() => { app.render(); renderRequestId = undefined; }); } // create PIXI viewport const viewport = new Viewport({ screenWidth: SCREEN_WIDTH, screenHeight: SCREEN_HEIGHT, worldWidth: WORLD_WIDTH, worldHeight: WORLD_HEIGHT, interaction: app.renderer.plugins.interaction }); const zoomIn = () => { viewport.zoom(-WORLD_WIDTH / 10, true); }; const zoomOut = () => { viewport.zoom(WORLD_WIDTH / 10, true); }; const resetViewport = () => { viewport.center = new PIXI.Point(WORLD_WIDTH / 2, WORLD_HEIGHT / 2); viewport.fitWorld(true); }; app.stage.addChild(viewport); viewport.drag().pinch().wheel().decelerate().clampZoom({ minWidth: SCREEN_WIDTH, minHeight: SCREEN_HEIGHT }); // create layers: links, front links, nodes, labels, front nodes, front labels const linksLayer = new PIXI.Container(); viewport.addChild(linksLayer); const frontLinksLayer = new PIXI.Container(); viewport.addChild(frontLinksLayer); const nodesLayer = new PIXI.Container(); viewport.addChild(nodesLayer); const labelsLayer = new PIXI.Container(); viewport.addChild(labelsLayer); const frontNodesLayer = new PIXI.Container(); viewport.addChild(frontNodesLayer); const frontLabelsLayer = new PIXI.Container(); viewport.addChild(frontLabelsLayer); // create textures: circle, circle border, icons const circleGraphics = new PIXI.Graphics(); circleGraphics.beginFill(TEXTURE_COLOR); circleGraphics.drawCircle(NODE_RADIUS, NODE_RADIUS, NODE_RADIUS); const circleTexture = app.renderer.generateTexture(circleGraphics, PIXI.settings.SCALE_MODE, RESOLUTION); const circleBorderGraphics = new PIXI.Graphics(); circleBorderGraphics.lineStyle(NODE_BORDER_WIDTH, TEXTURE_COLOR); circleBorderGraphics.drawCircle(NODE_BORDER_RADIUS, NODE_BORDER_RADIUS, NODE_RADIUS); const circleBorderTexture = app.renderer.generateTexture(circleBorderGraphics, PIXI.settings.SCALE_MODE, RESOLUTION); const iconTextures = new Map(uniq(nodes.map(nodeData => ICON_TEXT(nodeData))).map(icon => { const iconText = new PIXI.Text(icon, { fontFamily: ICON_FONT_FAMILY, fontSize: ICON_FONT_SIZE, fill: TEXTURE_COLOR }); const iconTexture = app.renderer.generateTexture(iconText, PIXI.settings.SCALE_MODE, RESOLUTION); return [icon, iconTexture]; })); // state let nodeDataToNodeGfx = new WeakMap(); let nodeGfxToNodeData = new WeakMap(); let nodeDataToLabelGfx = new WeakMap(); let labelGfxToNodeData = new WeakMap(); let linkDataToLinkGfx = new WeakMap(); let linkGfxToLinkData = new WeakMap(); let hoveredNodeData = undefined; let clickedNodeData = undefined; let hoveredLinkData = undefined; const updatePositions = () => { nodes.forEach(nodeData => { const nodeGfx = nodeDataToNodeGfx.get(nodeData); const labelGfx = nodeDataToLabelGfx.get(nodeData); nodeGfx.x = nodeData.x; nodeGfx.y = nodeData.y; labelGfx.x = nodeData.x; labelGfx.y = nodeData.y; }); links.forEach(linkData => { const sourceNodeData = nodes.find(nodeData => nodeData.id === linkData.source); const targetNodeData = nodes.find(nodeData => nodeData.id === linkData.target); const linkGfx = linkDataToLinkGfx.get(linkData); const line = linkGfx.getChildByName(LINE); const lineLength = Math.max(Math.sqrt((targetNodeData.x - sourceNodeData.x) ** 2 + (targetNodeData.y - sourceNodeData.y) ** 2) - NODE_BORDER_RADIUS * 2, 0); linkGfx.x = sourceNodeData.x; linkGfx.y = sourceNodeData.y; linkGfx.rotation = Math.atan2(targetNodeData.y - sourceNodeData.y, targetNodeData.x - sourceNodeData.x); line.width = lineLength; }); requestRender(); }; const round = value => Math.round(value * 1000) / 1000; const updateVisibility = () => { // culling const cull = new PIXI.Cull(); cull.addAll(nodesLayer.children); cull.addAll(labelsLayer.children); cull.addAll(linksLayer.children); cull.cull(app.renderer.screen); // console.log( // [...cull._targetList].filter(x => x.visible === true).length, // [...cull._targetList].filter(x => x.visible === false).length // ); // levels of detail const zoom = viewport.scale.x; const zoomSteps = [0.1, 0.2, 0.4, Infinity]; const zoomStep = zoomSteps.findIndex(zoomStep => zoom <= zoomStep); nodes.forEach(nodeData => { const nodeGfx = nodeDataToNodeGfx.get(nodeData); const circleBorder = nodeGfx.getChildByName(CIRCLE_BORDER); const icon = nodeGfx.getChildByName(ICON); const labelGfx = nodeDataToLabelGfx.get(nodeData); const label = labelGfx.getChildByName(LABEL); const labelBackground = labelGfx.getChildByName(LABEL_BACKGROUND); circleBorder.visible = zoomStep >= 1; icon.visible = zoomStep >= 2; label.visible = zoomStep >= 3; labelBackground.visible = zoomStep >= 3; }); links.forEach(linkData => { const linkGfx = linkDataToLinkGfx.get(linkData); const line = linkGfx.getChildByName(LINE); line.visible = zoomStep >= 1; }); }; // event handlers const hoverNode = nodeData => { if (clickedNodeData) { return; } if (hoveredNodeData === nodeData) { return; } hoveredNodeData = nodeData; const nodeGfx = nodeDataToNodeGfx.get(nodeData); const labelGfx = nodeDataToLabelGfx.get(nodeData); // move to front layer nodesLayer.removeChild(nodeGfx); frontNodesLayer.addChild(nodeGfx); labelsLayer.removeChild(labelGfx); frontLabelsLayer.addChild(labelGfx); // add hover effect const circleBorder = nodeGfx.getChildByName(CIRCLE_BORDER); circleBorder.tint = NODE_HOVER_BORDER_COLOR; const labelBackground = labelGfx.getChildByName(LABEL_BACKGROUND); labelBackground.tint = LABEL_HOVER_BACKGROUND_COLOR; labelBackground.alpha = LABEL_HOVER_BACKGROUND_ALPHA; requestRender(); }; const unhoverNode = nodeData => { if (clickedNodeData) { return; } if (hoveredNodeData !== nodeData) { return; } hoveredNodeData = undefined; const nodeGfx = nodeDataToNodeGfx.get(nodeData); const labelGfx = nodeDataToLabelGfx.get(nodeData); // move back from front layer frontNodesLayer.removeChild(nodeGfx); nodesLayer.addChildAt(nodeGfx, nodes.indexOf(nodeData)); frontLabelsLayer.removeChild(labelGfx); labelsLayer.addChildAt(labelGfx, nodes.indexOf(nodeData)); // clear hover effect const circleBorder = nodeGfx.getChildByName(CIRCLE_BORDER); circleBorder.tint = NODE_BORDER_COLOR; const labelBackground = labelGfx.getChildByName(LABEL_BACKGROUND); labelBackground.tint = LABEL_BACKGROUND_COLOR; labelBackground.alpha = LABEL_BACKGROUND_ALPHA; requestRender(); }; const hoverLink = linkData => { if (hoveredLinkData === linkData) { return; } hoveredLinkData = linkData; const linkGfx = linkDataToLinkGfx.get(linkData); // move to front layer linksLayer.removeChild(linkGfx); frontLinksLayer.addChild(linkGfx); // add hover effect const line = linkGfx.getChildByName(LINE); line.tint = LINK_HOVER_COLOR; requestRender(); }; const unhoverLink = linkData => { if (hoveredLinkData !== linkData) { return; } hoveredLinkData = undefined; const linkGfx = linkDataToLinkGfx.get(linkData); // move back from front layer frontLinksLayer.removeChild(linkGfx); linksLayer.addChildAt(linkGfx, links.indexOf(linkData)); // clear hover effect const line = linkGfx.getChildByName(LINE); line.tint = LINK_COLOR; requestRender(); }; const moveNode = (nodeData, point) => { const nodeGfx = nodeDataToNodeGfx.get(nodeData); nodeData.x = point.x; nodeData.y = point.y; updatePositions(); }; const appMouseMove = event => { if (!clickedNodeData) { return; } moveNode(clickedNodeData, viewport.toWorld(event.data.global)); }; const clickNode = nodeData => { clickedNodeData = nodeData; // enable node dragging app.renderer.plugins.interaction.on('mousemove', appMouseMove); // disable viewport dragging viewport.pause = true; }; const unclickNode = () => { clickedNodeData = undefined; // disable node dragging app.renderer.plugins.interaction.off('mousemove', appMouseMove); // enable viewport dragging viewport.pause = false; }; // create node graphics const nodeDataGfxPairs = nodes.map(nodeData => { const nodeGfx = new PIXI.Container(); nodeGfx.x = nodeData.x; nodeGfx.y = nodeData.y; nodeGfx.interactive = true; nodeGfx.buttonMode = true; nodeGfx.hitArea = new PIXI.Circle(0, 0, NODE_HIT_RADIUS); nodeGfx.on('mouseover', event => hoverNode(nodeGfxToNodeData.get(event.currentTarget))); nodeGfx.on('mouseout', event => unhoverNode(nodeGfxToNodeData.get(event.currentTarget))); nodeGfx.on('mousedown', event => clickNode(nodeGfxToNodeData.get(event.currentTarget))); nodeGfx.on('mouseup', () => unclickNode()); nodeGfx.on('mouseupoutside', () => unclickNode()); const circle = new PIXI.Sprite(circleTexture); circle.name = CIRCLE; circle.x = -circle.width / 2; circle.y = -circle.height / 2; circle.tint = colorToNumber(color(nodeData)); nodeGfx.addChild(circle); const circleBorder = new PIXI.Sprite(circleBorderTexture); circleBorder.name = CIRCLE_BORDER; circleBorder.x = -circleBorder.width / 2; circleBorder.y = -circleBorder.height / 2; circleBorder.tint = NODE_BORDER_COLOR; nodeGfx.addChild(circleBorder); const icon = new PIXI.Sprite(iconTextures.get(ICON_TEXT(nodeData))); icon.name = ICON; icon.x = -icon.width / 2; icon.y = -icon.height / 2; icon.tint = ICON_COLOR; nodeGfx.addChild(icon); const labelGfx = new PIXI.Container(); labelGfx.x = nodeData.x; labelGfx.y = nodeData.y; labelGfx.interactive = true; labelGfx.buttonMode = true; labelGfx.on('mouseover', event => hoverNode(labelGfxToNodeData.get(event.currentTarget))); labelGfx.on('mouseout', event => unhoverNode(labelGfxToNodeData.get(event.currentTarget))); labelGfx.on('mousedown', event => clickNode(labelGfxToNodeData.get(event.currentTarget))); labelGfx.on('mouseup', () => unclickNode()); labelGfx.on('mouseupoutside', () => unclickNode()); const label = new PIXI.BitmapText(LABEL_TEXT(nodeData), { font: { name: LABEL_FONT_FAMILY, size: LABEL_FONT_SIZE }, align: 'center', tint: LABEL_COLOR }); label.name = LABEL; label.x = -label.width / 2; label.y = NODE_HIT_RADIUS + LABEL_PADDING; const labelBackground = new PIXI.Sprite(PIXI.Texture.WHITE); labelBackground.name = LABEL_BACKGROUND; labelBackground.x = -(label.width + LABEL_PADDING * 2) / 2; labelBackground.y = NODE_HIT_RADIUS; labelBackground.width = label.width + LABEL_PADDING * 2; labelBackground.height = label.height + LABEL_PADDING * 2; labelBackground.tint = LABEL_BACKGROUND_COLOR; labelBackground.alpha = LABEL_BACKGROUND_ALPHA; labelGfx.addChild(labelBackground); labelGfx.addChild(label); nodesLayer.addChild(nodeGfx); labelsLayer.addChild(labelGfx); return [nodeData, nodeGfx, labelGfx]; }); // create link graphics const linkDataGfxPairs = links.map(linkData => { const sourceNodeData = nodes.find(nodeData => nodeData.id === linkData.source); const targetNodeData = nodes.find(nodeData => nodeData.id === linkData.target); const lineLength = Math.max(Math.sqrt((targetNodeData.x - sourceNodeData.x) ** 2 + (targetNodeData.y - sourceNodeData.y) ** 2) - NODE_BORDER_RADIUS * 2, 0); const lineSize = LINK_SIZE(linkData); const linkGfx = new PIXI.Container(); linkGfx.x = sourceNodeData.x; linkGfx.y = sourceNodeData.y; linkGfx.pivot.set(0, lineSize / 2); linkGfx.rotation = Math.atan2(targetNodeData.y - sourceNodeData.y, targetNodeData.x - sourceNodeData.x); linkGfx.interactive = true; linkGfx.buttonMode = true; linkGfx.on('mouseover', event => hoverLink(linkGfxToLinkData.get(event.currentTarget))); linkGfx.on('mouseout', event => unhoverLink(linkGfxToLinkData.get(event.currentTarget))); const line = new PIXI.Sprite(PIXI.Texture.WHITE); line.name = LINE; line.x = NODE_BORDER_RADIUS; line.y = -lineSize / 2; line.width = lineLength; line.height = lineSize; line.tint = LINK_COLOR; linkGfx.addChild(line); linksLayer.addChild(linkGfx); return [linkData, linkGfx]; }); // create lookup tables nodeDataToNodeGfx = new WeakMap(nodeDataGfxPairs.map(([nodeData, nodeGfx, labelGfx]) => [nodeData, nodeGfx])); nodeGfxToNodeData = new WeakMap(nodeDataGfxPairs.map(([nodeData, nodeGfx, labelGfx]) => [nodeGfx, nodeData])); nodeDataToLabelGfx = new WeakMap(nodeDataGfxPairs.map(([nodeData, nodeGfx, labelGfx]) => [nodeData, labelGfx])); labelGfxToNodeData = new WeakMap(nodeDataGfxPairs.map(([nodeData, nodeGfx, labelGfx]) => [labelGfx, nodeData])); linkDataToLinkGfx = new WeakMap(linkDataGfxPairs.map(([linkData, linkGfx]) => [linkData, linkGfx])); linkGfxToLinkData = new WeakMap(linkDataGfxPairs.map(([linkData, linkGfx]) => [linkGfx, linkData])); // initial draw resetViewport(); updatePositions(); viewport.on('frame-end', () => { if (viewport.dirty) { updateVisibility(); requestRender(); viewport.dirty = false; } }); // destroy PIXI application on Observable cell invalidation invalidation.then(() => { if (renderRequestId) { window.cancelAnimationFrame(renderRequestId); renderRequestId = undefined; } app.destroy(true, true); }); // prevent body scrolling app.view.addEventListener('wheel', event => { event.preventDefault(); }); // create container const container = html`

`; const toolbar = html`

`; container.appendChild(toolbar); const zoomInButton = html``; zoomInButton.addEventListener('click', () => zoomIn()); toolbar.appendChild(zoomInButton); const zoomOutButton = html``; zoomOutButton.addEventListener('click', () => zoomOut()); toolbar.appendChild(zoomOutButton); const resetButton = html``; resetButton.addEventListener('click', () => resetViewport()); toolbar.appendChild(resetButton); const infoText = html`

Layout stats:
Layout: ${config.layout}
Time: ${formatInt(layoutTime)} ms
Readability score: Computing...

`; const readabilityScoreText = infoText.querySelector('#readability-score'); toolbar.appendChild(infoText); if (config.showFpsMeter) { const fpsMeterContainer = html`

`; fpsMeterContainer.appendChild(fpsMeter()); container.appendChild(fpsMeterContainer); } container.appendChild(app.view); yield container; readabilityScoreText.innerHtml = 'Computing...'; const layoutReadability = await getLayoutReadability(graph); readabilityScoreText.innerText = formatFloat(layoutReadability); }34:T33ce,runLayout = (...args) => { return new Promise((resolve, reject) => { const workerCode = ` // hotfix for Sigma self.document = { documentElement: {}, createElement: function(tagName) { // hotfix for sigma.layout.paragraphl if (tagName === 'canvas') { return new OffscreenCanvas(100, 100); } } }; self.HTMLElement = function() {}; // hotfix for sigma.layout.paragraphl self.alert = console.error; Object.defineProperty(self, 'vizit', { get: function() { return window.vizit; } }); function randomString() { return Math.floor(Math.random() * 10e12).toString(36); } function runD3Layout(data, d3ForceManyBodyFunc) { const { nodes, links } = data; const iterations = 300; const nodeRepulsion = -250; d3.forceSimulation(nodes) .force('link', d3.forceLink(links).id(linkData => linkData.id)) .force('charge', d3ForceManyBodyFunc().strength(nodeRepulsion)) .force('center', d3.forceCenter()) .stop() .tick(iterations); const positions = Object.fromEntries(nodes.map(node => { return [node.id, { x: node.x, y: node.y }]; })); return positions; } function runCytoscapeLayout(data, cytoscapeLayoutName) { return new Promise(resolve => { const { nodes, links } = data; const iterations = 300; const nodeRepulsion = 1000000; const cytoscapeGraph = [ ...nodes.map(node => ({ group: 'nodes', data: node })), ...links.map(link => ({ group: 'edges', data: link })), ]; cytoscape({ headless: true, styleEnabled: false, layout: { name: cytoscapeLayoutName, // numIter: iterations, nodeRepulsion: nodeRepulsion, randomize: true, animate: false, stop: event => { const positions = Object.fromEntries(event.cy.elements('node').map(node => { return [node.id(), node.position()]; })); resolve(positions); }, }, elements: cytoscapeGraph, }); }); } async function runSigmaLayout(data, sigmaLayoutFunc) { const { nodes, links } = data; const iterations = 300; const scalingRatio = 40; const sigmaGraph = { nodes: nodes.map(node => ({ ...node, x: Math.random(), y: Math.random() })), edges: links.map(link => ({ id: randomString(), ...link })) }; const s = new sigma({ graph: sigmaGraph }); await sigmaLayoutFunc(s, { iterations, scalingRatio }); const positions = Object.fromEntries(s.graph.nodes().map(node => { return [node.id, { x: node.x, y: node.y }]; })); return positions; } function runGraphologyLayout(data, graphologyLayoutFunc) { const { nodes, links } = data; const iterations = 300; const scalingRatio = 80; const graph = new graphology.Graph(); nodes.forEach(node => { graph.addNode(node.id); }); links.forEach(link => { graph.addEdge(link.source, link.target); }); graph.forEachNode(nodeId => { graph.setNodeAttribute(nodeId, 'x', Math.random()); graph.setNodeAttribute(nodeId, 'y', Math.random()); }); const positions = graphologyLayoutFunc(graph, { iterations, settings: { ...graphologyLayoutFunc.inferSettings(graph), scalingRatio, }, }); return positions; } function runNgraphLayout(data, ngraphLayoutFunc) { const { nodes, links } = data; const iterations = 300; const gravity = -100; const graph = createGraph(); nodes.forEach(node => { graph.addNode(node.id); }); links.forEach(link => { graph.addLink(link.source, link.target); }); const layout = ngraphLayoutFunc(graph, { gravity: gravity }); for (let i = 0; i < iterations; i++) { layout.step(); } const positions = Object.fromEntries(nodes.map(node => { return [node.id, layout.getNodePosition(node.id)]; })); return positions; } function runSpringyLayout(data, springyLayoutFunc) { return new Promise(resolve => { const { nodes, links } = data; const graph = new Springy.Graph(); const nodesMap = new Map(nodes.map(node => { return [node.id, graph.newNode({ id: node.id })]; })); links.forEach(link => { graph.newEdge(nodesMap.get(link.source), nodesMap.get(link.target)); }); const layout = new springyLayoutFunc(graph, 400, 400, 0.5, 0.00001); layout.start(undefined, () => { const positions = Object.fromEntries(Array.from(nodesMap.values()).map(node => { const point = layout.point(node); return [node.data.id, { x: point.p.x * 20, y: point.p.y * 20 }]; })); resolve(positions); }); }); } function runRandomLayout(data) { const { nodes } = data; const positions = Object.fromEntries(nodes.map(node => { return [node.id, { x: Math.random() * 1000, y: Math.random() * 1000 }]; })); return positions; } async function runLayout(data, layoutName) { const layoutFuncs = new Map([ ['d3-force', { importUrls: [ 'https://unpkg.com/d3@5.14.2/dist/d3.min.js', ], run: data => runD3Layout(data, d3.forceManyBody), }], ['d3-force-reuse', { importUrls: [ 'https://unpkg.com/d3@5.14.2/dist/d3.min.js', 'https://unpkg.com/d3-force-reuse@1.0.1/build/d3-force-reuse.js', ], run: data => runD3Layout(data, d3.forceManyBodyReuse), }], ['d3-force-sampled', { importUrls: [ 'https://unpkg.com/d3@5.14.2/dist/d3.min.js', 'https://unpkg.com/d3-force-sampled@1.0.0/build/d3-force-sampled.js', ], run: data => runD3Layout(data, d3.forceManyBodySampled), }], ['cytoscape-cose', { importUrls: [ 'https://unpkg.com/cytoscape@3.13.0/dist/cytoscape.min.js', ], run: data => runCytoscapeLayout(data, 'cose'), }], ['cytoscape-cola', { importUrls: [ 'https://unpkg.com/cytoscape@3.13.0/dist/cytoscape.min.js', 'https://bundle.run/cytoscape-cola@2.3.0', ], run: data => runCytoscapeLayout(data, 'cola'), }], ['cytoscape-cose-bilkent', { importUrls: [ 'https://unpkg.com/cytoscape@3.13.0/dist/cytoscape.min.js', 'https://unpkg.com/layout-base@1.0.2/layout-base.js', 'https://unpkg.com/cose-base@1.0.1/cose-base.js', 'https://unpkg.com/cytoscape-cose-bilkent@4.1.0/cytoscape-cose-bilkent.js', ], run: data => runCytoscapeLayout(data, 'cose-bilkent'), }], ['cytoscape-fcose', { importUrls: [ 'https://unpkg.com/cytoscape@3.13.0/dist/cytoscape.min.js', 'https://unpkg.com/numeric@1.2.6/numeric-1.2.6.js', 'https://unpkg.com/layout-base@1.0.2/layout-base.js', 'https://unpkg.com/cose-base@1.0.1/cose-base.js', 'https://unpkg.com/cytoscape-fcose@1.2.0/cytoscape-fcose.js', ], run: data => runCytoscapeLayout(data, 'fcose'), }], ['cytoscape-euler', { importUrls: [ 'https://unpkg.com/cytoscape@3.13.0/dist/cytoscape.min.js', 'https://unpkg.com/cytoscape-euler@1.2.2/cytoscape-euler.js', ], run: data => runCytoscapeLayout(data, 'euler'), }], ['sigma.layout.fruchtermanReingold', { importUrls: [ 'https://unpkg.com/sigma@1.2.1/build/sigma.require.js', 'https://unpkg.com/sigma@1.2.1/build/plugins/sigma.plugins.animate.min.js', 'https://unpkg.com/linkurious@1.5.2/dist/plugins/sigma.layouts.fruchtermanReingold.min.js' ], run: data => runSigmaLayout( data, async (s, config) => { const listener = sigma.layouts.fruchtermanReingold.configure(s, { maxIterations: config.iterations }); const promise = new Promise(resolve => listener.bind('stop', resolve)); sigma.layouts.fruchtermanReingold.start(s); await promise; const scalingRatio = 10; s.graph.nodes().forEach(node => { node.x = node.x * scalingRatio; node.y = node.y * scalingRatio; }); } ), }], ['sigma.layout.forceAtlas2', { importUrls: [ 'https://unpkg.com/sigma@1.2.1/build/sigma.require.js', 'https://unpkg.com/sigma@1.2.1/build/plugins/sigma.layout.forceAtlas2.min.js' ], run: data => runSigmaLayout( data, async (s, config) => { s.startForceAtlas2({ startingIterations: config.iterations, iterationsPerRender: 0, scalingRatio: config.scalingRatio }); await new Promise(resolve => setTimeout(resolve, 500)); s.killForceAtlas2(); } ), }], ['sigma.layout.paragraphl', { importUrls: [ 'https://unpkg.com/sigma@1.2.1/build/sigma.require.js', 'https://unpkg.com/sigma@1.2.1/build/plugins/sigma.plugins.animate.min.js', 'https://cdn.jsdelivr.net/gh/nblintao/ParaGraphL@master/GPGPUtility.js', 'https://cdn.jsdelivr.net/gh/nblintao/ParaGraphL@master/sigma.layout.paragraphl.js' ], run: data => runSigmaLayout( data, async (s, config) => { var listener = sigma.layouts.paragraphl.configure(s, { iterations: config.iterations }); const promise = new Promise(resolve => listener.bind('stop', resolve)); sigma.layouts.paragraphl.start(s); await promise; const scalingRatio = 10; s.graph.nodes().forEach(node => { node.x = node.x * scalingRatio; node.y = node.y * scalingRatio; }); } ) }], ['graphology-layout-forceatlas2', { importUrls: [ 'https://unpkg.com/graphology@0.17.0/dist/graphology.umd.js', 'https://unpkg.com/graphology-layout-forceatlas2@0.4.2/build/graphology-layout-forceatlas2.min.js', ], run: data => runGraphologyLayout(data, forceAtlas2), }], ['ngraph.forcelayout', { importUrls: [ 'https://unpkg.com/ngraph.graph@19.0.2/dist/ngraph.graph.min.js', 'https://bundle.run/ngraph.forcelayout@1.0.0/index.js', ], run: data => runNgraphLayout(data, ngraph_forcelayout), }], ['springy', { importUrls: [ 'https://unpkg.com/springy@2.8.0/springy.js', ], run: data => runSpringyLayout(data, Springy.Layout.ForceDirected), }], ['random', { run: data => runRandomLayout(data), }], ]); const layoutFunc = layoutFuncs.get(layoutName); if (!layoutFunc) { throw new Error('Unknown layout ' + layoutName); } // import layout dependencies if (layoutFunc.importUrls) { layoutFunc.importUrls.forEach(importUrl => { importScripts(importUrl); }); } // run layout and measure time const startTime = performance.now(); const positions = await layoutFunc.run(data); const endTime = performance.now(); const layoutTime = endTime - startTime; const result = { positions, layoutTime }; return result; }; self.onmessage = async event => { const result = await runLayout.apply(undefined, event.data); self.postMessage(result); } `; const workerBlob = new Blob([workerCode], { type: 'application/javascript' }); const workerUrl = URL.createObjectURL(workerBlob) const worker = new Worker(workerUrl); worker.onmessage = event => { resolve(event.data); worker.terminate(); URL.revokeObjectURL(workerUrl); }; worker.postMessage(args); }); }35:T492,getLayoutReadability = (...args) => { return new Promise((resolve, reject) => { const workerCode = ` importScripts('https://cdn.jsdelivr.net/gh/rpgove/greadability@master/greadability.js'); function getLayoutReadability(graph) { const layoutQuality = greadability.greadability( JSON.parse(JSON.stringify(graph.nodes)), JSON.parse(JSON.stringify(graph.links)), d => d.id, ); const layoutReadability = (layoutQuality.crossing + layoutQuality.crossingAngle + layoutQuality.angularResolutionMin + layoutQuality.angularResolutionDev) / 4; return layoutReadability; } self.onmessage = async event => { const result = await getLayoutReadability.apply(undefined, event.data); self.postMessage(result); } `; const workerBlob = new Blob([workerCode], { type: 'application/javascript' }); const workerUrl = URL.createObjectURL(workerBlob) const worker = new Worker(workerUrl); worker.onmessage = event => { resolve(event.data); worker.terminate(); URL.revokeObjectURL(workerUrl); }; worker.postMessage(args); }); }36:[] 2f:{"id":"7e5de669ef809db2","slug":"force-directed-graph-pixi","title":"Force-Directed Graph - WebGL & Canvas with PIXI.js","thumbnail":"4a466a92801d4fa3c692cf9791eee41f24fa4f17f0693dba4c71b87dcdad27d5","access_level":"public","create_time":"$D2019-08-11T18:44:11.628Z","update_time":"$D2020-11-02T07:45:17.534Z","view_time":null,"first_public_time":"$D2019-08-11T18:45:19.495Z","fork":{"id":"a6c00de7c09bdfa1","slug":"force-directed-graph-component","title":"Force-directed graph component","owner":{"id":"863951e3ebe4c0ae","login":"d3","name":"D3"}},"stars":44,"starred":false,"owner":{"type":"team","id":"a12effbfd35c93c7","login":"zakjan","name":"Jan Žák","avatar_url":"https://avatars-next.observableusercontent.com/734b40ac6df193f558af089ec56464c2b7d80288e1cef2475d312d15c2cb2bfa","tier":"starter_2024"},"version":1959,"publish_version":1959,"role":null,"authored":false,"authors":[{"type":"individual","id":"b40b7243df0ef758","login":"zakjan","name":"Jan Žák","avatar_url":"https://avatars-next.observableusercontent.com/734b40ac6df193f558af089ec56464c2b7d80288e1cef2475d312d15c2cb2bfa","tier":null}],"members":[{"type":"individual","id":"b40b7243df0ef758","login":"zakjan","name":"Jan Žák","avatar_url":"https://avatars-next.observableusercontent.com/734b40ac6df193f558af089ec56464c2b7d80288e1cef2475d312d15c2cb2bfa","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":72,"collection":{"id":"bd6bf555ef3feef1","slug":"graphs","title":"Graphs","owner":{"id":"a12effbfd35c93c7","login":"zakjan","name":"Jan Žák"}},"type":"notebook","body":{"title":"Force-Directed Graph - WebGL & Canvas with PIXI.js","cells":[{"id":1,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":694,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1543,"value":"md`Total nodes: ${formatInt(graph.nodes.length)}, links: ${formatInt(graph.links.length)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":770,"value":"graphs = {\n const lesMiserables = await d3.json(\"https://gist.githubusercontent.com/mbostock/4062045/raw/5916d145c8c048a6e3086915a6be464467391c62/miserables.json\");\n const socfbCaltech36 = await d3.json(\"https://gist.githubusercontent.com/zakjan/eb366020e5477c578456d8cf9e8e5d01/raw/373d82875ac329e0543f3f723010c53423a0588a/socfb-Caltech36.json\");\n \n return {\n 'Point': point(),\n 'Line': line(10),\n 'Circle': circle(10),\n 'Star': star(10),\n 'Wheel': wheel(10),\n 'Complete': complete(10),\n 'Triangle Lattice': triangleLattice(5),\n 'Square Lattice': squareLattice(5),\n 'Sierpinski Triangle': sierpinskiTriangle(3),\n 'Les Misérables': lesMiserables,\n 'socfb-Caltech36': socfbCaltech36,\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":773,"value":"graph = hyper(\n multiply(\n graphs[config.graph],\n parseInt(config.multiply, 10)\n ),\n parseInt(config.hyper, 10)\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"height = 600","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"color = {\n const scale = d3.scaleOrdinal(d3.schemeCategory10);\n return nodeData => scale(nodeData.group);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":140,"value":"colorToNumber = color => parseInt(color.slice(1), 16)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1246,"value":"layouts = ['d3-force', 'd3-force-reuse', 'd3-force-sampled', 'cytoscape-cola', 'cytoscape-cose', 'cytoscape-cose-bilkent', 'cytoscape-fcose', 'cytoscape-euler', 'sigma.layout.fruchtermanReingold', 'sigma.layout.forceAtlas2', 'sigma.layout.paragraphl', 'graphology-layout-forceatlas2', 'ngraph.forcelayout', 'springy', 'random']","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":498,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1873,"value":"$35","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":708,"value":"md`## Imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"d3 = require(\"d3@5.14.2\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":201,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":207,"value":"FontFaceObserver = require('fontfaceobserver@2.1.0').catch(() => window.FontFaceObserver)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":139,"value":"PIXI = require('pixi.js@5.2.0/dist/pixi.min.js').catch(async () => {\n window.PIXI.Cull = (await require('https://bundle.run/@pixi-essentials/cull@1.0.5/dist/cull.js')).PIXI.Cull;\n return window.PIXI;\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":264,"value":"Viewport = (await require('https://bundle.run/pixi-viewport@4.5.0/dist/viewport.js')).Viewport","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":695,"value":"import {select, checkbox} from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":699,"value":"import {inputsForm} from '@zakjan/inputs-form'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":839,"value":"import {fpsMeter} from '@zakjan/fps-meter'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1587,"value":"import {uniq, formatInt, formatFloat, randomString} from '@zakjan/utils'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1531,"value":"import {point, line, circle, star, wheel, complete, triangleLattice, squareLattice, sierpinskiTriangle, multiply, hyper} from '@zakjan/graph-utils'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 30:"$2f:body"