graph-difference
find the subgraph between two nodes in a directed acyclic graph
npm install graph-difference
Want to see pretty graphs? Log in now!
4 | downloads in the last week |
8 | downloads in the last month |
Last Published By | |
---|---|
Version | 0.1.0 last updated 7 months ago |
License | BSD |
Keywords | tree |
Dependencies | ancestor, async |
Dependents | histo-revisions |
graph-difference
Find the subgraph difference between two nodes in a directed acyclic graph.
Given a node A
the algorithm finds all nodes that are ancestors of node B
but are not ancestors from node A
.
Example
The graph:
4-5-8-9 11-12
/ \ \ / \
1-2-3---6-7-10-13-14-15-16
var graphDiff = require('graph-difference')
var nodes = {
1: [],
2: [1],
...
15: [12, 14],
16: [15]
}
var readParents = function(id, cb) {
cb(null, nodes[id])
}
graphDiff(5, 7, readParents, function(err, result) {
// result should be [7, 6, 3]
})