@tangle/graph v3.2.0
@tangle/graph
A module which allows you to build a simple graph, and provides simple helper methods for modifying an querying that graph.
Example Usage
const Graph = require('@tangle/graph')
// A (root)
// / \ |
// B C | causality
// \ / V
// D
const nodes = [
{
key: 'A',
previous: null, // << signals this is a rootNode
data: {
comment: 'What shall we have for dinner?',
items: { pizza: 1 }
}
},
{
key: 'B',
previous: ['A'],
data: {
comment: 'Hows about spaghetti?',
items: { spaghetti: 1 }
}
},
{
key: 'C',
previous: ['A'],
data: {
comment: 'My only constraint is no wheat.',
items: { wheat: -1 }
}
},
{
key: 'D',
previous: ['C', 'D'],
data: {
comment: 'Everyone ok with glutten-free spaghetti?',
items: { spaghetti: 1 }
}
}
]
const graph = new Graph (nodes)
graph.isMergeNode('D')
// => true
API
new Graph(nodes) -> graph
Creates a Graph instance which builds a model of the graph. Notably builds a graph based on links where:
All of these graph methods assume you're passing in nodes which have :
- a
key
property which is unique - 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
graph.getNode(key) => result
where result
is:
node
if it's connected within the graphnull
if it's disconnectedundefined
if it was not in the set of nodes passed in
graph.isConnected(key) => Boolean
graph.getNext(key) => [key]
Returns an Array of keys of nodes that are causally linked to this node-key. This contains keys of nodes after this key-node in the graph.
(alias: graph.getLinks
)
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
Tells you whether the graph diverges as you proceed from the given node-key.
(basically graph.getLinks(key).length > 1
)
graph.isMergeNode(key) => Boolean
Tells you if 2 or more branches converge in the given node-key.
(basically graph.getPrevious(key).length > 1
)
graph.isTipNode(key) => Boolean
Tells you whether the given node-key belongs to a tip of the graph,
i.e. a leading tip causally
(basically graph.getNext(key).length === 0
)
`graph.invalidateKeys(keys)
Takes an Array of node keys and prunes them from the graph. Note this also prunes all nodes down-stream of those nodes.
This is an opinion baked into the tangle spec - that a node is only valid if it extends from other valid nodes.
graph.rootNodes => [Node]
A getter which gives you access to an Array of root nodes (i.e. are the starting points of the graph)
graph.rootKeys => [Key]
A getter which gives you access to an Array of keys for nodes which are "roots" within the graph (i.e. are the starting points of the graph)
(alias: graph.rootNodeKeys
)
graph.tipNodes => [Node]
A getter which gives you access to an Array of tip nodes (i.e. are the ending points of the graph)
graph.tipKeys => [Key]
A getter which gives you access to an Array of keys for nodes which are "tips" within the graph (i.e. are the ending points of the graph)
(alias: graph.tipNodeKeys
)
graph.raw
A getter which gives you access to { linkMap, backlinkMap }
.
These are data structures which map the links of the graph in both directions.
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.
NOTES
this is expected to be used with DAGs (directed acyclic graphs), but there is currently no internal check built to guarantee this