@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