Skip to content

Instantly share code, notes, and snippets.

@thejmazz

thejmazz/README.md

Last active June 17, 2018 03:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save thejmazz/c52b6226df0360ffb8e8f25150bbdcaa to your computer and use it in GitHub Desktop.
Save thejmazz/c52b6226df0360ffb8e8f25150bbdcaa to your computer and use it in GitHub Desktop.
Download ZIP
Protype Procedural DAG API
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<style>
html {
height: 100%;
}
body {
margin: 0;
height: 100%;
}
#cy {
width: 100%;
height: 100%;
}
</style>
<script src="https://cdnjs.cloudflare.com/ajax/libs/cytoscape/3.2.13/cytoscape.min.js"></script>
<script src="https://dagrejs.github.io/project/graphlib/latest/graphlib.min.js"></script>
</head>
<body>
<div id="cy"></div>
<script src="main.js"></script>
</body>
</html>
Raw
main.js
window.cy = cytoscape({
container: document.getElementById('cy'),
elements: [
// { data: { id: 'A' } },
// { data: { id: 'B' } },
// { data: { id: 'AB', source: 'A', target: 'B' } },
],
style: [
{
selector: 'node',
style: {
'background-color': '#666',
'label': 'data(id)'
}
},
{
selector: 'edge',
style: {
'curve-style': 'bezier',
'width': 3,
'line-color': '#ccc',
'target-arrow-color': '#ccc',
'target-arrow-shape': 'triangle',
'target-arrow-fill': 'filled'
}
}
],
layout: {
name: 'breadthfirst'
}
})
// const nodes = []
// const edges = []
// const join = function(...items) {
// const ids = []
// items.forEach((item) => {
// if (typeof(item) === 'string') {
// // Node id
// if (nodes.indexOf(item) === -1) {
// cy.add({ data: { id: item } })
// nodes.push(item)
// }
// ids.push(item)
// } else if (Array.isArray(item)) {
// console.log('An array!')
// ids.push(item[0])
// } else if (items.join) {
// }
// })
// // console.log(ids)
// for (let i = 0; i < ids.length - 1; i++) {
// const source = ids[i]
// const target = ids[i+1]
// const id = `${source}${target}`
// cy.add({ data: { id, source, target } })
// edges.push(id)
// }
// return { join: true, ids }
// }
// const join = function(items) {
// const ids = []
// // Recurse until items is a plain array of ids
// let plain = true
// items.forEach((item) => {
// if (Array.isArray(item)) {
// plain = false
// const nested = join(item)
// ids.push([ nested[0], nested[nested.length - 1] ])
// } else {
// ids.push(item)
// }
// })
// for (let i = 0; i < ids.length - 1; i++) {
// let source = ids[i]
// let target = ids[i+1]
// if (Array.isArray(source)) {
// source = source[source.length - 1]
// }
// if (Array.isArray(target)) {
// target = target[0]
// }
// for (node of [ source, target ]) {
// if (nodes.indexOf(node) === -1) {
// cy.add({ data: { id: node } })
// nodes.push(node)
// }
// }
// const edgeId = `${source}${target}`
// cy.add({ data: { id: edgeId, source, target } })
// edges.push(edgeId)
// }
// // console.log(ids)
// // ids.forEach((id) => Array.isArray(id) ? null : cy.add({ data: { id } }))
// // for (let i = 0; i < ids.length - 1; i++) {
// // const source = Array.isArray(ids[i]) ? ids[i][1] : ids[i]
// // const target = Array.isArray(ids[i]) ? ids[i][0] : ids[i+1]
// // const id = `${source}${target}`
// // cy.add({ data: { id, source, target } })
// // }
// return ids
// }
// join('A', 'D')
// join('A', 'B', 'C')
// cy.add({ data: { id: 'D' } })
// join('B', 'C')
// join([ 'B', 'C' ])
// join([ 'A', [ 'B', 'C' ] ])
// join([ 'A', [ 'B', 'C' ], 'D' ])
// join('A', [ 'B', 'C' ], 'D')
// join(['A', 'B'], [ 'C', 'D' ])
// join(
// [
// 'A',
// [
// 'D',
// [ 'B', 'C' ]
// ]
// ]
// )
// TODO way to test this against hardcoded DAG
// fan can return list of ids
// join(
// 'A',
// fan(
// 'D',
// join('B', 'C')
// )
// )
// join(
// 'A',
// [
// 'D',
// [ 'B', 'C' ]
// ]
// )
// join(
// 'A',
// [
// 'D',
// join('B', 'C') // [ 'B', 'C']
// ]
// )
// const g = new graphlib.Graph({
// directed: true,
// multigraph: false,
// compound: false
// })
const getPairs = (arr) => arr.reduce((sum, item, i) => {
if (i < arr.length - 1) {
return [ ...sum, [ arr[i], arr[i+1] ] ]
} else {
return sum
}
}, [])
// console.log(getPairs([ 'A', 'B', 'C' ]))
// const join = (a, b) => {
// g.setEdge(a, b)
// }
// const join = (...items) => {
// getPairs(items).forEach((pair) => {
// g.setEdge(pair[0], pair[1])
// })
// // quick hack
// return items[0]
// }
// Need getRoots, getLeaves
// .sources() and .sinks()
// const fan = (src, targets) => {
// targets.forEach((target) => {
// g.setEdge(src, target)
// })
// }
// join('A', 'B')
// join('A', 'C', 'D')
// fan('A', [ 'B', 'C' ])
// fan(
// 'A',
// [
// join('B', 'C'),
// 'D'
// ]
// )
window.node = function (id) {
const graph = new graphlib.Graph({
directed: true,
multigraph: false,
compound: true
})
graph.setNode(id)
return graph
}
window.n = window.node
window.join = function(...items) {
items = items.map((item) => {
if (typeof(item) === 'string') {
return node(item)
} else {
return item
}
})
// Assumes each item is an individual node
const graph = new graphlib.Graph({
directed: true,
multigraph: false,
compound: true
})
getPairs(items).forEach(([ src, trg ]) => {
console.log('Src nodes:', src.nodes())
console.log('Src edges:', src.edges())
console.log('Trg nodes:', trg.nodes())
console.log('Trg edges:', trg.edges())
src.nodes().concat(trg.nodes()).forEach((id) => {
console.log(`Setting ${id}`)
graph.setNode(id)
})
src.edges().concat(trg.edges()).forEach(({ v, w }) => {
console.log(`Edge ${v} → ${w}`)
graph.setEdge(v, w)
})
// Assumes one sink and one source
console.log('Src sinks:', src.sinks())
console.log('Trg sources:', trg.sources())
src.sinks().forEach((v) => {
trg.sources().forEach((w) => {
graph.setEdge(v, w)
})
})
// const v = src.sinks()[0]
// const w = trg.sources()[0]
// // NOTE, misses internals!
// graph.setEdge(v, w)
})
return graph
}
// const fan = (src, targets) => {
// targets.forEach((target) => {
// g.setEdge(src, target)
// })
// }
window.fan = function(src, targets) {
// TODO handle multipled sources
src = typeof(src) === 'string' ? node(src) : src
targets = targets.map((item) => {
if (typeof(item) === 'string') {
return node(item)
} else {
return item
}
})
const graph = new graphlib.Graph({
directed: true,
multigraph: false,
compound: true
})
// TODO import targets?
targets.forEach((target) => {
target.nodes().forEach((id) => graph.setNode(id))
target.edges().forEach(({ v, w }) => graph.setEdge(v, w))
})
src.nodes().forEach((id) => graph.setNode(id))
src.edges().forEach(({ v, w }) => graph.setEdge(v, w))
src.sinks().forEach((v) => {
targets.forEach((target) => {
target.sources().forEach((w) => {
graph.setEdge(v, w)
})
})
})
return graph
}
// check if graph.children(<id>).length === 0
// use compound graph for fork() support
window.render = function (g) {
// These still exist in memory...
cy.elements().remove()
g.nodes().forEach(id => cy.add({ data: { id } }))
g.edges().forEach(({ v: source, w: target }) => {
return cy.add({ data: { source, target } })
})
cy.layout({ name: 'breadthfirst' }).run()
}
window.printEdges = function (graph) {
return graph.edges().map(({ v, w }) => `${v} → ${w}`)
}
window.getChildNodes = function (graph) {
return graph.nodes()
.filter(id => graph.parent(id))
.map(id => `${id} ∊ ${graph.parent(id)}`)
}
// render(join('A', join('B', 'C'), 'D'))
// render(join('A', fan('B', [ 'C', 'D' ])))
// render(join('A', fan('B', [ join('C', 'D'), 'E' ])))
render(
join(
join(
'A',
fan(
'B',
[
join('C', fan('D', [ 'E', join('F', 'G') ])),
'H'
]
)
),
'I'
)
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment