Skip to content

Instantly share code, notes, and snippets.

@gillesdemey
Last active June 27, 2021 16:55
Show Gist options
  • Save gillesdemey/c1522d7721775df11b099b07906098f5 to your computer and use it in GitHub Desktop.
Save gillesdemey/c1522d7721775df11b099b07906098f5 to your computer and use it in GitHub Desktop.
Simple graph + walker
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)
/**
* 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
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment