# @tangle/graph

3.2.0 • Public • Published

# @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: {
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 graph
• null if it's disconnected
• undefined if it was not in the set of nodes passed in

### 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

## Package Sidebar

### Install

npm i @tangle/graph`

### Repository

gitlab.com/tangle-js/tangle-graph

130

3.2.0

LGPL-3.0-only

51.4 kB

18