@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

``js
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

$3

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

$3

where result is:
- node if it's _connected_ within the graph
- null if it's _disconnected_
- undefined if it was not in the set of nodes passed in

$3

$3

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)

$3

This returns the previous property for a given node.
This contains keys of nodes _before_ this key-node in the graph.

(alias: graph.getBacklinks)

$3

Tells you whether the graph diverges as you proceed from the given node-key.
(basically graph.getLinks(key).length > 1)

$3

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

$3

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)

$3

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.

$3

A getter which gives you access to an Array of root nodes
(i.e. are the starting points of the graph)

$3

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)

$3

A getter which gives you access to an Array of tip nodes
(i.e. are the ending points of the graph)

$3

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)

$3

A getter which gives you access to { linkMap, backlinkMap }`.
These are data structures which map the links of the graph in both directions.

$3

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