@tangle/graph

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

const graph = new Graph (nodes)
graph.isMergeNode('D')
// => true

API

new Graph(nodes, opts) -> 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 thread property which stores root (key) and previous (Array of keys)

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

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 initially

graph.isConnected(key) => Boolean

graph.getLinks(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.

graph.getBacklinks(key) => [key]

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.isBrancNode(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.getBacklinks(key).length > 1)

graph.isHeadNode(key) => Boolean

Tells you whether the given node-key belongs to a head of the graph, i.e. a leading tip causally (basically graph.getLinks(key).length === 0)

graph.rootNodeKeys

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)

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.

---

NOTES

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