Skip to content

Instantly share code, notes, and snippets.

@saraquigley saraquigley/.block

Created Nov 14, 2017
Embed
What would you like to do?
Knowledge tree DSL
license: mit

An example of a Domain-Specific Language for the definition of small knowledge graphs, building on the tangled tree language.

Indentation is used to define a hierarchy of nodes (black) and links (red). Links can be inverted by using < or >.

Three types of links have a special meaning: isA is used to define superclass-subclass relationships, instanceOf links an instance to its class, and denotes links a linguistic term to the concept it stands for.

(Needs cleanup: part of the code for the temporal knowledge graph is still included).

forked from nitaku's block: Knowledge tree DSL

window.AppView = Backbone.D3View.extend
initialize: () ->
# retrieve the grammar from an external file
d3.text 'knowledge.peg.js', (grammar) =>
editor = new Editor
model: @model
grammar: grammar
@el.appendChild(editor.el)
editor.render()
node_link = new NodeLink
model: @model
@el.appendChild(node_link.el)
node_link.render()
// Generated by CoffeeScript 1.10.0
(function() {
window.AppView = Backbone.D3View.extend({
initialize: function() {
return d3.text('knowledge.peg.js', (function(_this) {
return function(grammar) {
var editor, node_link;
editor = new Editor({
model: _this.model,
grammar: grammar
});
_this.el.appendChild(editor.el);
editor.render();
node_link = new NodeLink({
model: _this.model
});
_this.el.appendChild(node_link.el);
return node_link.render();
};
})(this));
}
});
}).call(this);
// Backbone.D3View.js 0.3.1
// ---------------
// (c) 2015 Adam Krebs
// Backbone.D3View may be freely distributed under the MIT license.
// For all details and documentation:
// https://github.com/akre54/Backbone.D3View
(function (factory) {
if (typeof define === 'function' && define.amd) { define(['backbone', 'd3'], factory);
} else if (typeof exports === 'object') { module.exports = factory(require('backbone'), require('d3'));
} else { factory(Backbone, d3); }
}(function (Backbone, d3) {
// Cached regex to match an opening '<' of an HTML tag, possibly left-padded
// with whitespace.
var paddedLt = /^\s*</;
var ElementProto = (typeof Element !== 'undefined' && Element.prototype) || {};
var matchesSelector = ElementProto.matches ||
ElementProto.webkitMatchesSelector ||
ElementProto.mozMatchesSelector ||
ElementProto.msMatchesSelector ||
ElementProto.oMatchesSelector;
Backbone.D3ViewMixin = {
// A reference to the d3 selection backing the view.
d3el: null,
namespace: d3.ns.prefix.svg,
$: function(selector) {
return this.el.querySelectorAll(selector);
},
$$: function(selector) {
return this.d3el.selectAll(selector);
},
_removeElement: function() {
this.undelegateEvents();
this.d3el.remove();
},
_createElement: function(tagName) {
var ns = typeof this.namespace === 'function' ? this.namespace() : this.namespace;
return ns ?
document.createElementNS(ns, tagName) :
document.createElement(tagName);
},
_setElement: function(element) {
if (typeof element == 'string') {
if (paddedLt.test(element)) {
var el = document.createElement('div');
el.innerHTML = element;
this.el = el.firstChild;
} else {
this.el = document.querySelector(element);
}
} else {
this.el = element;
}
this.d3el = d3.select(this.el);
},
_setAttributes: function(attributes) {
this.d3el.attr(attributes);
},
// `delegate` supports two- and three-arg forms. The `selector` is optional.
delegate: function(eventName, selector, listener) {
if (listener === undefined) {
listener = selector;
selector = null;
}
var view = this;
var wrapped = function(event) {
var node = event.target,
idx = 0,
o = d3.event;
d3.event = event;
// The `event` object is stored in `d3.event` but Backbone expects it as
// the first argument to the listener.
if (!selector) {
listener.call(view, d3.event, node.__data__, idx++);
d3.event = o;
return;
}
while (node && node !== view.el) {
if (matchesSelector.call(node, selector)) {
listener.call(view, d3.event, node.__data__, idx++);
}
node = node.parentNode;
}
d3.event = o;
};
var map = this._domEvents || (this._domEvents = {});
var handlers = map[eventName] || (map[eventName] = []);
handlers.push({selector: selector, listener: listener, wrapped: wrapped});
this.el.addEventListener(eventName, wrapped, false);
return this;
},
undelegate: function(eventName, selector, listener) {
if (!this._domEvents || !this._domEvents[eventName]) return;
if (typeof selector !== 'string') {
listener = selector;
selector = null;
}
var handlers = this._domEvents[eventName].slice();
var i = handlers.length;
while (i--) {
var handler = handlers[i];
var match = (listener ? handler.listener === listener : true) &&
(selector ? handler.selector === selector : true);
if (!match) continue;
this.el.removeEventListener(eventName, handler.wrapped, false);
this._domEvents[eventName].splice(i, 1);
}
},
undelegateEvents: function() {
var map = this._domEvents, el = this.el;
if (!el || !map) return;
Object.keys(map).forEach(function(eventName) {
map[eventName].forEach(function(handler) {
el.removeEventListener(eventName, handler.wrapped, false);
});
});
this._domEvents = {};
return this;
}
};
Backbone.D3View = Backbone.View.extend(Backbone.D3ViewMixin);
return Backbone.D3View;
}));
window.Editor = Backbone.D3View.extend
namespace: null
tagName: 'div'
initialize: (conf) ->
@d3el.classed 'Editor', true
# Chrome bug workaround (https://github.com/codemirror/CodeMirror/issues/3679)
editor_div = @d3el.append 'div'
.attr
class: 'editor_div'
.style
position: 'relative'
wrapper = editor_div.append 'div'
.style
position: 'absolute'
height: '100%'
width: '100%'
@status_bar = @d3el.append 'div'
.attr
class: 'status_bar'
@parser = PEG.buildParser conf.grammar
@editor = CodeMirror wrapper.node(), {
lineNumbers: true,
lineWrapping: true,
keyMap: 'sublime',
value: '''
# concept hierarchy
CelestialBody
<isA
FixedStar
WanderingStar
<isA
GalileanMoon
<instanceOf
Io
Europa
Ganimede
Callisto
<instanceOf
Jupiter
# terminology
Term
<isA
AstronomicalTerm
<instanceOf
stella
denotes>
CelestialBody
stellula
denotes>
CelestialBody
inerrans_stella
denotes>
FixedStar
stella_vagans
denotes>
WanderingStar
planeta
denotes>
WanderingStar
Iuppiter
denotes>
Jupiter
# other relations
Jupiter
<revolvesAround
Io
Europa
Ganimede
Callisto
'''
extraKeys: {
Tab: (cm) ->
# replace tab with spaces
if cm.somethingSelected()
cm.indentSelection('add')
else
cm.replaceSelection(Array(cm.getOption('indentUnit') + 1).join(' '), 'end', '+input')
}
}
@editor.on 'change', () =>
@compile()
@compile()
render: () ->
@editor.refresh()
compile: () ->
@status_bar.text 'All ok.'
@status_bar.classed 'error', false
try
graph = @parser.parse @editor.getValue()
@highlight_code graph
@model.update graph
catch e
@status_bar.text "Line #{e.location.start.line}: #{e.message}"
@status_bar.classed 'error', true
highlight_code: (graph) ->
# clear highlighting
@editor.getAllMarks().forEach (mark) ->
mark.clear()
graph.nodes.forEach (d) =>
cl = d.code_location
if not d.dummy
@editor.markText {line: cl.start.line-1, ch: cl.start.column-1}, {line: cl.end.line-1, ch: cl.end.column-1}, {className: 'node_def'}
graph.node_refs.forEach (d) =>
cl = d.code_location
@editor.markText {line: cl.start.line-1, ch: cl.start.column-1}, {line: cl.end.line-1, ch: cl.end.column-1}, {className: 'node_ref'}
graph.links.forEach (d) =>
cl = d.code_location
if not d.source.dummy
@editor.markText {line: cl.start.line-1, ch: cl.start.column-1}, {line: cl.end.line-1, ch: cl.end.column-1}, {className: 'link'}
graph.comments.forEach (d) =>
cl = d.code_location
@editor.markText {line: cl.start.line-1, ch: cl.start.column-1}, {line: cl.end.line-1, ch: cl.end.column-1}, {className: 'comment'}
.Editor {
display: flex;
flex-direction: column;
}
.Editor .editor_div {
flex-grow: 1;
height: 0;
}
.Editor .CodeMirror {
height: 100%;
font-size: 12px;
line-height: 1.3;
color: #999;
background: #FFF;
}
.Editor .status_bar {
height: 22px;
background: #DDD;
border-top: 1px solid gray;
font-family: sans-serif;
font-size: 12px;
padding: 4px;
box-sizing: border-box;
}
.Editor .error {
background: #F77;
}
.Editor .node_def {
color: black;
}
.Editor .node_ref {
color: black;
font-style: italic;
}
.Editor .link {
color: #905050;
}
.Editor .comment {
color: #509050;
font-style: italic;
}
// Generated by CoffeeScript 1.10.0
(function() {
window.Editor = Backbone.D3View.extend({
namespace: null,
tagName: 'div',
initialize: function(conf) {
var editor_div, wrapper;
this.d3el.classed('Editor', true);
editor_div = this.d3el.append('div').attr({
"class": 'editor_div'
}).style({
position: 'relative'
});
wrapper = editor_div.append('div').style({
position: 'absolute',
height: '100%',
width: '100%'
});
this.status_bar = this.d3el.append('div').attr({
"class": 'status_bar'
});
this.parser = PEG.buildParser(conf.grammar);
this.editor = CodeMirror(wrapper.node(), {
lineNumbers: true,
lineWrapping: true,
keyMap: 'sublime',
value: '# concept hierarchy\nCelestialBody\n <isA\n FixedStar\n WanderingStar\n <isA\n GalileanMoon\n <instanceOf\n Io\n Europa\n Ganimede\n Callisto\n <instanceOf\n Jupiter\n\n# terminology\nTerm\n <isA\n AstronomicalTerm\n <instanceOf\n stella\n denotes>\n CelestialBody\n stellula\n denotes>\n CelestialBody\n inerrans_stella\n denotes>\n FixedStar\n stella_vagans\n denotes>\n WanderingStar\n planeta\n denotes>\n WanderingStar\n Iuppiter\n denotes>\n Jupiter\n\n# other relations\nJupiter\n <revolvesAround\n Io\n Europa\n Ganimede\n Callisto',
extraKeys: {
Tab: function(cm) {
if (cm.somethingSelected()) {
return cm.indentSelection('add');
} else {
return cm.replaceSelection(Array(cm.getOption('indentUnit') + 1).join(' '), 'end', '+input');
}
}
}
});
this.editor.on('change', (function(_this) {
return function() {
return _this.compile();
};
})(this));
return this.compile();
},
render: function() {
return this.editor.refresh();
},
compile: function() {
var e, error, graph;
this.status_bar.text('All ok.');
this.status_bar.classed('error', false);
try {
graph = this.parser.parse(this.editor.getValue());
this.highlight_code(graph);
return this.model.update(graph);
} catch (error) {
e = error;
this.status_bar.text("Line " + e.location.start.line + ": " + e.message);
return this.status_bar.classed('error', true);
}
},
highlight_code: function(graph) {
this.editor.getAllMarks().forEach(function(mark) {
return mark.clear();
});
graph.nodes.forEach((function(_this) {
return function(d) {
var cl;
cl = d.code_location;
if (!d.dummy) {
return _this.editor.markText({
line: cl.start.line - 1,
ch: cl.start.column - 1
}, {
line: cl.end.line - 1,
ch: cl.end.column - 1
}, {
className: 'node_def'
});
}
};
})(this));
graph.node_refs.forEach((function(_this) {
return function(d) {
var cl;
cl = d.code_location;
return _this.editor.markText({
line: cl.start.line - 1,
ch: cl.start.column - 1
}, {
line: cl.end.line - 1,
ch: cl.end.column - 1
}, {
className: 'node_ref'
});
};
})(this));
graph.links.forEach((function(_this) {
return function(d) {
var cl;
cl = d.code_location;
if (!d.source.dummy) {
return _this.editor.markText({
line: cl.start.line - 1,
ch: cl.start.column - 1
}, {
line: cl.end.line - 1,
ch: cl.end.column - 1
}, {
className: 'link'
});
}
};
})(this));
return graph.comments.forEach((function(_this) {
return function(d) {
var cl;
cl = d.code_location;
return _this.editor.markText({
line: cl.start.line - 1,
ch: cl.start.column - 1
}, {
line: cl.end.line - 1,
ch: cl.end.column - 1
}, {
className: 'comment'
});
};
})(this));
}
});
}).call(this);
window.Graph = Backbone.Model.extend
defaults:
graph: {
dummy_root: null
nodes: []
links: []
node_refs: []
comments: []
}
update: (graph) ->
# compute link ids and mark links as directed
graph.links.forEach (l) ->
l.directed = true
dir = if l.inverse then '<-' else '->'
l.id = l.source.id + dir + l.full_name + dir + l.target.id
# infer node types from links
# FIXME this is a limited solution
if l.full_name is 'isA'
l.target.class = 'class'
l.source.class = 'class'
else if l.full_name is 'instanceOf'
if not l.inverse
l.target.class = 'class'
l.source.class = 'instance'
else
l.source.class = 'class'
l.target.class = 'instance'
# FIXME dirty hack
if l.source.id is 'Term'
l.target.class = 'term'
else if l.full_name is 'denotes'
if not l.inverse
l.source.class = 'term'
else
l.target.class = 'term'
@set 'graph', graph
// Generated by CoffeeScript 1.10.0
(function() {
window.Graph = Backbone.Model.extend({
defaults: {
graph: {
dummy_root: null,
nodes: [],
links: [],
node_refs: [],
comments: []
}
},
update: function(graph) {
graph.links.forEach(function(l) {
var dir;
l.directed = true;
dir = l.inverse ? '<-' : '->';
l.id = l.source.id + dir + l.full_name + dir + l.target.id;
if (l.full_name === 'isA') {
l.target["class"] = 'class';
return l.source["class"] = 'class';
} else if (l.full_name === 'instanceOf') {
if (!l.inverse) {
l.target["class"] = 'class';
l.source["class"] = 'instance';
} else {
l.source["class"] = 'class';
l.target["class"] = 'instance';
}
if (l.source.id === 'Term') {
return l.target["class"] = 'term';
}
} else if (l.full_name === 'denotes') {
if (!l.inverse) {
return l.source["class"] = 'term';
} else {
return l.target["class"] = 'term';
}
}
});
return this.set('graph', graph);
}
});
}).call(this);
app = new AppView
el: 'body'
model: new Graph
html, body {
margin: 0;
padding: 0;
width: 100%;
height: 100%;
overflow: hidden;
}
body {
display: flex;
flex-direction: row;
}
.editor {
display: none;
width: 0;
flex-grow: 2;
border-right: 2px solid gray;
}
.node_link {
width: 0;
flex-grow: 3;
}
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Knowledge tree DSL</title>
<link rel="stylesheet" href="index.css">
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="/webvis/tmp/peg-0.9.0.min.js"></script>
<script src="https://underscorejs.org/underscore-min.js"></script>
<script src="https://backbonejs.org/backbone-min.js"></script>
<script src="backbone.d3view.js"></script>
<script src="https://marvl.infotech.monash.edu/webcola/cola.v3.min.js"></script>
<script src="tsort.js"></script>
<script src="http://cdnjs.cloudflare.com/ajax/libs/lodash.js/3.10.0/lodash.min.js"></script>
<link type="text/css" href="//cdnjs.cloudflare.com/ajax/libs/codemirror/4.6.0/codemirror.min.css" rel="stylesheet"/>
<script src="//cdnjs.cloudflare.com/ajax/libs/codemirror/4.6.0/codemirror.min.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/codemirror/4.6.0/keymap/sublime.js"></script>
<!-- your views go here -->
<script src="AppView.js"></script>
<script src="Editor.js"></script>
<link rel="stylesheet" href="Editor.css">
<script src="NodeLink.js"></script>
<link rel="stylesheet" href="NodeLink.css">
<!-- your models go here -->
<script src="Graph.js"></script>
</head>
<body>
<script src="index.js"></script>
</body>
</html>
// Generated by CoffeeScript 1.10.0
(function() {
var app;
app = new AppView({
el: 'body',
model: new Graph
});
}).call(this);
{
var prev_indentation = -1;
var node_index = {};
var graph = {
dummy_root: {
id: '',
dummy: true
},
nodes: [],
links: [],
node_refs: [],
comments: []
};
graph.nodes.push(graph.dummy_root);
var stack = [graph.dummy_root];
var frames_index = {};
}
start
= first:Line rest:('\n' Line)* {
var line_list = [first]
.concat(rest.map(function(d){ return d[1]; }))
.filter(function(d){ return d.content != null && d.content.type != 'comment'; });
// Comments
var comment_list = [first]
.concat(rest.map(function(d){ return d[1]; }))
.filter(function(d){ return d.content != null && d.content.type == 'comment'; });
comment_list.forEach(function(d){
graph.comments.push(d.content);
});
// Nodes and Links
line_list.forEach(function(d){
// Nodes
var node;
if(d.content.type == 'node') {
// create node if not already found
if(!node_index.hasOwnProperty(d.content.id)) {
node_index[d.content.id] = d.content;
graph.nodes.push(d.content);
}
else {
// store this node as a reference node
d.definition = node_index[d.content.id];
graph.node_refs.push(d.content);
}
}
// Links
// retrieve the current indentation
var indentation = d.indentation;
// use indentation to create links
var delta = indentation - prev_indentation;
// Check and pop
if(delta > 0) {
// this is a child
if(d.content.type == 'node' && stack[stack.length-1] != stack[0] && stack[stack.length-1].type == 'node') {
throw {
message: 'Missing link',
location: d.content.code_location
};
}
if(d.content.type == 'link' && (stack.length == 1 || stack[stack.length-1].type == 'link')) {
throw {
message: 'Missing node',
location: d.content.code_location
};
}
} else if(delta == 0) {
// this is a sibling
stack.pop();
} else { // delta < 0
// find something with equal indentation
var i;
var found = false;
for(i in stack) {
if(stack[i].indentation == indentation) {
found = true;
break;
}
}
if(!found) {
throw {
message: 'Inconsistent indentation',
location: d.content.code_location
};
}
stack = stack.slice(0,parseInt(i)+1);
if(d.content.type != stack[stack.length-1].content.type) {
throw {
message: 'Expected ' + stack[stack.length-1].content.type + ' at this indentation level.',
location: d.content.code_location
};
}
// this is a sibling node
stack.pop();
}
// Insert
if(d.content.type == 'node' && stack.length >= 3) {
var link = stack[stack.length-1].content;
var source = node_index[stack[stack.length-2].content.id]; // always use the stored reference
var target = node_index[d.content.id]; // always use the stored reference
graph.links.push({
source: source,
target: target,
prefix: link.prefix,
name: link.name,
frames: link.frames,
full_name: (link.prefix != null ? link.prefix+':' : '') + link.name,
inverse: link.inverse,
code_location: link.code_location
});
}
// Dummy links
if(d.content.type == 'node' && stack.length == 1) {
graph.links.push({
source: graph.dummy_root,
target: node_index[d.content.id] // always use the stored reference
});
}
// Push
stack.push(d);
prev_indentation = indentation;
});
graph.frames = Object.keys(frames_index).map(function(d){ return parseInt(d); }).sort(function(a,b){ return a-b; });
// no frames = all frames
graph.nodes.forEach(function(d){
if(d.frames == null) {
d.frames = graph.frames;
}
});
graph.links.forEach(function(d){
if(d.frames == null) {
d.frames = graph.frames;
}
});
return graph;
}
Line 'line'
= w:Whitespace* content:(Comment / Link / Node)? { return {indentation: w.length, content: content}; }
Comment 'comment'
= '#' [^\n]* { return {type: 'comment', code_location: location()}; }
Node 'node'
= p:Prefix? n:Name f:Frames? {
var id;
if(p != null) {
id = p + ':' + n;
}
else {
id = n;
}
return {type: 'node', prefix: p, name: n, id: id, frames: f, code_location: location()};
}
Link 'link'
= p:Prefix? n:Name '>' f:Frames? { return {type: 'link', prefix: p, name: n, frames: f, inverse: false, code_location: location()}; }
/ '<' p:Prefix? n:Name f:Frames? { return {type: 'link', prefix: p, name: n, frames: f, inverse: true, code_location: location()}; }
Prefix 'prefix'
= [_a-zA-Z0-9]+ ':' {
var t = text();
return t.slice(0,t.length-1);
}
Name 'name'
= [_a-zA-Z0-9]+ { return text(); }
Whitespace 'whitespace'
= ' '
Frames 'frames'
= ' ' first:Frame rest:(' ' Frame)* {
var frames = [first].concat(rest.map(function(d){ return d[1]; }));
frames.forEach(function(d){
frames_index[d] = true;
});
return frames;
}
Frame 'frame'
= [0-9]+ { return parseInt(text()); }
/**
* general topological sort
* @author SHIN Suzuki (shinout310@gmail.com)
* @param Array<Array> edges : list of edges. each edge forms Array<ID,ID> e.g. [12 , 3]
*
* @returns Array : topological sorted list of IDs
**/
function tsort(edges) {
var nodes = {}, // hash: stringified id of the node => { id: id, afters: lisf of ids }
sorted = [], // sorted list of IDs ( returned value )
visited = {}; // hash: id of already visited node => true
var Node = function(id) {
this.id = id;
this.afters = [];
};
// 1. build data structures
edges.forEach(function(v) {
var from = v[0], to = v[1];
if (!nodes[from]) nodes[from] = new Node(from);
if (!nodes[to]) nodes[to] = new Node(to);
nodes[from].afters.push(to);
});
// 2. topological sort
Object.keys(nodes).forEach(function visit(idstr, ancestors) {
var node = nodes[idstr],
id = node.id;
// if already exists, do nothing
if (visited[idstr]) return;
if (!Array.isArray(ancestors)) ancestors = [];
ancestors.push(id);
visited[idstr] = true;
node.afters.forEach(function(afterID) {
if (ancestors.indexOf(afterID) >= 0) // if already in ancestors, a closed chain exists.
throw new Error('closed chain : ' + afterID + ' is in ' + id);
visit(afterID.toString(), ancestors.map(function(v) { return v })); // recursive call
});
sorted.unshift(id);
});
return sorted;
}
/**
* TEST
**/
function tsortTest() {
// example 1: success
var edges = [
[1, 2],
[1, 3],
[2, 4],
[3, 4]
];
var sorted = tsort(edges);
console.log(sorted);
// example 2: failure ( A > B > C > A )
edges = [
['A', 'B'],
['B', 'C'],
['C', 'A']
];
try {
sorted = tsort(edges);
}
catch (e) {
console.log(e.message);
}
// example 3: generate random edges
var max = 100, iteration = 30;
function randomInt(max) {
return Math.floor(Math.random() * max) + 1;
}
edges = (function() {
var ret = [], i = 0;
while (i++ < iteration) ret.push( [randomInt(max), randomInt(max)] );
return ret;
})();
try {
sorted = tsort(edges);
console.log("succeeded", sorted);
}
catch (e) {
console.log("failed", e.message);
}
}
// for node.js
if (typeof exports == 'object' && exports === this) {
module.exports = tsort;
if (process.argv[1] === __filename) tsortTest();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.