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
// Generated by CoffeeScript 1.10.0
(function() {
var app;
app = new AppView({
el: 'body',
model: new Graph
});
}).call(this);
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Knowledge tree DSL</title>
<link rel="stylesheet" href="index.css">
<script src="//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="//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>
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);
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);
R = 20
C = 0.4
ANIMATION_DURATION = 1400
ANIMATION_DELAY = 400
window.NodeLink = Backbone.D3View.extend
tagName: 'svg'
initialize: () ->
@d3el.classed 'node_link', true
# define categorical color scales for links and nodes
@link_color = d3.scale.ordinal()
.range ['#ff7f0e','#9467bd','#8c564b','#1f77b4','#2ca02c','#d62728','#e377c2','#bcbd22','#17becf']
@node_color = d3.scale.ordinal()
.domain ['class','instance','term']
.range ['#ff7f0e','#9467bd','#8c564b','#7f7f7f']
@defs = @d3el.append 'defs'
# append a group for zoomable content
zoomable_layer = @d3el.append('g')
zoom = d3.behavior.zoom()
.scaleExtent([-Infinity,Infinity])
.on 'zoom', () ->
zoomable_layer
.attr
transform: "translate(#{zoom.translate()})scale(#{zoom.scale()})"
@d3el.call(zoom)
# compansate for dummy nodes translation
@graph_layer = zoomable_layer.append 'g'
# create two layers for nodes and links
@links_layer = @graph_layer.append 'g'
@nodes_layer = @graph_layer.append 'g'
# create the legend layer
@legend = @d3el.append 'g'
.attr
class: 'legend'
@legend.append 'rect'
.attr
class: 'legend_box'
throttled_render = _.debounce (() =>
@render()
), 800, {trailing: true}
@listenTo @model, 'change:graph', throttled_render
render: () ->
width = @el.getBoundingClientRect().width
height = @el.getBoundingClientRect().height
@graph_layer
.attr
transform: "translate(0,#{-2*R}) rotate(-10,#{width/2},#{height/2})"
graph = @model.get 'graph'
@graph = graph # FIXME
### extract the Directed Acyclic Graph composed by isA and instanceOf links ###
# TODO abort tangled representation if cycles are found
dag_links = []
dag_nodes_index = {}
graph.links.forEach (d) ->
if d.source.dummy or d.full_name is 'isA' or d.full_name is 'instanceOf'
dag_links.push d
dag_nodes_index[d.source.id] = d.source
dag_nodes_index[d.target.id] = d.target
dag =
nodes: Object.keys(dag_nodes_index).map (k) -> dag_nodes_index[k]
links: dag_links
### store the node index into the node itself ###
for n, i in dag.nodes
n.i = i
### store neighbor nodes into each node ###
for n, i in dag.nodes
n.in_neighbors = []
n.out_neighbors = []
for l in dag.links
l.source.out_neighbors.push l.target
l.target.in_neighbors.push l.source
### compute longest distances ###
topological_order = tsort(dag.links.map (l) -> [l.source.i, l.target.i])
# console.debug 'Topological order: ' + topological_order
for n in dag.nodes
n.longest_dist = -Infinity
# initialize root node
graph.dummy_root.longest_dist = 0
for i in topological_order
n = dag.nodes[i]
for nn in n.out_neighbors
if nn.longest_dist < n.longest_dist+1
nn.longest_dist = n.longest_dist+1
### CONSTRAINTS ###
graph.constraints = []
# sort the nodes in order to have the first indexes equal to the dag ones
graph.nodes.sort (a,b) -> if a.i? and b.i? then a.i-b.i else if a.i? then -1 else 1
### create the alignment contraints ###
levels = _.uniq dag.nodes.map (n) -> n.longest_dist
levels.forEach (depth) ->
graph.constraints.push {
type: 'alignment',
axis: 'y',
offsets: dag.nodes.filter((n) -> n.longest_dist is depth).map (n) -> {
node: n.i,
offset: 0
}
}
PAD_MULTIPLIER = 3.5
### create the position contraints ###
levels.forEach (depth, i) ->
if i < levels.length-1
n1 = _.find dag.nodes, (n) -> n.longest_dist is depth
n2 = _.find dag.nodes, (n) -> n.longest_dist is depth+1
graph.constraints.push {
axis: 'y',
left: n1.i,
right: n2.i,
gap: 2*R
}
# VIS
link_types = d3.map(graph.links, (d) -> d.full_name)
link_types.remove 'undefined'
link_types.remove 'isA'
link_types.remove 'instanceOf'
link_types.remove 'denotes'
link_types = link_types.keys()
link_types = ['isA','instanceOf','denotes'].concat(link_types)
# set the color domain to cover link types
@link_color
.domain link_types
# create a colored arrowhead for each type of link
arrowheads = @defs.selectAll '.arrowhead'
.data link_types, (d) -> d
enter_arrowheads = arrowheads.enter().append 'marker'
.attr
class: 'arrowhead'
id: (d) -> d + '_arrow'
viewBox: '0 0 10 10'
refX: 6.5
refY: 5
orient: 'auto'
enter_arrowheads.append 'path'
.attr
d: 'M0,0 L0,10 L10,5 z'
arrowheads.select 'path'
.attr
fill: (d) => @link_color(d)
arrowheads.exit().remove()
# create a colored arrowhead for each type of link (used by legend)
legend_arrowheads = @defs.selectAll '.legend_arrowhead'
.data link_types, (d) -> d
enter_legend_arrowheads = legend_arrowheads.enter().append 'marker'
.attr
class: 'legend_arrowhead'
id: (d) -> d + '_legend_arrow'
viewBox: '0 0 10 10'
refX: 4
refY: 5
orient: 'auto'
enter_legend_arrowheads.append 'path'
.attr
d: 'M0,0 L0,10 L10,5 z'
legend_arrowheads.select 'path'
.attr
fill: (d) => @link_color(d)
legend_arrowheads.exit().remove()
# configure and populate the legend
legend_width = 200
legend_height = 16*link_types.length+10
@legend
.attr
transform: "translate(#{width-legend_width-10},#{height-legend_height-10})"
@legend.select '.legend_box'
.attr
width: legend_width
height: legend_height
legend_items = @legend.selectAll '.item'
.data link_types, (d) -> d
enter_legend_items = legend_items.enter().append 'g'
.attr
class: 'item'
enter_legend_items.append 'text'
.text (d) -> d
.attr
x: 54
dy: '0.35em'
enter_legend_links = enter_legend_items.append 'g'
.attr
class: (d) -> "link #{d}"
enter_legend_links.append 'line'
.attr
x1: 2
x2: 42
stroke: (d) => @link_color(d)
'marker-end': (d) -> "url(##{d}_legend_arrow)"
legend_items
.attr
transform: (d,i) -> "translate(10,#{13+16*i})"
legend_items.exit()
.remove()
# draw nodes
nodes = @nodes_layer.selectAll '.node'
.data graph.nodes, (d) -> d.id
enter_nodes = nodes.enter().append 'g'
.attr
display: (d) -> if d.dummy then 'none' else null
enter_nodes.append 'circle'
.attr
class: 'bg'
r: R
enter_nodes.append 'circle'
.attr
class: 'fg'
r: R
# draw the label
enter_nodes.append 'text'
.text (d) ->
if d.class is 'term'
d.id.replace /_/g, ' '
else
d.id
.attr
dy: '0.35em'
transform: 'rotate(10)'
nodes
.attr
class: (d) -> "node #{d.class}"
nodes.select '.fg'
.attr
fill: (d) => @node_color(d.class)
nodes.exit()
.remove()
# draw links
links = @links_layer.selectAll '.link'
.data graph.links, (d) -> d.id
enter_links = links
.enter().append 'g'
.attr
class: (d) -> "link #{d.full_name}"
display: (d) -> if d.source.dummy or d.target.dummy then 'none' else null
enter_links.append 'path'
links.select 'path'
.classed 'directed', (d) -> d.directed
.attr
stroke: (d) => @link_color(d.full_name)
'marker-end': (d) -> "url(##{d.full_name}_arrow)"
links.exit()
.remove()
### cola layout ###
graph.nodes.forEach (v) ->
v.width = 5*R
v.height = 3*R
d3cola = cola.d3adaptor()
.size([width, height])
.avoidOverlaps(true)
.linkDistance(70)
.flowLayout('y', 80)
# .constraints(graph.constraints)
.nodes(graph.nodes)
.links(dag.links)
.on 'tick', () ->
# update nodes and links
nodes
.attr('transform', (d) -> "translate(#{d.x},#{d.y})")
links.select 'path'
.attr
d: (d) ->
if not d.inverse
x1 = d.source.x
x2 = d.target.x
y1 = d.source.y
y2 = d.target.y
else
x1 = d.target.x
x2 = d.source.x
y1 = d.target.y
y2 = d.source.y
alpha = Math.atan2(y2-y1, x2-x1)
xr = R*Math.sin alpha
yr = R*Math.cos alpha
if d.full_name is 'isA' or d.full_name is 'instanceOf' # FIXME hardcoded hierarchical links
return "M#{x1+yr} #{y1+xr} L#{x2-yr} #{y2-xr}"
else
h = Math.sqrt(Math.pow(x2-x1,2) + Math.pow(y2-y1,2))
a = C*h*Math.sin alpha
b = C*h*Math.cos alpha
return "M#{x1+xr} #{y1-yr} C#{x1+xr+a} #{y1-yr-b} #{x2+xr+a} #{y2-yr-b} #{x2+xr} #{y2-yr}"
drag = d3cola.drag()
drag.on 'dragstart', () ->
# silence other listener
d3.event.sourceEvent.stopPropagation()
nodes
.call(drag)
d3cola.start(200,30,30)
.node_link .node > circle.bg {
fill: white;
}
.node_link .node > circle.fg {
opacity: 0.4;
stroke: white;
}
.node_link .node > text {
font-family: sans-serif;
text-anchor: middle;
pointer-events: none;
font-size: 12px;
fill: black;
/* text-shadow: -1px -1px white, -1px 1px white, 1px 1px white, 1px -1px white, -1px 0 white, 0 1px white, 1px 0 white, 0 -1px white; */
-webkit-touch-callout: none; /* iOS Safari */
-webkit-user-select: none; /* Chrome/Safari/Opera */
-khtml-user-select: none; /* Konqueror */
-moz-user-select: none; /* Firefox */
-ms-user-select: none; /* IE/Edge */
user-select: none; /* non-prefixed version, currently
not supported by any browser */
}
.node_link .link > * {
stroke-width: 2px;
opacity: 0.3;
fill: none;
}
.node_link .link.isA > *, .node_link .link.instanceOf > * {
stroke-width: 4px;
}
.node_link .class.node > text,
.node_link .instance.node > text
{
font-family: monospace;
font-weight: bold;
}
.node_link .term.node > text {
font-style: italic;
font-family: serif;
font-weight: normal;
font-size: 13px;
}
.node_link .legend_box, .node_link .frame_box {
shape-rendering: crispEdges;
fill: rgba(255,255,255,0.9);
stroke: #DDD;
}
.node_link .legend text {
font-family: monospace;
font-size: 11px;
}
.node_link .frame {
cursor: pointer;
}
.node_link .frame:hover text {
font-weight: bold;
}
.node_link .selected.frame rect {
fill: yellow;
fill-opacity: 0.1;
}
.node_link .frame text {
pointer-events: none;
text-anchor: middle;
font-family: sans-serif;
fill: #333;
font-size: 10px;
-webkit-touch-callout: none; /* iOS Safari */
-webkit-user-select: none; /* Chrome/Safari/Opera */
-khtml-user-select: none; /* Konqueror */
-moz-user-select: none; /* Firefox */
-ms-user-select: none; /* IE/Edge */
user-select: none; /* non-prefixed version, currently
not supported by any browser */
}// Generated by CoffeeScript 1.10.0
(function() {
var ANIMATION_DELAY, ANIMATION_DURATION, C, R;
R = 20;
C = 0.4;
ANIMATION_DURATION = 1400;
ANIMATION_DELAY = 400;
window.NodeLink = Backbone.D3View.extend({
tagName: 'svg',
initialize: function() {
var throttled_render, zoom, zoomable_layer;
this.d3el.classed('node_link', true);
this.link_color = d3.scale.ordinal().range(['#ff7f0e', '#9467bd', '#8c564b', '#1f77b4', '#2ca02c', '#d62728', '#e377c2', '#bcbd22', '#17becf']);
this.node_color = d3.scale.ordinal().domain(['class', 'instance', 'term']).range(['#ff7f0e', '#9467bd', '#8c564b', '#7f7f7f']);
this.defs = this.d3el.append('defs');
zoomable_layer = this.d3el.append('g');
zoom = d3.behavior.zoom().scaleExtent([-Infinity, Infinity]).on('zoom', function() {
return zoomable_layer.attr({
transform: "translate(" + (zoom.translate()) + ")scale(" + (zoom.scale()) + ")"
});
});
this.d3el.call(zoom);
this.graph_layer = zoomable_layer.append('g');
this.links_layer = this.graph_layer.append('g');
this.nodes_layer = this.graph_layer.append('g');
this.legend = this.d3el.append('g').attr({
"class": 'legend'
});
this.legend.append('rect').attr({
"class": 'legend_box'
});
throttled_render = _.debounce(((function(_this) {
return function() {
return _this.render();
};
})(this)), 800, {
trailing: true
});
return this.listenTo(this.model, 'change:graph', throttled_render);
},
render: function() {
var PAD_MULTIPLIER, arrowheads, d3cola, dag, dag_links, dag_nodes_index, drag, enter_arrowheads, enter_legend_arrowheads, enter_legend_items, enter_legend_links, enter_links, enter_nodes, graph, height, i, j, l, legend_arrowheads, legend_height, legend_items, legend_width, len, len1, len2, len3, len4, len5, levels, link_types, links, m, n, nn, nodes, o, p, q, r, ref, ref1, ref2, ref3, ref4, topological_order, width;
width = this.el.getBoundingClientRect().width;
height = this.el.getBoundingClientRect().height;
this.graph_layer.attr({
transform: "translate(0," + (-2 * R) + ") rotate(-10," + (width / 2) + "," + (height / 2) + ")"
});
graph = this.model.get('graph');
this.graph = graph;
/* extract the Directed Acyclic Graph composed by isA and instanceOf links */
dag_links = [];
dag_nodes_index = {};
graph.links.forEach(function(d) {
if (d.source.dummy || d.full_name === 'isA' || d.full_name === 'instanceOf') {
dag_links.push(d);
dag_nodes_index[d.source.id] = d.source;
return dag_nodes_index[d.target.id] = d.target;
}
});
dag = {
nodes: Object.keys(dag_nodes_index).map(function(k) {
return dag_nodes_index[k];
}),
links: dag_links
};
/* store the node index into the node itself */
ref = dag.nodes;
for (i = j = 0, len = ref.length; j < len; i = ++j) {
n = ref[i];
n.i = i;
}
/* store neighbor nodes into each node */
ref1 = dag.nodes;
for (i = m = 0, len1 = ref1.length; m < len1; i = ++m) {
n = ref1[i];
n.in_neighbors = [];
n.out_neighbors = [];
}
ref2 = dag.links;
for (o = 0, len2 = ref2.length; o < len2; o++) {
l = ref2[o];
l.source.out_neighbors.push(l.target);
l.target.in_neighbors.push(l.source);
}
/* compute longest distances */
topological_order = tsort(dag.links.map(function(l) {
return [l.source.i, l.target.i];
}));
ref3 = dag.nodes;
for (p = 0, len3 = ref3.length; p < len3; p++) {
n = ref3[p];
n.longest_dist = -Infinity;
}
graph.dummy_root.longest_dist = 0;
for (q = 0, len4 = topological_order.length; q < len4; q++) {
i = topological_order[q];
n = dag.nodes[i];
ref4 = n.out_neighbors;
for (r = 0, len5 = ref4.length; r < len5; r++) {
nn = ref4[r];
if (nn.longest_dist < n.longest_dist + 1) {
nn.longest_dist = n.longest_dist + 1;
}
}
}
/* CONSTRAINTS */
graph.constraints = [];
graph.nodes.sort(function(a, b) {
if ((a.i != null) && (b.i != null)) {
return a.i - b.i;
} else if (a.i != null) {
return -1;
} else {
return 1;
}
});
/* create the alignment contraints */
levels = _.uniq(dag.nodes.map(function(n) {
return n.longest_dist;
}));
levels.forEach(function(depth) {
return graph.constraints.push({
type: 'alignment',
axis: 'y',
offsets: dag.nodes.filter(function(n) {
return n.longest_dist === depth;
}).map(function(n) {
return {
node: n.i,
offset: 0
};
})
});
});
PAD_MULTIPLIER = 3.5;
/* create the position contraints */
levels.forEach(function(depth, i) {
var n1, n2;
if (i < levels.length - 1) {
n1 = _.find(dag.nodes, function(n) {
return n.longest_dist === depth;
});
n2 = _.find(dag.nodes, function(n) {
return n.longest_dist === depth + 1;
});
return graph.constraints.push({
axis: 'y',
left: n1.i,
right: n2.i,
gap: 2 * R
});
}
});
link_types = d3.map(graph.links, function(d) {
return d.full_name;
});
link_types.remove('undefined');
link_types.remove('isA');
link_types.remove('instanceOf');
link_types.remove('denotes');
link_types = link_types.keys();
link_types = ['isA', 'instanceOf', 'denotes'].concat(link_types);
this.link_color.domain(link_types);
arrowheads = this.defs.selectAll('.arrowhead').data(link_types, function(d) {
return d;
});
enter_arrowheads = arrowheads.enter().append('marker').attr({
"class": 'arrowhead',
id: function(d) {
return d + '_arrow';
},
viewBox: '0 0 10 10',
refX: 6.5,
refY: 5,
orient: 'auto'
});
enter_arrowheads.append('path').attr({
d: 'M0,0 L0,10 L10,5 z'
});
arrowheads.select('path').attr({
fill: (function(_this) {
return function(d) {
return _this.link_color(d);
};
})(this)
});
arrowheads.exit().remove();
legend_arrowheads = this.defs.selectAll('.legend_arrowhead').data(link_types, function(d) {
return d;
});
enter_legend_arrowheads = legend_arrowheads.enter().append('marker').attr({
"class": 'legend_arrowhead',
id: function(d) {
return d + '_legend_arrow';
},
viewBox: '0 0 10 10',
refX: 4,
refY: 5,
orient: 'auto'
});
enter_legend_arrowheads.append('path').attr({
d: 'M0,0 L0,10 L10,5 z'
});
legend_arrowheads.select('path').attr({
fill: (function(_this) {
return function(d) {
return _this.link_color(d);
};
})(this)
});
legend_arrowheads.exit().remove();
legend_width = 200;
legend_height = 16 * link_types.length + 10;
this.legend.attr({
transform: "translate(" + (width - legend_width - 10) + "," + (height - legend_height - 10) + ")"
});
this.legend.select('.legend_box').attr({
width: legend_width,
height: legend_height
});
legend_items = this.legend.selectAll('.item').data(link_types, function(d) {
return d;
});
enter_legend_items = legend_items.enter().append('g').attr({
"class": 'item'
});
enter_legend_items.append('text').text(function(d) {
return d;
}).attr({
x: 54,
dy: '0.35em'
});
enter_legend_links = enter_legend_items.append('g').attr({
"class": function(d) {
return "link " + d;
}
});
enter_legend_links.append('line').attr({
x1: 2,
x2: 42,
stroke: (function(_this) {
return function(d) {
return _this.link_color(d);
};
})(this),
'marker-end': function(d) {
return "url(#" + d + "_legend_arrow)";
}
});
legend_items.attr({
transform: function(d, i) {
return "translate(10," + (13 + 16 * i) + ")";
}
});
legend_items.exit().remove();
nodes = this.nodes_layer.selectAll('.node').data(graph.nodes, function(d) {
return d.id;
});
enter_nodes = nodes.enter().append('g').attr({
display: function(d) {
if (d.dummy) {
return 'none';
} else {
return null;
}
}
});
enter_nodes.append('circle').attr({
"class": 'bg',
r: R
});
enter_nodes.append('circle').attr({
"class": 'fg',
r: R
});
enter_nodes.append('text').text(function(d) {
if (d["class"] === 'term') {
return d.id.replace(/_/g, ' ');
} else {
return d.id;
}
}).attr({
dy: '0.35em',
transform: 'rotate(10)'
});
nodes.attr({
"class": function(d) {
return "node " + d["class"];
}
});
nodes.select('.fg').attr({
fill: (function(_this) {
return function(d) {
return _this.node_color(d["class"]);
};
})(this)
});
nodes.exit().remove();
links = this.links_layer.selectAll('.link').data(graph.links, function(d) {
return d.id;
});
enter_links = links.enter().append('g').attr({
"class": function(d) {
return "link " + d.full_name;
},
display: function(d) {
if (d.source.dummy || d.target.dummy) {
return 'none';
} else {
return null;
}
}
});
enter_links.append('path');
links.select('path').classed('directed', function(d) {
return d.directed;
}).attr({
stroke: (function(_this) {
return function(d) {
return _this.link_color(d.full_name);
};
})(this),
'marker-end': function(d) {
return "url(#" + d.full_name + "_arrow)";
}
});
links.exit().remove();
/* cola layout */
graph.nodes.forEach(function(v) {
v.width = 5 * R;
return v.height = 3 * R;
});
d3cola = cola.d3adaptor().size([width, height]).avoidOverlaps(true).linkDistance(70).flowLayout('y', 80).nodes(graph.nodes).links(dag.links).on('tick', function() {
nodes.attr('transform', function(d) {
return "translate(" + d.x + "," + d.y + ")";
});
return links.select('path').attr({
d: function(d) {
var a, alpha, b, h, x1, x2, xr, y1, y2, yr;
if (!d.inverse) {
x1 = d.source.x;
x2 = d.target.x;
y1 = d.source.y;
y2 = d.target.y;
} else {
x1 = d.target.x;
x2 = d.source.x;
y1 = d.target.y;
y2 = d.source.y;
}
alpha = Math.atan2(y2 - y1, x2 - x1);
xr = R * Math.sin(alpha);
yr = R * Math.cos(alpha);
if (d.full_name === 'isA' || d.full_name === 'instanceOf') {
return "M" + (x1 + yr) + " " + (y1 + xr) + " L" + (x2 - yr) + " " + (y2 - xr);
} else {
h = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
a = C * h * Math.sin(alpha);
b = C * h * Math.cos(alpha);
return "M" + (x1 + xr) + " " + (y1 - yr) + " C" + (x1 + xr + a) + " " + (y1 - yr - b) + " " + (x2 + xr + a) + " " + (y2 - yr - b) + " " + (x2 + xr) + " " + (y2 - yr);
}
}
});
});
drag = d3cola.drag();
drag.on('dragstart', function() {
return d3.event.sourceEvent.stopPropagation();
});
nodes.call(drag);
return d3cola.start(200, 30, 30);
}
});
}).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;
}));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;
}
{
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();
}