@tangle/graph
Advanced tools
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() | ||
}) |
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
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
43231
16
1092