nitaku · July 27, 2016 03:00
diff --git a/README.md b/README.md
diff --git a/AppView.coffee b/AppView.coffee
 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()
      
diff --git a/AppView.js b/AppView.js
 // 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);
diff --git a/backbone.d3view.js b/backbone.d3view.js
 // 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;
 }));
diff --git a/Editor.coffee b/Editor.coffee
 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'}
    
diff --git a/Editor.css b/Editor.css
 .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;
 }
diff --git a/Editor.js b/Editor.js
 // 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);
diff --git a/Graph.coffee b/Graph.coffee
 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
    
diff --git a/Graph.js b/Graph.js
 // 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);
diff --git a/index.coffee b/index.coffee
 app = new AppView
  el: 'body'
  model: new Graph
diff --git a/index.css b/index.css
 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;
 }
diff --git a/index.html b/index.html
 <!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="http://underscorejs.org/underscore-min.js"></script>
    <script src="http://backbonejs.org/backbone-min.js"></script>
    <script src="backbone.d3view.js"></script>
    <script src="http://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>
diff --git a/index.js b/index.js
 // Generated by CoffeeScript 1.10.0
 (function() {
  var app;

  app = new AppView({
    el: 'body',
    model: new Graph
  });

 }).call(this);
diff --git a/knowledge.peg.js b/knowledge.peg.js
 {
  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()); }
diff --git a/NodeLink.coffee b/NodeLink.coffee
 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)
    
diff --git a/NodeLink.css b/NodeLink.css
 .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 */
 }
diff --git a/NodeLink.js b/NodeLink.js
 // 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);
diff --git a/thumbnail.png b/thumbnail.png
diff --git a/tsort.js b/tsort.js
 /**
 * 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();
 }
	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);
	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="http://underscorejs.org/underscore-min.js"></script>
	<script src="http://backbonejs.org/backbone-min.js"></script>
	<script src="backbone.d3view.js"></script>
	<script src="http://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>