Simple graph + walker

index.mjs

import graphlib from 'graphlib'
import { Walker } from './walk.mjs'

const { Graph, json } = graphlib

const graph = new Graph({ directed: true })

/*                          ┌───┐
 *                        ┌▶│ 5 │───┐
 *           ┌───┐  ┌───┐ │ └───┘   │   ┌───┐
 * ┌───┐  ┌─▶│ 2 │─▶│ 4 │─┤         ├──▶│ 8 │
 * │ 1 │──┴┐ └───┘  └───┘ │  ┌───┐  │   └───┘
 * └───┘   │              └─▶│ 6 │──┘     ▲
 *         │                 └───┘        │
 *         │   ┌───┐  ┌───┐               │
 *         └──▶│ 3 │─▶│ 7 │───────────────┘
 *             └───┘  └───┘
 *
 * ┌───┐       ┌───┐
 * │ 0 │──────▶│ 9 │
 * └───┘       └───┘
 */
graph.setEdge(1, 2)
graph.setEdge(1, 3)
graph.setEdge(2, 4)
graph.setEdge(3, 7)
graph.setEdge(4, 5)
graph.setEdge(4, 6)
graph.setEdge(5, 8)
graph.setEdge(6, 8)
graph.setEdge(7, 8)
graph.setEdge(0, 9)

console.log(
  json.write(graph)
)

const walker = new Walker(graph)

walker.walk()
  .then(console.dir)
  .catch(console.error)

walk.mjs

/**
 * This class will walk the graph, executing nodes in parallel when it can
 * @param graph Graphlib object
 */
export class Walker {
  constructor (graph) {
    // this is the graphlib graph
    this.graph = graph

    // keep track of the nodes we've resolved, successfully and failed
    this.results = new Map()
    this.errors = new Map()
  }

  async walk () {
    // find source nodes
    const sources = this.graph.sources()
    console.log('[sources]', sources)

    // start walking graph sources
    const resolveNodes = sources.map(source => this.walkNode(source))
    await Promise.all(resolveNodes)

    return {
      results: this.results,
      errors: this.errors
    }
  }

  async walkNode (node) {
    // find dependencies
    const dependencies = this.graph.predecessors(node)
    console.log('[dependencies] for node', node, dependencies)

    const allDependenciesResolved = dependencies.every(dependency => this.results.has(dependency))
    if (!allDependenciesResolved) {
      console.log('[dependencies] not all dependencies resolved yet for', node, 'skipping...')
      return null
    }

    try {
      const result = await this.runNode(node)
      this.results.set(node, result)
    } catch (err) {
      this.errors.set(node, err)
    }

    // find successors
    const successors = this.graph.successors(node)
    console.log('[successors] for node', node, successors)

    if (successors.length > 0) {
      const resolveNodes = successors.map(node => this.walkNode(node))
      return Promise.all(resolveNodes)
    }
  }

  async runNode (node) {
    console.log('[running] node', node)
    console.log('[finished] node', node)

    return node
  }
}