Hyper DiGraph

Decentralised directed graphs based on hypercore, using hyperbees under the hood.

Warning: alfa status--breaking changes possible until v1 release.

Note: this package is not concerned with requesting the required hyperbees on the network. If a bee is not found, the diGraph will error out when trying to access nodes in that bee.

Support for handling such scenarios will be added.

Install

npm add hyper-digraph

Usage

const { DiGraph } = require('hyper-digraph')
const HyperInterface = require('hyperpubee-hyper-interface')
const ram = require('random-access-memory')
const Corestore = require('corestore')

const corestore = new Corestore(ram)
const hyperInterface = new HyperInterface(corestore)

async function runExample () {
  // Creating a new DiGraph with only an empty root node
  const diGraph = await DiGraph.createNew({
    name: 'My digraph',
    hyperInterface
  })

  // Set the content of a node
  await diGraph.rootNode.setContent('I am the root node')

  // A DiGraph can also be loaded from a compatible hyperbee
  const bee = await hyperInterface.createHyperbee('My other digraph')
  await bee.put(
    'root',
    { content: 'I am the root of the other digraph', children: [{ location: 'aChild' }] }
  )
  await bee.put(
    'aChild',
    { content: 'I am a child of the other digraph', children: [] }
  )
  const otherDiGraph = await DiGraph.loadFromBee(
    { hash: bee.feed.key, hyperInterface }
  )

  // Checks that the bee is indeed a valid digraph
  // (expensive operation: iterates over all children)
  await otherDiGraph.deepValidate()

  console.log(await otherDiGraph.rootNode.getChildren()) // 1 entry at location 'aChild'

  // Add a new local node as child
  const localChild = await diGraph.rootNode.createChild('localChild')
  await localChild.setContent('I am a local child')

  // Add a new remote node to a child
  // (Note: the digraph is extended with this node and all its children)
  await diGraph.rootNode.pushChild({ hash: bee.feed.key, location: 'root' })

  console.log('Yield all nodes from the di-graph (note: no order guarantees')
  for await (const node of diGraph.yieldAllNodesOnce()) {
    console.log(node.beeLocation.toStr(), ': ', (await node.getContent()))
  }
  // Prints something like
  /*
    e363df1564efcbdc4fb70de864f468fbc7414e50b22904235e2b709e879c2555/root :  I am the root node
    e363df1564efcbdc4fb70de864f468fbc7414e50b22904235e2b709e879c2555/localChild :  I am a local child
    8126da769316af7073182b65d6f1f5020da0f40760a2466d5439799eb057cac3/root :  I am the root of the other digraph
    8126da769316af7073182b65d6f1f5020da0f40760a2466d5439799eb057cac3/aChild :  I am a child of the other digraph
  */

  console.log('Walk the di-graph depth-first')
  for await (const node of diGraph.walkDepthFirst()) {
    console.log(node.beeLocation.toStr(), ': ', (await node.getContent()))
  }
  
}

runExample()

Data Model

Nodes are represented as entries of a hyperbee. The key (str) is their location, and the value is JSON which must contain an entry for keys 'children' and 'content' (and may contain arbitrary other keys as well).

Children must be a list of child-objects, where each child object must have a location (str), and may have a hash (hypercore hexadecimal hash) and a version (int).

A child without hash is interpreted as belonging to the same hyperbee as the parent.

A child without version is interpreted as meaning the latest version. Note that the latest version can change over time.

The presence of a child in a node implies the existence of a directed edge from the node to the child.

Using Alternative Node Class

It is possible to specify an alternative node class for a diGraph, by subclassing Node. This is useful if you wish to add additional validation logic, or to define more-fine-grained accessors on a node's content.

Any DiGraph function returning or yielding nodes will use that class, rather than the built-in Node class.

Graphs in Scope

Any directed graph with a single root node can be represented by this module, including trees, graphs with cycles, and graphs with multiple paths to a node.

A single root is assumed because it is easier to reason about. You can transform any graph with multiple root nodes to a graph with a single root by creating a new node with as children all previous roots.

Algorithms

diGraph.yieldAllNodesOnce() efficiently yields all nodes once (ignoring order):

  for await (const node of diGraph.yieldAllNodesOnce()) {
    ...
  }

diGraph.recStepper() is a high-level algorithm which can be used to traverse the digraph in an order of choice, by implementing your own recursive algorithm on top of it. It yields {node, childYielders} pairs, where childYielders contains a function for each child which, if awaited, yields that child node and its own childYielders.

See diGraph.walkDepthFirst() for an example of how to implement an algorithm on top of diGraph.recStepper().

Note that graphs with cycles will keep yielding nodes forever, unless when the latest version of a node is specified (rather than a fixed version), where the cycle can disappear while traversing the graph, if the referenced node is updated.

Note on algorithmic efficiency

The main bottleneck when traversing a decentralised digraph is the time spent fetching remote entries.

Care should be taken not to wait unnecessarily on node-resolution before requesting the next.

When order is unimportant, diGraph.yieldAllNodesOnce() is efficient in the sense that child-entries are always queried asynchronously, even before they are awaited.

Suppose graph

    ROOT
    |   \
    N1-->N2
  / | \    \
N3  N4 N5   N6

Suppose all entries exist on different hyperbees, and that an entry is obtained in 100ms.

Ignoring processing time:

• The algorithm will first query the root.
• After 100ms it yields the ROOT, and knows the location of N1 and N2.
• After 200ms it yields N1 and N2, and knows then location of N3-N6.
• After 300ms it yields N3-N6 (it skips N2 because it was already handled).
• Each additional level adds another 100ms.

Pending Work

Pending work is to facilitate interactions with the network (e.g. hyperswarm), by exposing an event which triggers when a certain hyperbee is needed and not yet available.

Also pending is to store an index in the root node's hyperbee, containing the hashes of all referenced hyperbees (directly or indirectly). This way, the algorithm can immediately start finding peers for all those bees.

Note that this optimisation is not guaranteed to work when referring to the latest version of entries: in a newer version, an entry might now reference children in bees which are not conained in the index (and might no longer be referencing previously indexed bees).