@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 graph
• null if it's disconnected
• undefined 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