Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More
Socket
Socket
Sign inDemoInstall

@tangle/graph

Package Overview
Dependencies
Maintainers
3
Versions
13
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@tangle/graph - npm Package Compare versions

Comparing version 2.1.0 to 3.0.0

test/history.test.js

48

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 = {}) {
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.
constructor (nodes) {
this.nodes = nodes

@@ -22,13 +18,13 @@ this.setupGraph()

this.rootKeys = this.nodes
.filter(node => isRoot(node, this._getBacklinks))
.filter(node => isRoot(node))
.map(node => node.key)
if (this.nodes.length && this.rootKeys.length === 0) error('at least one root node')
if (containsSelfLoop(this.nodes, this._getBacklinks)) throw new Error('there is a selfloop in nodes')
if (containsSelfLoop(this.nodes)) throw new Error('there is a selfloop in nodes')
// build map of each hop which runs forward causally
this.linkMap = new LinkMap(this.nodes, this._getBacklinks)
this.linkMap = new LinkMap(this.nodes)
// and the inverse
this.backlinkMap = new BacklinkMap(this.linkMap)
this.lookup = new Lookup({ nodes: this.nodes, linkMap: this.linkMap, getBacklinks: this._getBacklinks })
this.lookup = new Lookup({ nodes: this.nodes, linkMap: this.linkMap })

@@ -42,3 +38,3 @@ // if (containsCycles(this.lookup.connected, this._getBacklinks)) throw new Error('there is a cycle in connected nodes')

getLinks (key) {
getNext (key) {
if (!this.lookup.isConnected(key)) return []

@@ -49,8 +45,17 @@

getBacklinks (key) {
// alias
getLinks (key) {
return this.getNext(key)
}
getPrevious (key) {
if (!this.lookup.isConnected(key)) return []
return this.backlinkMap.get(key)
}
// alias
getBacklinks (key) {
return this.getPrevious(key)
}
isBranchNode (key) {

@@ -105,2 +110,15 @@ if (!this.lookup.isConnected(key)) return false

}
getHistory (key) {
const history = []
for (const prevKey of this.getPrevious(key)) {
if (!history.includes(prevKey)) {
history.push(prevKey)
for (const prev of this.getHistory(prevKey)) {
if (!history.includes(prev)) history.push(prev)
}
}
}
return history
}
}

@@ -112,6 +130,6 @@

function containsSelfLoop (nodes, getBacklinks) {
function containsSelfLoop (nodes) {
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
node.previous !== null &&
node.previous.includes(node.key) // There is some node in nodes where node.key is in node.previous
))

@@ -118,0 +136,0 @@ }

const assert = require('assert').strict
module.exports = function isRoot (node, getBacklinks) {
module.exports = function isRoot (node) {
assert(node.key)
return getBacklinks(node) === null
return node.previous === null
}

@@ -23,8 +23,7 @@ const isRoot = require('./lib/is-root')

linkMap,
entryKeys, // optional
getBacklinks = (node) => node.previous // optional
entryKeys // optional
} = opts
if (!entryKeys) {
entryKeys = nodes
.filter(node => isRoot(node, getBacklinks))
.filter(node => isRoot(node))
.map(node => node.key)

@@ -47,4 +46,4 @@ }

// Check if all previous are connected already
if (getBacklinks(this.disconnected[key]) !== null) {
const previousNodesConnected = getBacklinks(this.disconnected[key]).every(previousKey => {
if (this.disconnected[key].previous !== null) {
const previousNodesConnected = this.disconnected[key].previous.every(previousKey => {
return this.connected[previousKey]

@@ -67,3 +66,3 @@ })

Object.values(this.disconnected).forEach(node => {
const previous = getBacklinks(node)
const previous = node.previous
if (previous === null) return // isRoot

@@ -70,0 +69,0 @@

@@ -9,9 +9,9 @@ const set = require('lodash.set')

module.exports = class LinkMap extends BaseMap {
constructor (nodes, getBacklinks) {
constructor (nodes) {
super()
nodes
.filter(node => !isRoot(node, getBacklinks))
.filter(node => !isRoot(node))
.forEach(node => {
getBacklinks(node).forEach(backlink => {
node.previous.forEach(backlink => {
set(this.map, [backlink, node.key], 1)

@@ -23,3 +23,3 @@ })

this.entryKeys = nodes
.filter(node => isRoot(node, getBacklinks))
.filter(node => isRoot(node))
.map(node => node.key)

@@ -26,0 +26,0 @@

{
"name": "@tangle/graph",
"version": "2.1.0",
"version": "3.0.0",
"description": "a helper for building + updating traverseable tangle graphs",

@@ -31,4 +31,4 @@ "main": "index.js",

"devDependencies": {
"@tangle/test": "^1.2.0",
"faucet": "0.0.1",
"lodash.get": "^4.4.2",
"standard": "^16.0.3",

@@ -35,0 +35,0 @@ "tape": "^5.0.1"

# @tangle/graph
A module which allows you to build a simple graph, and provides simple helper
A module which allows you to build a simple graph, and provides simple helper
methods for modifying an querying that graph.

@@ -20,19 +20,31 @@

key: 'A',
comment: 'What shall we have for dinner?',
previous: null // << signals this is a rootNode
previous: null, // << signals this is a rootNode
data: {
comment: 'What shall we have for dinner?',
items: { pizza: 1 }
}
},
{
key: 'B',
comment: 'Hows about spaghetti?',
previous: ['A']
previous: ['A'],
data: {
comment: 'Hows about spaghetti?',
items: { spaghetti: 1 }
}
},
{
key: 'C',
comment: 'My only constraint is no wheat.',
previous: ['A']
previous: ['A'],
data: {
comment: 'My only constraint is no wheat.',
items: { wheat: -1 }
}
},
{
key: 'D',
comment: 'Everyone ok with glutten-free spaghetti?',
previous: ['C', 'D']
previous: ['C', 'D'],
data: {
comment: 'Everyone ok with glutten-free spaghetti?',
items: { spaghetti: 1 }
}
}

@@ -48,19 +60,15 @@ ]

### `new Graph(nodes, opts) -> graph`
### `new Graph(nodes) -> graph`
Creates a Graph instance which builds a model of the graph.
Notably builds a graph based on links
where:
Notably builds a graph based on links where:
All of these graph methods assume you're passing in nodes which have :
All of these graph methods assume you're passing in nodes which have :
- a `key` property which is unique
- a `thread` property which stores `root` (key) and `previous` (Array of keys)
- a `previous` property which an array of keys for nodes
that are directly _before_ this key-node in the graph.
- an optional `data` property which can contain anything
In scuttlebutt the keys are the hash addresses of the messages
You can an `opts` Object to some methods:
- `getBacklinks` which takes a node and returns either:
- `[key]` - an Array of keys of nodes that this node was extending from
- `null` - if this was a "root node" (i.e. was the start of a tangle graph)
### `graph.getNode(key) => result`

@@ -71,16 +79,21 @@

- `null` if it's _disconnected_
- `undefined` if it was not in the set of nodes passed in initially
- `undefined` if it was not in the set of nodes passed in
### `graph.isConnected(key) => Boolean`
### `graph.getLinks(key) => [key]`
### `graph.getNext(key) => [key]`
Returns an Array of keys of nodes that are causally linked to this node-key.
These links pointing _forwards_ in time to node _after_ this key-node in the graph.
This contains keys of nodes _after_ this key-node in the graph.
### `graph.getBacklinks(key) => [key]`
(alias: `graph.getLinks`)
Returns an Array of keys of nodes that are causally linked to this node-key.
These links pointing _backwards_ in time to node _before_ this key-node in the graph.
### `graph.getPrevious(key) => [key]`
This returns the `previous` property for a given node.
This contains keys of nodes _before_ this key-node in the graph.
(alias: `graph.getBacklinks`)
### `graph.isBranchNode(key) => Boolean`

@@ -94,3 +107,3 @@

Tells you if 2 or more branches converge in the given node-key.
(basically `graph.getBacklinks(key).length > 1`)
(basically `graph.getPrevious(key).length > 1`)

@@ -101,3 +114,3 @@ ### `graph.isTipNode(key) => Boolean`

i.e. a leading tip causally
(basically `graph.getLinks(key).length === 0`)
(basically `graph.getNext(key).length === 0`)

@@ -129,2 +142,7 @@ ### `graph.invalidateKeys(keys)

### `graph.getHistory(key) => [key]`
A function that gets the keys of all nodes earlier in the graph of a given node.
This goes all the way back to the root, not just the directly previous nodes.
---

@@ -135,3 +153,2 @@

this is expected to be used with DAGs (directed acyclic graphs),
but there is currently no internal check built to guarentee this
but there is currently no internal check built to guarantee this

@@ -23,3 +23,2 @@ const test = require('tape')

const graph = new Graph([A, B, C, D, W, X])
const getBacklinks = node => node.previous

@@ -64,10 +63,10 @@ graph.addNodes([N, M])

test('addNodes graph.getLinks', t => {
t.deepEqual(graph.getLinks('A'), ['B', 'C'], 'getLinks')
t.deepEqual(graph.getLinks('B'), ['D'], 'getLinks')
t.deepEqual(graph.getLinks('C'), ['D'], 'getLinks')
t.deepEqual(graph.getLinks('W'), [], 'no links for disconnected')
t.deepEqual(graph.getLinks('X'), [], 'no links for disconnected')
t.deepEqual(graph.getLinks('Z'), [], 'no links for exterior')
t.deepEqual(graph.getLinks('N'), [], 'getLinks of semiconnected node')
test('addNodes graph.getNext', t => {
t.deepEqual(graph.getNext('A'), ['B', 'C'], 'getLinks')
t.deepEqual(graph.getNext('B'), ['D'], 'getLinks')
t.deepEqual(graph.getNext('C'), ['D'], 'getLinks')
t.deepEqual(graph.getNext('W'), [], 'no links for disconnected')
t.deepEqual(graph.getNext('X'), [], 'no links for disconnected')
t.deepEqual(graph.getNext('Z'), [], 'no links for exterior')
t.deepEqual(graph.getNext('N'), [], 'getLinks of semiconnected node')

@@ -77,9 +76,9 @@ t.end()

test('addNodes graph.getBacklinks', t => {
test('addNodes graph.getPrevious', t => {
/* getBacklinks */
t.deepEqual(graph.getBacklinks('B'), ['A'], 'getBacklinks')
t.deepEqual(graph.getBacklinks('W'), [], 'no backlinks for disconnected')
t.deepEqual(graph.getBacklinks('X'), [], 'no backlinks for disconnected')
t.deepEqual(graph.getBacklinks('Z'), [], 'no backlinks for exterior')
t.deepEqual(graph.getBacklinks('N'), [], 'getBacklinks of semiconnected node')
t.deepEqual(graph.getPrevious('B'), ['A'], 'getBacklinks')
t.deepEqual(graph.getPrevious('W'), [], 'no backlinks for disconnected')
t.deepEqual(graph.getPrevious('X'), [], 'no backlinks for disconnected')
t.deepEqual(graph.getPrevious('Z'), [], 'no backlinks for exterior')
t.deepEqual(graph.getPrevious('N'), [], 'getBacklinks of semiconnected node')

@@ -145,3 +144,3 @@ t.end()

t.equal(dGraph.getNode('D3'), D3, 'previously disconnected node found')
t.deepEqual(dGraph.getBacklinks('D3'), ['D2'], 'getBacklinks of previously disconnected node')
t.deepEqual(dGraph.getPrevious('D3'), ['D2'], 'getBacklinks of previously disconnected node')

@@ -179,14 +178,2 @@ t.end()

test('addNodes - adding using getBacklinks', t => {
const B1 = { key: 'B1', content: { previous: null, message: 'hello' } }
const B2 = { key: 'B2', content: { previous: ['B1'], message: 'goodbye' } }
const getBacklinks = node => node.content.previous
const bGraph = new Graph([B1], { getBacklinks })
bGraph.addNodes([B2])
t.deepEqual(new Graph([B1, B2], { getBacklinks }), bGraph, 'Using getBacklinks')
t.end()
})
// When testing the speed of addNodes use test.only and increase howManyNodes

@@ -198,3 +185,3 @@ const howManyNodes = 10

test('addNodes - adding lots of nodes', t => {
const graph1 = new Graph([A1], { getBacklinks })
const graph1 = new Graph([A1])
let prev = 'A1'

@@ -209,3 +196,3 @@ let i

const graph2 = new Graph([A1], { getBacklinks })
const graph2 = new Graph([A1])

@@ -212,0 +199,0 @@ const arrayOfNodes = []

@@ -46,8 +46,2 @@ const test = require('tape')

t.throws(
() => new Graph([A, B, C], { getBacklinks: true }),
/getBacklinks is not a function/,
'throws if getBacklinks is invalid'
)
t.end()

@@ -79,6 +73,6 @@ })

test('graph.getLinks', t => {
t.deepEqual(graph.getLinks('A'), ['B', 'C'], 'getLinks')
t.deepEqual(graph.getLinks('W'), [], 'no links for disconnected')
t.deepEqual(graph.getLinks('X'), [], 'no links for disconnected')
t.deepEqual(graph.getLinks('Z'), [], 'no links for exterior')
t.deepEqual(graph.getNext('A'), ['B', 'C'], 'getLinks')
t.deepEqual(graph.getNext('W'), [], 'no links for disconnected')
t.deepEqual(graph.getNext('X'), [], 'no links for disconnected')
t.deepEqual(graph.getNext('Z'), [], 'no links for exterior')

@@ -90,6 +84,6 @@ t.end()

/* getBacklinks */
t.deepEqual(graph.getBacklinks('B'), ['A'], 'getBacklinks')
t.deepEqual(graph.getBacklinks('W'), [], 'no backlinks for disconnected')
t.deepEqual(graph.getBacklinks('X'), [], 'no backlinks for disconnected')
t.deepEqual(graph.getBacklinks('Z'), [], 'no backlinks for exterior')
t.deepEqual(graph.getPrevious('B'), ['A'], 'getBacklinks')
t.deepEqual(graph.getPrevious('W'), [], 'no backlinks for disconnected')
t.deepEqual(graph.getPrevious('X'), [], 'no backlinks for disconnected')
t.deepEqual(graph.getPrevious('Z'), [], 'no backlinks for exterior')

@@ -143,5 +137,5 @@ t.end()

t.deepEqual(graph.getNode('D'), null, 'pruned node children not accessible')
t.deepEqual(graph.getLinks('A'), ['C'], 'updated links after prune')
t.deepEqual(graph.getLinks('B'), [], 'updated links after prune')
t.deepEqual(graph.getLinks('C'), [], 'updated links after prune')
t.deepEqual(graph.getNext('A'), ['C'], 'updated links after prune')
t.deepEqual(graph.getNext('B'), [], 'updated links after prune')
t.deepEqual(graph.getNext('C'), [], 'updated links after prune')

@@ -161,5 +155,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'), [], '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.
t.deepEqual(new Graph([A1, J]).getPrevious('J'), [], 'getPrevious for semiconnected')
t.deepEqual(new Graph([A1, J]).isMergeNode('J'), false, 'missing node in graph so not a a mergeNode')

@@ -201,5 +194,5 @@ t.end()

)
t.true(new Graph([node], { getBacklinks: m => m.value.content.tangles.profile.previous }), 'can create a graph with a big node')
// t.true(new Graph([node], { getBacklinks: m => m.value.content.tangles.profile.previous }), 'can create a graph with a big node')
t.end()
})
const test = require('tape')
const get = require('lodash.get')
const { LinkMap } = require('../maps')
const getBacklinks = node => node.thread.previous
// NOTE - many of these examples were written in a time when we had getThread
// instead of getPrevious. I've not bothered to make these tests simpler,
// instead have used built-in ability to custom set getBacklinks :)
test('LinkMap: linear', t => {

@@ -17,5 +11,5 @@ // A (root)

const A = { key: 'A', thread: { root: null, previous: null } }
const B = { key: 'B', thread: { root: 'A', previous: ['A'] } }
const C = { key: 'C', thread: { root: 'A', previous: ['B'] } }
const A = { key: 'A', previous: null }
const B = { key: 'B', previous: ['A'] }
const C = { key: 'C', previous: ['B'] }

@@ -27,4 +21,4 @@ const expectedMap = {

t.deepEqual(new LinkMap([A, B, C], getBacklinks).raw, expectedMap, 'simple linear')
t.deepEqual(new LinkMap([C, B], getBacklinks).raw, expectedMap, 'simple linear (order agnostic)')
t.deepEqual(new LinkMap([A, B, C]).raw, expectedMap, 'simple linear')
t.deepEqual(new LinkMap([C, B]).raw, expectedMap, 'simple linear (order agnostic)')

@@ -43,8 +37,8 @@ // ## message in-thread but "dangling" (doesn't link up to known messages)

const A = { key: 'A', thread: { root: null, previous: null } }
const B = { key: 'B', thread: { root: 'A', previous: ['A'] } }
const C = { key: 'C', thread: { root: 'A', previous: ['A'] } }
const D = { key: 'D', thread: { root: 'A', previous: ['B', 'C'] } }
const A = { key: 'A', previous: null }
const B = { key: 'B', previous: ['A'] }
const C = { key: 'C', previous: ['A'] }
const D = { key: 'D', previous: ['B', 'C'] }
const linkMap = new LinkMap([A, D, B, C], getBacklinks)
const linkMap = new LinkMap([A, D, B, C])
const expectedMap = {

@@ -70,6 +64,6 @@ A: { B: 1, C: 1 },

const A = { key: 'A', thread: { root: null, previous: null } }
const B = { key: 'B', thread: { root: 'A', previous: ['A'] } }
const C = { key: 'C', thread: { root: 'A', previous: ['B'] } }
const K = { key: 'K', thread: { root: 'A', previous: ['J'] } }
const A = { key: 'A', previous: null }
const B = { key: 'B', previous: ['A'] }
const C = { key: 'C', previous: ['B'] }
const K = { key: 'K', previous: ['J'] }

@@ -81,3 +75,3 @@ const expectedMap = {

}
t.deepEqual(new LinkMap([A, B, C, K], getBacklinks).raw, expectedMap, 'dangles')
t.deepEqual(new LinkMap([A, B, C, K]).raw, expectedMap, 'dangles')

@@ -94,6 +88,6 @@ t.end()

const A = { key: 'A', thread: { root: null, previous: null } }
const B = { key: 'B', thread: { root: 'A', previous: ['A'] } }
const C = { key: 'C', thread: { root: 'A', previous: ['B'] } }
const Q = { key: 'Q', thread: { root: 'R', previous: ['S'] } }
const A = { key: 'A', previous: null }
const B = { key: 'B', previous: ['A'] }
const C = { key: 'C', previous: ['B'] }
const Q = { key: 'Q', previous: ['S'] }

@@ -106,3 +100,3 @@ const expectedMap = {

t.deepEqual(new LinkMap([A, B, C, Q], getBacklinks).raw, expectedMap, 'out of thread messages')
t.deepEqual(new LinkMap([A, B, C, Q]).raw, expectedMap, 'out of thread messages')
t.end()

@@ -122,11 +116,11 @@ })

const A = { key: 'A', thread: { root: null, previous: null } }
const B = { key: 'B', thread: { root: 'A', previous: ['A'] } }
const C = { key: 'C', thread: { root: 'A', previous: ['A'] } }
const D = { key: 'D', thread: { root: 'A', previous: ['B'] } }
const E = { key: 'E', thread: { root: 'A', previous: ['C'] } }
const F = { key: 'F', thread: { root: 'A', previous: ['C'] } }
const H = { key: 'H', thread: { root: 'A', previous: ['D', 'E'] } }
const G = { key: 'G', thread: { root: 'A', previous: ['F'] } }
const I = { key: 'I', thread: { root: 'A', previous: ['H'] } }
const A = { key: 'A', previous: null }
const B = { key: 'B', previous: ['A'] }
const C = { key: 'C', previous: ['A'] }
const D = { key: 'D', previous: ['B'] }
const E = { key: 'E', previous: ['C'] }
const F = { key: 'F', previous: ['C'] }
const H = { key: 'H', previous: ['D', 'E'] }
const G = { key: 'G', previous: ['F'] }
const I = { key: 'I', previous: ['H'] }

@@ -143,3 +137,3 @@ const expectedMap = {

t.deepEqual(new LinkMap([A, B, C, C, D, E, F, G, G, H, I], getBacklinks).raw, expectedMap, 'ugly graph')
t.deepEqual(new LinkMap([A, B, C, C, D, E, F, G, G, H, I]).raw, expectedMap, 'ugly graph')

@@ -154,10 +148,5 @@ t.end()

const A = {
key: 'A',
threads: {
gathering: { root: null, previous: null }
}
}
const B = { key: 'B', threads: { gathering: { root: 'A', previous: ['A'] } } }
const C = { key: 'C', threads: { gathering: { root: 'A', previous: ['A'] } } }
const A = { key: 'A', previous: null }
const B = { key: 'B', previous: ['A'] }
const C = { key: 'C', previous: ['A'] }

@@ -168,4 +157,3 @@ const expectedMap = {

const getBacklinks = node => get(node, 'threads.gathering.previous')
t.deepEqual(new LinkMap([A, B, C], getBacklinks).raw, expectedMap, 'custom thread path')
t.deepEqual(new LinkMap([A, B, C]).raw, expectedMap, 'custom thread path')

@@ -197,5 +185,4 @@ t.end()

]
const getBacklinks = node => node.previous
return new LinkMap(nodes, getBacklinks)
return new LinkMap(nodes)
}

@@ -202,0 +189,0 @@

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc