Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
@tangle/graph
Advanced tools
@tangle/graph - npm Package Compare versions
Comparing version 1.3.1 to 2.0.0
102
index.js
| const { LinkMap, BacklinkMap } = require('./maps') | ||
| const Lookup = require('./lookup') | ||
| const isRoot = require('./lib/is-root') | ||
| const defaultGetBacklink = node => node.previous | ||
| module.exports = class Graph { | ||
| constructor (nodes, opts = {}) { | ||
| const getBacklinks = opts.getBacklinks || (node => node.previous) | ||
| // NOTE do not confuse with this.getBacklinks method described below | ||
| this._getBacklinks = opts.getBacklinks || defaultGetBacklink | ||
| // this._getBacklinks fetchs the backlink from an individual message. | ||
| // this.getBacklinks fetch the backlinks from a particular node in the graph. | ||
| this.nodes = nodes | ||
| this.setupGraph() | ||
| } | ||
| if (!Array.isArray(nodes)) error('nodes to be an Array') | ||
| if (new Set(nodes.map(node => node.key)).size !== nodes.length) { | ||
| setupGraph () { | ||
| if (!Array.isArray(this.nodes)) error('nodes to be an Array') | ||
| if (new Set(this.nodes.map(node => node.key)).size !== this.nodes.length) { | ||
| error('each node to have a unique key') | ||
| } | ||
| if (typeof getBacklinks !== 'function') error('opts.getBacklinks to be a function') | ||
| this.rootKeys = nodes | ||
| .filter(node => isRoot(node, getBacklinks)) | ||
| this.rootKeys = this.nodes | ||
| .filter(node => isRoot(node, this._getBacklinks)) | ||
| .map(node => node.key) | ||
| if (this.rootKeys.length === 0) error('at least one root node') | ||
| if (containsSelfLoop(nodes, getBacklinks)) throw new Error('there is a selfloop in nodes') | ||
| if (containsSelfLoop(this.nodes, this._getBacklinks)) throw new Error('there is a selfloop in nodes') | ||
| // build map of each hop which runs forward causally | ||
| this.linkMap = new LinkMap(nodes, getBacklinks) | ||
| this.linkMap = new LinkMap(this.nodes, this._getBacklinks) | ||
| // and the inverse | ||
| this.backlinkMap = new BacklinkMap(this.linkMap) | ||
| this.lookup = new Lookup({ nodes, linkMap: this.linkMap, getBacklinks }) | ||
| this.lookup = new Lookup({ nodes: this.nodes, linkMap: this.linkMap, getBacklinks: this._getBacklinks }) | ||
| if (containsCycles(this.lookup._connected, getBacklinks)) throw new Error('there is a cycle in connected nodes') | ||
| // if (containsCycles(this.lookup.connected, this._getBacklinks)) throw new Error('there is a cycle in connected nodes') | ||
| } | ||
@@ -49,13 +54,19 @@ | ||
| isBranchNode (key) { | ||
| return this.linkMap.get(key).length > 1 | ||
| if (!this.lookup.isConnected(key)) return false | ||
| return this.linkMap.get(key) | ||
| .filter(link => this.lookup.isConnected(link)) | ||
| .length > 1 | ||
| } | ||
| isMergeNode (key) { | ||
| if (!this.lookup.isConnected(key)) return false | ||
| return this.backlinkMap.get(key).length > 1 | ||
| } | ||
| isHeadNode (key) { | ||
| if (!this.lookup.getNode(key)) return false | ||
| isTipNode (key) { | ||
| if (!this.lookup.isConnected(key)) return false | ||
| return this.linkMap.get(key).length === 0 | ||
| return this.linkMap.get(key) | ||
| .filter(link => this.lookup.isConnected(link)) | ||
| .length === 0 | ||
| } | ||
@@ -79,2 +90,15 @@ | ||
| } | ||
| addNodes (newNodes) { | ||
| const undoNodes = this.nodes // This will revert changes to the nodes, but not to linkmaps or anything. | ||
| // Modifying graph | ||
| this.nodes = [...this.nodes, ...newNodes] | ||
| try { | ||
| this.setupGraph() | ||
| } catch (err) { | ||
| this.nodes = undoNodes | ||
| throw err | ||
| } | ||
| } | ||
| } | ||
@@ -87,30 +111,40 @@ | ||
| function containsSelfLoop (nodes, getBacklinks) { | ||
| return nodes.some((node) => getBacklinks(node) !== null && getBacklinks(node).includes(node.key)) // There is some node in nodes where node.key is in node.previous | ||
| return nodes.some((node) => ( | ||
| getBacklinks(node) !== null && | ||
| getBacklinks(node).includes(node.key) // There is some node in nodes where node.key is in node.previous | ||
| )) | ||
| } | ||
| /* | ||
| //Note that due to semiconnected nodes not appearing in graphs, we do not find larger Cycles | ||
| function containsCycles (connectedNodes, getBacklinks) { | ||
| var nodesToCheck = {} | ||
| var keysToRemoveFromPrevious = [] | ||
| Object.values(connectedNodes).forEach(nodeValue => { // We will only look for connected cycles | ||
| if (getBacklinks(nodeValue) === null) { // Root nodes will not be part of a cycle | ||
| keysToRemoveFromPrevious.push(nodeValue.key) | ||
| } else { | ||
| nodesToCheck[nodeValue.key] = getBacklinks(nodeValue) // Create a dictionary of nodes to check where previous only contains connected nodes | ||
| nodesToCheck[nodeValue.key] = nodesToCheck[nodeValue.key].filter(item => Object.keys(connectedNodes).includes(item)) | ||
| const seenNodes = new Set() | ||
| const nodesToCheck = {} | ||
| Object.values(connectedNodes).forEach(node => { // We will only look for connected cycles | ||
| if (getBacklinks(node) === null) seenNodes.add(node.key) | ||
| // Root nodes will not be part of a cycle | ||
| else { | ||
| nodesToCheck[node.key] = getBacklinks(node).filter(key => key in connectedNodes) | ||
| // Create a dictionary of nodes to check which only contains connected nodes | ||
| } | ||
| }) | ||
| var progressMade = true | ||
| while (Object.keys(nodesToCheck).length && progressMade) { // We want to keep looping until we run of nodes to check (good) or don't make progress (bad) | ||
| progressMade = false | ||
| Object.keys(nodesToCheck).forEach(nodeID => { | ||
| nodesToCheck[nodeID] = nodesToCheck[nodeID].filter(item => !keysToRemoveFromPrevious.includes(item)) // Remove all nodes Not in cycle from 'previous' | ||
| if (nodesToCheck[nodeID].length === 0) { | ||
| progressMade = true | ||
| keysToRemoveFromPrevious.push(nodeID) // We have deleted all previous so we know it's not part of a cycle | ||
| delete nodesToCheck[nodeID] | ||
| let foundLoop = false | ||
| while (!foundLoop && Object.keys(nodesToCheck).length) { | ||
| foundLoop = true | ||
| Object.keys(nodesToCheck).forEach(nodeKey => { | ||
| nodesToCheck[nodeKey] = nodesToCheck[nodeKey].filter(backlink => !seenNodes.has(backlink)) | ||
| // Remove all nodes NOT in cycle from 'previous' | ||
| if (nodesToCheck[nodeKey].length === 0) { | ||
| foundLoop = false | ||
| seenNodes.add(nodeKey) // We have deleted all previous so we know it's not part of a cycle | ||
| delete nodesToCheck[nodeKey] | ||
| } | ||
| }) | ||
| } | ||
| return (!progressMade) | ||
| return foundLoop | ||
| } | ||
| */ |
@@ -26,3 +26,2 @@ const isRoot = require('./lib/is-root') | ||
| } = opts | ||
| if (!entryKeys) { | ||
@@ -40,10 +39,19 @@ entryKeys = nodes | ||
| }) | ||
| var queue = entryKeys | ||
| var key | ||
| // Copy the graph roots to start searching for connected nodes | ||
| const queue = [...entryKeys] | ||
| let key | ||
| while (queue.length) { | ||
| key = queue.pop() | ||
| if (this.connected[key]) continue | ||
| // Check if all previous are connected already | ||
| if (getBacklinks(this.disconnected[key]) !== null) { | ||
| const previousNodesConnected = getBacklinks(this.disconnected[key]).every(previousKey => { | ||
| return this.connected[previousKey] | ||
| }) | ||
| // If not, add them to the holding cell (remains disconnected) | ||
| if (!previousNodesConnected) continue | ||
| } | ||
| // If it is then | ||
| // move record from 'disconnected' dict to 'connected' dict | ||
@@ -63,3 +71,3 @@ this.connected[key] = this.disconnected[key] | ||
| previous.forEach(linkedKey => { | ||
| if (!this.disconnected[linkedKey]) this.disconnected[linkedKey] = null | ||
| if (!this.disconnected[linkedKey] && !this.connected[linkedKey]) this.disconnected[linkedKey] = null | ||
| }) | ||
@@ -92,11 +100,2 @@ }) | ||
| } | ||
| /* getters */ | ||
| get _connected () { | ||
| return this.connected | ||
| } | ||
| get _disconnected () { | ||
| return this.disconnected | ||
| } | ||
| } |
@@ -34,8 +34,8 @@ const set = require('lodash.set') | ||
| var pruneKeys = new Set(keys) | ||
| const pruneKeys = new Set(keys) | ||
| // starting with the declared keys for pruning, | ||
| // we determine which keys are downstream of that | ||
| var queue = [...this.entryKeys] | ||
| var key | ||
| const queue = [...this.entryKeys] | ||
| let key | ||
@@ -56,3 +56,3 @@ while (queue.length) { | ||
| var newMap = clone(this.map) | ||
| const newMap = clone(this.map) | ||
@@ -59,0 +59,0 @@ // remove the top level invalid nodes |
| { | ||
| "name": "@tangle/graph", | ||
| "version": "1.3.1", | ||
| "version": "2.0.0", | ||
| "description": "a helper for building + updating traverseable tangle graphs", | ||
@@ -8,3 +8,3 @@ "main": "index.js", | ||
| "test": "npm run test:js && npm run lint", | ||
| "test:js": "tape test/*.test.js | tap-spec", | ||
| "test:js": "tape test/*.test.js | faucet", | ||
| "lint": "standard --fix" | ||
@@ -32,7 +32,7 @@ }, | ||
| "devDependencies": { | ||
| "faucet": "0.0.1", | ||
| "lodash.get": "^4.4.2", | ||
| "standard": "^14.3.4", | ||
| "tap-spec": "^5.0.0", | ||
| "standard": "^16.0.3", | ||
| "tape": "^5.0.1" | ||
| } | ||
| } |
@@ -83,3 +83,3 @@ # @tangle/graph | ||
| ### `graph.isBrancNode(key) => Boolean` | ||
| ### `graph.isBranchNode(key) => Boolean` | ||
@@ -94,5 +94,5 @@ Tells you whether the graph diverges as you proceed from the given node-key. | ||
| ### `graph.isHeadNode(key) => Boolean` | ||
| ### `graph.isTipNode(key) => Boolean` | ||
| Tells you whether the given node-key belongs to a _head_ of the graph, | ||
| Tells you whether the given node-key belongs to a _tip_ of the graph, | ||
| i.e. a leading tip causally | ||
@@ -99,0 +99,0 @@ (basically `graph.getLinks(key).length === 0`) |
@@ -38,3 +38,3 @@ const test = require('tape') | ||
| () => new Graph([A, B, C], { getBacklinks: true }), | ||
| /getBacklinks to be a function/, | ||
| /getBacklinks is not a function/, | ||
| 'throws if getBacklinks is invalid' | ||
@@ -110,9 +110,9 @@ ) | ||
| test('graph.isHeadNode', t => { | ||
| t.equal(graph.isHeadNode('A'), false, 'A not headNode') | ||
| t.equal(graph.isHeadNode('B'), false, 'B not headNode') | ||
| t.equal(graph.isHeadNode('D'), true, 'D is headNode') | ||
| t.equal(graph.isHeadNode('W'), false, 'W not headNode') // disconnected | ||
| t.equal(graph.isHeadNode('X'), false, 'X not headNode') // disconnected | ||
| t.equal(graph.isHeadNode('Z'), false, 'Z not headNode') // exterior node | ||
| test('graph.isTipNode', t => { | ||
| t.equal(graph.isTipNode('A'), false, 'A not headNode') | ||
| t.equal(graph.isTipNode('B'), false, 'B not headNode') | ||
| t.equal(graph.isTipNode('D'), true, 'D is headNode') | ||
| t.equal(graph.isTipNode('W'), false, 'W not headNode') // disconnected | ||
| t.equal(graph.isTipNode('X'), false, 'X not headNode') // disconnected | ||
| t.equal(graph.isTipNode('Z'), false, 'Z not headNode') // exterior node | ||
@@ -149,4 +149,4 @@ t.end() | ||
| t.deepEqual(new Graph([A1, A2, J]).rootNodes, [A1, A2], 'Graph can have multiple rootNodes') | ||
| t.deepEqual(new Graph([A1, J]).getBacklinks('J'), ['A1', 'A2'], 'getBacklinks but one is missing') // I expected this to give just ['A1'] | ||
| t.deepEqual(new Graph([A1, J]).isMergeNode('J'), true, 'missing node in graph but still a mergeNode') // I didn't think this would be a mergenode | ||
| t.deepEqual(new Graph([A1, J]).getBacklinks('J'), [], 'getBacklinks for semiconnected') // I expected this to give just ['A1'] | ||
| t.deepEqual(new Graph([A1, J]).isMergeNode('J'), false, 'missing node in graph so not a a mergeNode') // I didn't think this would be a mergenode | ||
| // Maybe getBacklinks should give just the known nodes and then the disconnected ones seperately. | ||
@@ -153,0 +153,0 @@ |
@@ -33,4 +33,4 @@ const test = require('tape') | ||
| t.deepEqual(lookup._connected, { A, B, C }, 'categorises connected') | ||
| t.deepEqual(lookup._disconnected, { K, J: null }, 'categorises disconnected') | ||
| t.deepEqual(lookup.connected, { A, B, C }, 'categorises connected') | ||
| t.deepEqual(lookup.disconnected, { K, J: null }, 'categorises disconnected') | ||
@@ -42,6 +42,45 @@ /* prune! */ | ||
| t.deepEqual(lookup._connected, { A, B }, 'categorises connected') | ||
| t.deepEqual(lookup._disconnected, { C, K, J: null }, 'categorises disconnected') | ||
| t.deepEqual(lookup.connected, { A, B }, 'categorises connected') | ||
| t.deepEqual(lookup.disconnected, { C, K, J: null }, 'categorises disconnected') | ||
| t.end() | ||
| }) | ||
| test('Lookup semiconnected', t => { | ||
| // ## message in-thread but "dangling" (doesn't link up to known messages) | ||
| // | ||
| // A K? | ||
| // | / | ||
| // B J | ||
| // | / | ||
| // C | ||
| const A = { key: 'A', previous: null } | ||
| const B = { key: 'B', previous: ['A'] } | ||
| const C = { key: 'C', previous: ['B', 'J'] } | ||
| const J = { key: 'J', previous: ['K'] } // disconnected | ||
| const linkMap = new LinkMap([A, B, C, J], getBacklinks) | ||
| const lookup = new Lookup({ | ||
| nodes: [A, B, C, J], | ||
| // entryKeys: ['A'], | ||
| linkMap | ||
| }) | ||
| t.deepEqual(lookup.getNode('A'), A, 'getNode') | ||
| t.equal(lookup.getNode('C'), null, 'getNode (semiconnected key)') | ||
| t.deepEqual(lookup.connected, { A, B }, 'categorises connected') | ||
| t.deepEqual(lookup.disconnected, { C, J, K: null }, 'categorises disconnected') | ||
| /* prune! */ | ||
| lookup.disconnect(['C']) // Disconnect a semiconnected key | ||
| t.deepEqual(lookup.connected, { A, B }, 'categorises connected') | ||
| t.deepEqual(lookup.disconnected, { C, J, K: null }, 'categorises disconnected') | ||
| lookup.disconnect(['J']) // Disconnect a disconnected leading to semiconnected key | ||
| t.deepEqual(lookup.connected, { A, B }, 'categorises connected') | ||
| t.deepEqual(lookup.disconnected, { C, J, K: null }, 'categorises disconnected') | ||
| t.end() | ||
| }) |
| const test = require('tape') | ||
| const Graph = require('..') | ||
| // C1---C2 | ||
| // \ / | ||
| // C3 | ||
| test('Self loop', t => { | ||
| const A1 = { key: 'A1', previous: null } | ||
| const SL = { key: 'SL', previous: ['SL', 'A1'] } // Selfloop | ||
| // C2---C3 A1 | ||
| // \ / / | ||
| // C1 / | ||
| // \ / | ||
| // C4 | ||
| t.throws(() => new Graph([A1, SL]), /there is a selfloop in nodes/, 'new Selfloop Graph') | ||
| // Big mess connected to a root | ||
| // A1 | ||
| // \\\ | ||
| // M1, ) | ||
| // ( M2, ) | ||
| // ( M3 | ||
| const graph = new Graph([A1]) | ||
| t.throws(() => graph.addNodes([SL]), /there is a selfloop in nodes/, 'addNodes spots new selfloop') | ||
| t.deepEqual(new Graph([A1]), graph, 'addNodes reverted if selfloop found') | ||
| const A1 = { key: 'A1', previous: null } | ||
| const C1 = { key: 'C1', previous: ['C2'] } | ||
| const C2 = { key: 'C2', previous: ['C3'] } | ||
| const C3 = { key: 'C3', previous: ['C1'] } | ||
| t.end() | ||
| }) | ||
| // One parent is the root but the other is part of a circle | ||
| const C4 = { key: 'C4', previous: ['C1', 'A1'] } | ||
| const SL = { key: 'SL', previous: ['SL', 'A1'] } // Selfloop | ||
| test('Cycles (disconnected)', t => { | ||
| // C1---C2 | ||
| // \ / | ||
| // C3 | ||
| const M1 = { key: 'M1', previous: ['A1', 'M2', 'M3'] } | ||
| const M2 = { key: 'M2', previous: ['A1', 'M1', 'M3'] } | ||
| const M3 = { key: 'M3', previous: ['A1', 'M1', 'M2'] } | ||
| // C2---C3 A1 | ||
| // \ / / | ||
| // C1 / | ||
| // \ / | ||
| // C4 | ||
| test('disconnected loops', t => { | ||
| t.throws(() => new Graph([C1, C2, C3]), | ||
| /at least one root node/, | ||
| 'new Circular Graph') | ||
| // t.true(new Graph([C1, C2, C3, A1]), 'new Circular Graph with a disconnected root node') //No checks for cycles | ||
| const A1 = { key: 'A1', previous: null } | ||
| const C1 = { key: 'C1', previous: ['C2'] } | ||
| const C2 = { key: 'C2', previous: ['C3'] } | ||
| const C3 = { key: 'C3', previous: ['C1'] } | ||
| // One parent is the root but the other is part of a circle | ||
| const C4 = { key: 'C4', previous: ['C1', 'A1'] } | ||
| t.throws(() => new Graph([C1, C2, C3]), /at least one root node/, 'all graphs need some root') | ||
| t.true(new Graph([C1, C2, C3, A1]), 'cycle that is not connected is fine') | ||
| new Graph([C1, C2, C3, A1]).invalidateKeys(['C1']) // Can invalidate a node in a cycle if it's disconnected | ||
@@ -45,10 +45,11 @@ | ||
| const circularRootGraph = new Graph([C1, C2, C3, C4, A1]) | ||
| t.equal(circularRootGraph.isMergeNode('C4'), true, 'C4 is a merge node') | ||
| t.equal(circularRootGraph.isBranchNode('C1'), true, 'Circle C1 is a branch node') // Since C1 is disconnected, should it still be a branch node? | ||
| t.deepEqual(circularRootGraph.getLinks('C1'), [], 'getLinks of circle C1 gives []') // I expected this to give ['C4','C2'] since C1 is a branch node but it gives [] since it's disconnected | ||
| t.equal(circularRootGraph.isMergeNode('C4'), false, 'C4 is a semiconnected merge node') | ||
| t.equal(circularRootGraph.isBranchNode('C1'), false, 'Circle C1 is disconnected') | ||
| t.deepEqual(circularRootGraph.getLinks('C1'), [], 'getLinks of disconnected circle C1 gives []') // I expected this to give ['C4','C2'] since C1 is a branch node but it gives [] since it's disconnected | ||
| t.deepEqual(circularRootGraph.getBacklinks('C1'), [], 'getBacklinks of circle C1') // I expected this to give ['C3'] | ||
| t.deepEqual(circularRootGraph.getBacklinks('C4'), ['C1', 'A1'], 'getBacklinks to part of the circle') | ||
| t.deepEqual(circularRootGraph.getBacklinks('C4'), [], 'C4 is semiconnected') | ||
| console.log('circular root graph ', circularRootGraph.lookup.connected) | ||
| t.deepEqual(circularRootGraph.getNode('C2'), null, 'node in circle not accessible') | ||
| t.deepEqual(circularRootGraph.getNode('C4'), C4, 'can find C4') | ||
| t.deepEqual(circularRootGraph.getNode('C4'), null, 'cant find C4 since it is semiconnected') | ||
@@ -58,35 +59,94 @@ t.end() | ||
| /* | ||
| We check if there is a cycle in the loop. | ||
| We do this by repeatedly removing nodes that are not part of a cycle, starting from the roots | ||
| { | ||
| A1: { key: 'A1', previous: null }, | ||
| M1: { key: 'M1', previous: [ 'A1', 'M2', 'M3' ] }, | ||
| M2: { key: 'M2', previous: [ 'A1', 'M1', 'M3' ] }, | ||
| M3: { key: 'M3', previous: [ 'A1', 'M1', 'M2' ] } | ||
| } | ||
| { | ||
| M1: [ 'A1', 'M2', 'M3' ], | ||
| M2: [ 'A1', 'M1', 'M3' ], | ||
| M3: [ 'A1', 'M1', 'M2' ] | ||
| } | ||
| { M1: [ 'M2', 'M3' ], M2: [ 'M1', 'M3' ], M3: [ 'M1', 'M2' ] } | ||
| When we can't remove any more we have either found a cycle (like above) or shown that none of the nodes are in a loop. | ||
| test('Cycles', t => { | ||
| // A1 | ||
| // | | ||
| // V | ||
| // M1 <-- M3 | ||
| // | ^ | ||
| // v / | ||
| // M2 / | ||
| Note, we only check connected nodes and initially remove any disconnected nodes from previous. | ||
| */ | ||
| test('Detecting cycles', t => { | ||
| t.throws(() => new Graph([A1, SL]), | ||
| /there is a selfloop in nodes/, | ||
| 'new Selfloop Graph') | ||
| const A1 = { key: 'A1', previous: null } | ||
| t.throws(() => new Graph([A1, M1, M2, M3]), | ||
| /there is a cycle in connected nodes/, | ||
| 'new Circular Graph') | ||
| const M1 = { key: 'M1', previous: ['A1', 'M3'] } | ||
| const M2 = { key: 'M2', previous: ['M1'] } | ||
| const M3 = { key: 'M3', previous: ['M2'] } | ||
| t.throws(() => new Graph([A1, M1, M2]), | ||
| /there is a cycle in connected nodes/, | ||
| 'new Circular Graph') | ||
| t.true(new Graph([A1, M1]), 'new not Circular Graph') | ||
| const graph = new Graph([A1, M1, M2, M3]) | ||
| t.deepEqual(Object.keys(graph.lookup.connected), ['A1'], 'no cycle in list of connected nodes') | ||
| // NOTE - these tests are failing because the nodes are "semi-connected" | ||
| // i.e. M1 is not considered connected because it's previous nodes don't all come from a root | ||
| // so we never hit the cycle detector... | ||
| // t.throws(() => new Graph([A1, M1, M2, M3]), /there is a cycle in connected nodes/, 'new Circular Graph') | ||
| // t.throws(() => new Graph([A1, M1, M2]), /there is a cycle in connected nodes/, 'new Circular Graph') | ||
| // const graph = new Graph([A1]) | ||
| // t.throws(() => graph.addNodes([M1, M2, M3]), /there is a cycle in connected nodes/, 'addNodes throws if it creates cycle') | ||
| t.end() | ||
| }) | ||
| test('Cycles (2)', t => { | ||
| // Big mess connected to a root | ||
| // A1 | ||
| // \\\ | ||
| // M1, ) | ||
| // ( M2, ) | ||
| // ( M3 | ||
| const A1 = { key: 'A1', previous: null } | ||
| const M1 = { key: 'M1', previous: ['A1', 'M2', 'M3'] } | ||
| const M2 = { key: 'M2', previous: ['A1', 'M1', 'M3'] } | ||
| const M3 = { key: 'M3', previous: ['A1', 'M1', 'M2'] } | ||
| /* | ||
| We check if there is a cycle in the loop. | ||
| We do this by repeatedly removing nodes that are not part of a cycle, starting from the roots | ||
| { | ||
| A1: { key: 'A1', previous: null }, | ||
| M1: { key: 'M1', previous: [ 'A1', 'M2', 'M3' ] }, | ||
| M2: { key: 'M2', previous: [ 'A1', 'M1', 'M3' ] }, | ||
| M3: { key: 'M3', previous: [ 'A1', 'M1', 'M2' ] } | ||
| } | ||
| { | ||
| M1: [ 'A1', 'M2', 'M3' ], | ||
| M2: [ 'A1', 'M1', 'M3' ], | ||
| M3: [ 'A1', 'M1', 'M2' ] | ||
| } | ||
| { | ||
| M1: [ 'M2', 'M3' ], | ||
| M2: [ 'M1', 'M3' ], | ||
| M3: [ 'M1', 'M2' ] | ||
| } | ||
| When we can't remove any more we have either found a cycle (like above) or shown that none of the nodes are in a loop. | ||
| Note, we only check connected nodes and initially remove any disconnected nodes from previous. | ||
| */ | ||
| const graph = new Graph([A1, M1, M2, M3]) | ||
| t.deepEqual(Object.keys(graph.lookup.connected), ['A1'], 'no cycle in list of connected nodes') | ||
| t.end() | ||
| }) | ||
| test('Cycles (3)', t => { | ||
| // A1 | ||
| // / \ | ||
| // / _ \ | ||
| // B1_B2 | ||
| const A1 = { key: 'A1', previous: null } | ||
| const B1 = { key: 'B1', previous: ['A1', 'B2'] } | ||
| const B2 = { key: 'B2', previous: ['A1', 'B1'] } | ||
| const graph = new Graph([A1, B1, B2]) | ||
| // t.throws(() => new Graph([A1, B1, B2]), /there is a cycle in connected nodes/, 'new Circular Graph') | ||
| t.equal(graph.isBranchNode('A1'), false, 'The root branches to a loop') | ||
| t.equal(graph.isTipNode('A1'), true, 'The loop is semiconnected') | ||
| t.end() | ||
| }) |
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by36.61%
43231
- Number of package files
- increased by6.67%
16
- Lines of code
- increased by34.32%
1092
No dependency changes