Dcent Digraph

Algorithms for decentralised directed graphs

Install

npm add dcent-digraph

Usage

You need to define a Node, which must have property uniqueId and method async getChildren.

You can choose to extend BaseNode, but any class which conforms to the above interface will work.

Once the Node is defined, a DiGraph is fully defined by its root node: new DiGraph(rootNode)

See example.js.

API

const diGraph = new DiGraph(rootNode)

Create a new diGraph, with the given rootNode

const root = diGraph.rootNode

Get the root node

const allNodesIterator = diGraph.yieldAllNodesOnce()

Async iterator which efficiently yields all nodes of the diGraph once, without guaranteeing any order.

const depthFirstIterator = diGraph.walkDepthFirst()

Async iterator to walk the diGraph depth-first. Note that this algorithm will enter in an infinite loop if the diGraph contains cycles.

const stepper = diGraph.recStepper()

High-level algorithm which can be used to efficiently 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().

Node API

A Node must adhere to the following interface:

node.uniqueId

An id uniquely identifying the node.

const children = await node.getChildren()

Return an iterable of child nodes.

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.

Note on Algorithmic Efficiency

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

When using diGraph.recStepper() to create your own walking algorithm, 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 remotely, 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.

Had this graph been walked by awaiting node-per-node, it would have taken 700ms (without repetitions) or 900ms (with repetitions).