<commit_before>/*
 *  Dracula Graph Layout and Drawing Framework 0.0.3alpha
 *  (c) 2010 <NAME> <<EMAIL>>, http://strathausen.eu
 *  Contributions by <NAME> <<EMAIL>>.
 *
 *  based on the Graph JavaScript framework, version 0.0.1
 *  (c) 2006 <NAME> <<EMAIL>>
 *  (c) 2006 <NAME> <<EMAIL>>
 *
 *  Ported from Graph::Layouter::Spring in
 *    http://search.cpan.org/~pasky/Graph-Layderer-0.02/
 *  The algorithm is based on a spring-style layouter of a Java-based social
 *  network tracker PieSpy written by <NAME> <<EMAIL>>.
 *
 *  This code is freely distributable under the MIT license. Commercial use is
 *  hereby granted without any cost or restriction.
 *
 *  Links:
 *
 *  Graph Dracula JavaScript Framework:
 *      http://graphdracula.net
 *
 /*--------------------------------------------------------------------------*/

/*
 * Edge Factory
 */
var AbstractEdge = function() {
}
AbstractEdge.prototype = {
  hide: function() {
    this.connection.fg.hide();
    this.connection.bg && this.bg.connection.hide();
  }
};
var EdgeFactory = function() {
  this.template = new AbstractEdge();
  this.template.style = new Object();
  this.template.style.directed = false;
  this.template.weight = 1;
};
EdgeFactory.prototype = {
  build: function(source, target) {
    var e = jQuery.extend(true, {}, this.template);
    e.source = source;
    e.target = target;
    return e;
  }
};

/*
 * Graph
 */
var Graph = function() {
  this.nodes = {};
  this.edges = [];
  this.snapshots = []; // previous graph states TODO to be implemented
  this.edgeFactory = new EdgeFactory();
};
Graph.prototype = {
  /*
   * add a node
   * @id          the node's ID (string or number)
   * @content     (optional, dictionary) can contain any information that is
   *              being interpreted by the layout algorithm or the graph
   *              representation
   */
  addNode: function(id, content) {
    /* testing if node is already existing in the graph */
    if(this.nodes[id] == undefined) {
      this.nodes[id] = new Graph.Node(id, content);
    }
    return this.nodes[id];
  },

  addEdge: function(source, target, style) {
    var s = this.addNode(source);
    var t = this.addNode(target);
    var edge = this.edgeFactory.build(s, t);
    jQuery.extend(true, edge.style, style);
    s.edges.push(edge);
    this.edges.push(edge);
    // NOTE: Even directed edges are added to both nodes.
    t.edges.push(edge);
  },

           /* TODO to be implemented
            * Preserve a copy of the graph state (nodes, positions, ...)
            * @comment     a comment describing the state
            */
  snapShot: function(comment) {
    /* FIXME
       var graph = new Graph();
       graph.nodes = jQuery.extend(true, {}, this.nodes);
       graph.edges = jQuery.extend(true, {}, this.edges);
       this.snapshots.push({comment: comment, graph: graph});
       */
            },
removeNode: function(id) {
              delete this.nodes[id];
              for(var i = 0; i < this.edges.length; i++) {
                if (this.edges[i].source.id == id || this.edges[i].target.id == id) {
                  this.edges.splice(i, 1);
                  i--;
                }
              }
            }
};

/*
 * Node
 */
Graph.Node = function(id, node){
  node = node || {};
  node.id = id;
  node.edges = [];
  node.hide = function() {
    this.hidden = true;
    this.shape && this.shape.hide(); /* FIXME this is representation specific code and should be elsewhere */
    for(i in this.edges)
      (this.edges[i].source.id == id || this.edges[i].target == id) && this.edges[i].hide && this.edges[i].hide();
  };
  node.show = function() {
    this.hidden = false;
    this.shape && this.shape.show();
    for(i in this.edges)
      (this.edges[i].source.id == id || this.edges[i].target == id) && this.edges[i].show && this.edges[i].show();
  };
  return node;
};
Graph.Node.prototype = {
};

/*
 * Renderer base class
 */
Graph.Renderer = {};

/*
 * Renderer implementation using RaphaelJS
 */
Graph.Renderer.Raphael = function(element, graph, width, height) {
  this.width = width || 400;
  this.height = height || 400;
  var selfRef = this;
  this.r = Raphael(element, this.width, this.height);
  this.radius = 40; /* max dimension of a node */
  this.graph = graph;
  this.mouse_in = false;

  /* TODO default node rendering function */
  if(!this.graph.render) {
    this.graph.render = function() {
      return;
    }
  }

  /*
   * Dragging
   */
  this.isDrag = false;
  this.dragger = function (e) {
    this.dx = e.clientX;
    this.dy = e.clientY;
    selfRef.isDrag = this;
    this.set && this.set.animate({"fill-opacity": .1}, 200);
    e.preventDefault && e.preventDefault();
  };

  var d = document.getElementById(element);
  d.onmousemove = function (e) {
    e = e || window.event;
    if (selfRef.isDrag) {
      var bBox = selfRef.isDrag.set.getBBox();
      // TODO round the coordinates here (eg. for proper image representation)
      var newX = e.clientX - selfRef.isDrag.dx + (bBox.x + bBox.width / 2);
      var newY = e.clientY - selfRef.isDrag.dy + (bBox.y + bBox.height / 2);
      /* prevent shapes from being dragged out of the canvas */
      var clientX = e.clientX - (newX < 20 ? newX - 20 : newX > selfRef.width - 20 ? newX - selfRef.width + 20 : 0);
      var clientY = e.clientY - (newY < 20 ? newY - 20 : newY > selfRef.height - 20 ? newY - selfRef.height + 20 : 0);
      selfRef.isDrag.set.translate(clientX - Math.round(selfRef.isDrag.dx), clientY - Math.round(selfRef.isDrag.dy));
      //            console.log(clientX - Math.round(selfRef.isDrag.dx), clientY - Math.round(selfRef.isDrag.dy));
      for (var i in selfRef.graph.edges) {
        selfRef.graph.edges[i] &&
          selfRef.graph.edges[i].connection && selfRef.graph.edges[i].connection.draw();
      }
      //selfRef.r.safari();
      selfRef.isDrag.dx = clientX;
      selfRef.isDrag.dy = clientY;
    }
  };
  d.onmouseup = function () {
    selfRef.isDrag && selfRef.isDrag.set.animate({"fill-opacity": .6}, 500);
    selfRef.isDrag = false;
  };
  this.draw();
};


/* Moved this default node renderer function out of the main prototype code
 * so it can be override by default */
Graph.Renderer.defaultRenderFunc = function(r, node) {
    /* the default node drawing */
    var color = Raphael.getColor();
    var ellipse = r.ellipse(0, 0, 30, 20).attr({fill: node.fill || color, stroke: node.stroke || color, "stroke-width": 2});
    /* set DOM node ID */
    ellipse.node.id = node.label || node.id;
    shape = r.set().
        push(ellipse).
        push(r.text(0, 30, node.label || node.id));
    return shape;
}


Graph.Renderer.Raphael.prototype = {
    translate: function(point) {
        return [
            (point[0] - this.graph.layoutMinX) * this.factorX + this.radius,
            (point[1] - this.graph.layoutMinY) * this.factorY + this.radius
        ];
    },

    rotate: function(point, length, angle) {
        var dx = length * Math.cos(angle);
        var dy = length * Math.sin(angle);
        return [point[0]+dx, point[1]+dy];
    },

    draw: function() {
        this.factorX = (this.width - 2 * this.radius) / (this.graph.layoutMaxX - this.graph.layoutMinX);
        this.factorY = (this.height - 2 * this.radius) / (this.graph.layoutMaxY - this.graph.layoutMinY);
        for (i in this.graph.nodes) {
            this.drawNode(this.graph.nodes[i]);
        }
        for (var i = 0; i < this.graph.edges.length; i++) {
            this.drawEdge(this.graph.edges[i]);
        }
    },

    drawNode: function(node) {
        var point = this.translate([node.layoutPosX, node.layoutPosY]);
        node.point = point;

        /* if node has already been drawn, move the nodes */
        if(node.shape) {
            var oBBox = node.shape.getBBox();
            var opoint = { x: oBBox.x + oBBox.width / 2, y: oBBox.y + oBBox.height / 2};
            node.shape.translate(Math.round(point[0] - opoint.x), Math.round(point[1] - opoint.y));
            this.r.safari();
            return node;
        }/* else, draw new nodes */

        var shape;

        /* if a node renderer function is provided by the user, then use it
           or the default render function instead */
        if(!node.render) {
            node.render = Graph.Renderer.defaultRenderFunc;
        }
        /* or check for an ajax representation of the nodes */
        if(node.shapes) {
            // TODO ajax representation evaluation
        }

        shape = node.render(this.r, node).hide();

        shape.attr({"fill-opacity": .6});
        /* re-reference to the node an element belongs to, needed for dragging all elements of a node */
        shape.items.forEach(function(item){ item.set = shape; item.node.style.cursor = "move"; });
        shape.mousedown(this.dragger);

        var box = shape.getBBox();
        shape.translate(Math.round(point[0]-(box.x+box.width/2)),Math.round(point[1]-(box.y+box.height/2)))
        //console.log(box,point);
        node.hidden || shape.show();
        node.shape = shape;
    },
    drawEdge: function(edge) {
        /* if this edge already exists the other way around and is undirected */
        if(edge.backedge)
            return;
        if(edge.source.hidden || edge.target.hidden) {
            edge.connection && edge.connection.fg.hide();
            edge.connection.bg && edge.connection.bg.hide();
            return;
        }
        /* if edge already has been drawn, only refresh the edge */
        if(!edge.connection) {
            edge.style && edge.style.callback && edge.style.callback(edge); // TODO move this somewhere else
            edge.connection = this.r.connection(edge.source.shape, edge.target.shape, edge.style);
            return;
        }
        //FIXME showing doesn't work well
        edge.connection.fg.show();
        edge.connection.bg && edge.connection.bg.show();
        edge.connection.draw();
    }
};
Graph.Layout = {};
Graph.Layout.Spring = function(graph) {
    this.graph = graph;
    this.iterations = 500;
    this.maxRepulsiveForceDistance = 6;
    this.k = 2;
    this.c = 0.01;
    this.maxVertexMovement = 0.5;
    this.layout();
};
Graph.Layout.Spring.prototype = {
    layout: function() {
        this.layoutPrepare();
        for (var i = 0; i < this.iterations; i++) {
            this.layoutIteration();
        }
        this.layoutCalcBounds();
    },

    layoutPrepare: function() {
        for (i in this.graph.nodes) {
            var node = this.graph.nodes[i];
            node.layoutPosX = 0;
            node.layoutPosY = 0;
            node.layoutForceX = 0;
            node.layoutForceY = 0;
        }

    },

    layoutCalcBounds: function() {
        var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;

        for (i in this.graph.nodes) {
            var x = this.graph.nodes[i].layoutPosX;
            var y = this.graph.nodes[i].layoutPosY;

            if(x > maxx) maxx = x;
            if(x < minx) minx = x;
            if(y > maxy) maxy = y;
            if(y < miny) miny = y;
        }

        this.graph.layoutMinX = minx;
        this.graph.layoutMaxX = maxx;
        this.graph.layoutMinY = miny;
        this.graph.layoutMaxY = maxy;
    },

    layoutIteration: function() {
        // Forces on nodes due to node-node repulsions

        var prev = new Array();
        for(var c in this.graph.nodes) {
            var node1 = this.graph.nodes[c];
            for (var d in prev) {
                var node2 = this.graph.nodes[prev[d]];
                this.layoutRepulsive(node1, node2);

            }
            prev.push(c);
        }

        // Forces on nodes due to edge attractions
        for (var i = 0; i < this.graph.edges.length; i++) {
            var edge = this.graph.edges[i];
            this.layoutAttractive(edge);
        }

        // Move by the given force
        for (i in this.graph.nodes) {
            var node = this.graph.nodes[i];
            var xmove = this.c * node.layoutForceX;
            var ymove = this.c * node.layoutForceY;

            var max = this.maxVertexMovement;
            if(xmove > max) xmove = max;
            if(xmove < -max) xmove = -max;
            if(ymove > max) ymove = max;
            if(ymove < -max) ymove = -max;

            node.layoutPosX += xmove;
            node.layoutPosY += ymove;
            node.layoutForceX = 0;
            node.layoutForceY = 0;
        }
    },

    layoutRepulsive: function(node1, node2) {
        if (typeof node1 == 'undefined' || typeof node2 == 'undefined')
            return;
        var dx = node2.layoutPosX - node1.layoutPosX;
        var dy = node2.layoutPosY - node1.layoutPosY;
        var d2 = dx * dx + dy * dy;
        if(d2 < 0.01) {
            dx = 0.1 * Math.random() + 0.1;
            dy = 0.1 * Math.random() + 0.1;
            var d2 = dx * dx + dy * dy;
        }
        var d = Math.sqrt(d2);
        if(d < this.maxRepulsiveForceDistance) {
            var repulsiveForce = this.k * this.k / d;
            node2.layoutForceX += repulsiveForce * dx / d;
            node2.layoutForceY += repulsiveForce * dy / d;
            node1.layoutForceX -= repulsiveForce * dx / d;
            node1.layoutForceY -= repulsiveForce * dy / d;
        }
    },

    layoutAttractive: function(edge) {
        var node1 = edge.source;
        var node2 = edge.target;

        var dx = node2.layoutPosX - node1.layoutPosX;
        var dy = node2.layoutPosY - node1.layoutPosY;
        var d2 = dx * dx + dy * dy;
        if(d2 < 0.01) {
            dx = 0.1 * Math.random() + 0.1;
            dy = 0.1 * Math.random() + 0.1;
            var d2 = dx * dx + dy * dy;
        }
        var d = Math.sqrt(d2);
        if(d > this.maxRepulsiveForceDistance) {
            d = this.maxRepulsiveForceDistance;
            d2 = d * d;
        }
        var attractiveForce = (d2 - this.k * this.k) / this.k;
        if(edge.attraction == undefined) edge.attraction = 1;
        attractiveForce *= Math.log(edge.attraction) * 0.5 + 1;

        node2.layoutForceX -= attractiveForce * dx / d;
        node2.layoutForceY -= attractiveForce * dy / d;
        node1.layoutForceX += attractiveForce * dx / d;
        node1.layoutForceY += attractiveForce * dy / d;
    }
};

Graph.Layout.Ordered = function(graph, order) {
    this.graph = graph;
    this.order = order;
    this.layout();
};
Graph.Layout.Ordered.prototype = {
    layout: function() {
        this.layoutPrepare();
        this.layoutCalcBounds();
    },

    layoutPrepare: function(order) {
        for (i in this.graph.nodes) {
            var node = this.graph.nodes[i];
            node.layoutPosX = 0;
            node.layoutPosY = 0;
        }
            var counter = 0;
            for (i in this.order) {
                var node = this.order[i];
                node.layoutPosX = counter;
                node.layoutPosY = Math.random();
                counter++;
            }
    },

    layoutCalcBounds: function() {
        var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;

        for (i in this.graph.nodes) {
            var x = this.graph.nodes[i].layoutPosX;
            var y = this.graph.nodes[i].layoutPosY;

            if(x > maxx) maxx = x;
            if(x < minx) minx = x;
            if(y > maxy) maxy = y;
            if(y < miny) miny = y;
        }

        this.graph.layoutMinX = minx;
        this.graph.layoutMaxX = maxx;

        this.graph.layoutMinY = miny;
        this.graph.layoutMaxY = maxy;
    }
};


Graph.Layout.OrderedTree = function(graph, order) {
    this.graph = graph;
    this.order = order;
    this.layout();
};

/*
 * OrderedTree is like Ordered but assumes there is one root
 * This way we can give non random positions to nodes on the Y-axis
 * it assumes the ordered nodes are of a perfect binary tree
 */
Graph.Layout.OrderedTree.prototype = {
    layout: function() {
        this.layoutPrepare();
        this.layoutCalcBounds();
    },
    
    layoutPrepare: function(order) {
        for (i in this.graph.nodes) {
            var node = this.graph.nodes[i];
            node.layoutPosX = 0;
            node.layoutPosY = 0;
        }
        //to reverse the order of rendering, we need to find out the
        //absolute number of levels we have. simple log math applies.
        var numNodes = this.order.length;
        var totalLevels = Math.floor(Math.log(numNodes) / Math.log(2));
        
        var counter = 1;
        for (i in this.order) {
            var node = this.order[i];
            //rank aka x coordinate 
            var rank = Math.floor(Math.log(counter) / Math.log(2));
            //file relative to top
            var file = counter - Math.pow(rank, 2);
            
            log('Node ' + node.id + '  #' + counter + ' is at rank ' + rank + ' file ' + file);
            node.layoutPosX = totalLevels - rank;
            node.layoutPosY = file;
            counter++;
        }
    },
    
    layoutCalcBounds: function() {
        var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;

        for (i in this.graph.nodes) {
            var x = this.graph.nodes[i].layoutPosX;
            var y = this.graph.nodes[i].layoutPosY;
            
            if(x > maxx) maxx = x;
            if(x < minx) minx = x;
            if(y > maxy) maxy = y;
            if(y < miny) miny = y;
        }

        this.graph.layoutMinX = minx;
        this.graph.layoutMaxX = maxx;

        this.graph.layoutMinY = miny;
        this.graph.layoutMaxY = maxy;
    }
};


Graph.Layout.TournamentTree = function(graph, order) {
    this.graph = graph;
    this.order = order;
    this.layout();
};

/*
 * TournamentTree looks more like a binary tree
 */
Graph.Layout.TournamentTree.prototype = {
    layout: function() {
        this.layoutPrepare();
        this.layoutCalcBounds();
    },
    
    layoutPrepare: function(order) {
        for (i in this.graph.nodes) {
            var node = this.graph.nodes[i];
            node.layoutPosX = 0;
            node.layoutPosY = 0;
        }
        //to reverse the order of rendering, we need to find out the
        //absolute number of levels we have. simple log math applies.
        var numNodes = this.order.length;
        var totalLevels = Math.floor(Math.log(numNodes) / Math.log(2));
        
        var counter = 1;
        for (i in this.order) {
            var node = this.order[i];
            var depth = Math.floor(Math.log(counter) / Math.log(2));
            var xpos = counter - Math.pow(depth, 2);
            var offset = Math.pow(2, totalLevels - depth);
            var final_x = offset + (counter - Math.pow(2,depth)) * Math.pow(2,(totalLevels - depth)+1);
            
            log('Node ' + node.id + '  #' + counter + ' is at depth ' + depth + ' offset ' + offset + ' final_x ' + final_x);
            node.layoutPosX = final_x;
            node.layoutPosY = depth;
            counter++;
        }
    },
    
    layoutCalcBounds: function() {
        var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;

        for (i in this.graph.nodes) {
            var x = this.graph.nodes[i].layoutPosX;
            var y = this.graph.nodes[i].layoutPosY;
            
            if(x > maxx) maxx = x;
            if(x < minx) minx = x;
            if(y > maxy) maxy = y;
            if(y < miny) miny = y;
        }

        this.graph.layoutMinX = minx;
        this.graph.layoutMaxX = maxx;

        this.graph.layoutMinY = miny;
        this.graph.layoutMaxY = maxy;
    }
};




/*
 * usefull JavaScript extensions,
 */

function log(a) {console.log&&console.log(a);}

/*
 * Raphael Tooltip Plugin
 * - attaches an element as a tooltip to another element
 *
 * Usage example, adding a rectangle as a tooltip to a circle:
 *
 *      paper.circle(100,100,10).tooltip(paper.rect(0,0,20,30));
 *
 * If you want to use more shapes, you'll have to put them into a set.
 *
 */
Raphael.el.tooltip = function (tp) {
    this.tp = tp;
    this.tp.o = {x: 0, y: 0};
    this.tp.hide();
    this.hover(
        function(event){
            this.mousemove(function(event){
                this.tp.translate(event.clientX -
                                  this.tp.o.x,event.clientY - this.tp.o.y);
                this.tp.o = {x: event.clientX, y: event.clientY};
            });
            this.tp.show().toFront();
        },
        function(event){
            this.tp.hide();
            this.unmousemove();
        });
    return this;
};

/* For IE */
if (!Array.prototype.forEach)
{
  Array.prototype.forEach = function(fun /*, thisp*/)
  {
    var len = this.length;
    if (typeof fun != "function")
      throw new TypeError();

    var thisp = arguments[1];
    for (var i = 0; i < len; i++)
    {
      if (i in this)
        fun.call(thisp, this[i], i, this);
    }
  };
}
<commit_msg>remove EdgeFactory, reintroduce Edge class<commit_after>/*
 *  Dracula Graph Layout and Drawing Framework 0.0.3alpha
 *  (c) 2010 <NAME> <<EMAIL>>, http://strathausen.eu
 *  Contributions by <NAME> <<EMAIL>>.
 *
 *  based on the Graph JavaScript framework, version 0.0.1
 *  (c) 2006 <NAME> <<EMAIL>>
 *  (c) 2006 <NAME> <<EMAIL>>
 *
 *  Ported from Graph::Layouter::Spring in
 *    http://search.cpan.org/~pasky/Graph-Layderer-0.02/
 *  The algorithm is based on a spring-style layouter of a Java-based social
 *  network tracker PieSpy written by <NAME> <<EMAIL>>.
 *
 *  This code is freely distributable under the MIT license. Commercial use is
 *  hereby granted without any cost or restriction.
 *
 *  Links:
 *
 *  Graph Dracula JavaScript Framework:
 *      http://graphdracula.net
 *
 /*--------------------------------------------------------------------------*/



/*
 * Graph
 */
var Graph = function() {
  this.nodes = {};
  this.edges = [];
  this.snapshots = []; // previous graph states TODO to be implemented
};
Graph.prototype = {
  /*
   * add a node
   * @id          the node's ID (string or number)
   * @content     (optional, dictionary) can contain any information that is
   *              being interpreted by the layout algorithm or the graph
   *              representation
   */
  addNode: function(id, content) {
    /* testing if node is already existing in the graph */
    if(this.nodes[id] === undefined) {
      this.nodes[id] = new Graph.Node(id, content);
    }
    return this.nodes[id];
  },

  addEdge: function(source, target, style) {
    var s = this.addNode(source);
    var t = this.addNode(target);
    var edge = new Graph.Edge({ source: s, target: t, style: style });
    s.edges.push(edge);
    this.edges.push(edge);
    // NOTE: Even directed edges are added to both nodes.
    t.edges.push(edge);
  },

  /* TODO to be implemented
   * Preserve a copy of the graph state (nodes, positions, ...)
   * @comment     a comment describing the state
   */
  snapShot: function(comment) {
    // FIXME
    //var graph = new Graph();
    //graph.nodes = jQuery.extend(true, {}, this.nodes);
    //graph.edges = jQuery.extend(true, {}, this.edges);
    //this.snapshots.push({comment: comment, graph: graph});
  },
  removeNode: function(id) {
    delete this.nodes[id];
    for(var i = 0; i < this.edges.length; i++) {
      if (this.edges[i].source.id == id || this.edges[i].target.id == id) {
        this.edges.splice(i, 1);
        i--;
      }
    }
  }
};

/*
 * Edge
 */
Graph.Edge = function DraculaEdge(opts) {
  this.source = opts.source;
  this.target = opts.target;
  this.style = { directed: false };
  if (opts.style) {
    this.style = jQuery.extend(true, this.style, opts.style);
  }
};
Graph.Edge.prototype = {
  weight: 0,
  hide: function hideEdge() {
    this.connection.fg.hide();
    this.connection.bg && this.bg.connection.hide();
  }
}

/*
 * Node
 */
Graph.Node = function DraculaNode(id, node){
  node = node || {};
  node.id = id;
  node.edges = [];
  node.hide = function() {
    this.hidden = true;
    this.shape && this.shape.hide(); /* FIXME this is representation specific code and should be elsewhere */
    for(i in this.edges)
      (this.edges[i].source.id == id || this.edges[i].target == id) && this.edges[i].hide && this.edges[i].hide();
  };
  node.show = function() {
    this.hidden = false;
    this.shape && this.shape.show();
    for(i in this.edges)
      (this.edges[i].source.id == id || this.edges[i].target == id) && this.edges[i].show && this.edges[i].show();
  };
  return node;
};
Graph.Node.prototype = {
};

/*
 * Renderer Base Class
 */
Graph.Renderer = {};

/*
 * Renderer implementation using RaphaelJS
 */
Graph.Renderer.Raphael = function(element, graph, width, height) {
  this.width = width || 400;
  this.height = height || 400;
  var selfRef = this;
  this.r = Raphael(element, this.width, this.height);
  this.radius = 40; /* max dimension of a node */
  this.graph = graph;
  this.mouse_in = false;

  /* TODO default node rendering function */
  if(!this.graph.render) {
    this.graph.render = function() {
      return;
    }
  }

  /*
   * Dragging
   */
  this.isDrag = false;
  this.dragger = function (e) {
    this.dx = e.clientX;
    this.dy = e.clientY;
    selfRef.isDrag = this;
    this.set && this.set.animate({"fill-opacity": .1}, 200);
    e.preventDefault && e.preventDefault();
  };

  var d = document.getElementById(element);
  d.onmousemove = function (e) {
    e = e || window.event;
    if (selfRef.isDrag) {
      var bBox = selfRef.isDrag.set.getBBox();
      // TODO round the coordinates here (eg. for proper image representation)
      var newX = e.clientX - selfRef.isDrag.dx + (bBox.x + bBox.width / 2);
      var newY = e.clientY - selfRef.isDrag.dy + (bBox.y + bBox.height / 2);
      /* prevent shapes from being dragged out of the canvas */
      var clientX = e.clientX - (newX < 20 ? newX - 20 : newX > selfRef.width - 20 ? newX - selfRef.width + 20 : 0);
      var clientY = e.clientY - (newY < 20 ? newY - 20 : newY > selfRef.height - 20 ? newY - selfRef.height + 20 : 0);
      selfRef.isDrag.set.translate(clientX - Math.round(selfRef.isDrag.dx), clientY - Math.round(selfRef.isDrag.dy));
      //            console.log(clientX - Math.round(selfRef.isDrag.dx), clientY - Math.round(selfRef.isDrag.dy));
      for (var i in selfRef.graph.edges) {
        selfRef.graph.edges[i] &&
          selfRef.graph.edges[i].connection && selfRef.graph.edges[i].connection.draw();
      }
      //selfRef.r.safari();
      selfRef.isDrag.dx = clientX;
      selfRef.isDrag.dy = clientY;
    }
  };
  d.onmouseup = function () {
    selfRef.isDrag && selfRef.isDrag.set.animate({"fill-opacity": .6}, 500);
    selfRef.isDrag = false;
  };
  this.draw();
};


/* Moved this default node renderer function out of the main prototype code
 * so it can be override by default */
Graph.Renderer.defaultRenderFunc = function(r, node) {
    /* the default node drawing */
    var color = Raphael.getColor();
    var ellipse = r.ellipse(0, 0, 30, 20).attr({fill: node.fill || color, stroke: node.stroke || color, "stroke-width": 2});
    /* set DOM node ID */
    ellipse.node.id = node.label || node.id;
    shape = r.set().
        push(ellipse).
        push(r.text(0, 30, node.label || node.id));
    return shape;
}


Graph.Renderer.Raphael.prototype = {
    translate: function(point) {
        return [
            (point[0] - this.graph.layoutMinX) * this.factorX + this.radius,
            (point[1] - this.graph.layoutMinY) * this.factorY + this.radius
        ];
    },

    rotate: function(point, length, angle) {
        var dx = length * Math.cos(angle);
        var dy = length * Math.sin(angle);
        return [point[0]+dx, point[1]+dy];
    },

    draw: function() {
        this.factorX = (this.width - 2 * this.radius) / (this.graph.layoutMaxX - this.graph.layoutMinX);
        this.factorY = (this.height - 2 * this.radius) / (this.graph.layoutMaxY - this.graph.layoutMinY);
        for (i in this.graph.nodes) {
            this.drawNode(this.graph.nodes[i]);
        }
        for (var i = 0; i < this.graph.edges.length; i++) {
            this.drawEdge(this.graph.edges[i]);
        }
    },

    drawNode: function(node) {
        var point = this.translate([node.layoutPosX, node.layoutPosY]);
        node.point = point;

        /* if node has already been drawn, move the nodes */
        if(node.shape) {
            var oBBox = node.shape.getBBox();
            var opoint = { x: oBBox.x + oBBox.width / 2, y: oBBox.y + oBBox.height / 2};
            node.shape.translate(Math.round(point[0] - opoint.x), Math.round(point[1] - opoint.y));
            this.r.safari();
            return node;
        }/* else, draw new nodes */

        var shape;

        /* if a node renderer function is provided by the user, then use it
           or the default render function instead */
        if(!node.render) {
            node.render = Graph.Renderer.defaultRenderFunc;
        }
        /* or check for an ajax representation of the nodes */
        if(node.shapes) {
            // TODO ajax representation evaluation
        }

        shape = node.render(this.r, node).hide();

        shape.attr({"fill-opacity": .6});
        /* re-reference to the node an element belongs to, needed for dragging all elements of a node */
        shape.items.forEach(function(item){ item.set = shape; item.node.style.cursor = "move"; });
        shape.mousedown(this.dragger);

        var box = shape.getBBox();
        shape.translate(Math.round(point[0]-(box.x+box.width/2)),Math.round(point[1]-(box.y+box.height/2)))
        //console.log(box,point);
        node.hidden || shape.show();
        node.shape = shape;
    },
    drawEdge: function(edge) {
        /* if this edge already exists the other way around and is undirected */
        if(edge.backedge)
            return;
        if(edge.source.hidden || edge.target.hidden) {
            edge.connection && edge.connection.fg.hide();
            edge.connection.bg && edge.connection.bg.hide();
            return;
        }
        /* if edge already has been drawn, only refresh the edge */
        if(!edge.connection) {
            edge.style && edge.style.callback && edge.style.callback(edge); // TODO move this somewhere else
            edge.connection = this.r.connection(edge.source.shape, edge.target.shape, edge.style);
            return;
        }
        //FIXME showing doesn't work well
        edge.connection.fg.show();
        edge.connection.bg && edge.connection.bg.show();
        edge.connection.draw();
    }
};
Graph.Layout = {};
Graph.Layout.Spring = function(graph) {
    this.graph = graph;
    this.iterations = 500;
    this.maxRepulsiveForceDistance = 6;
    this.k = 2;
    this.c = 0.01;
    this.maxVertexMovement = 0.5;
    this.layout();
};
Graph.Layout.Spring.prototype = {
    layout: function() {
        this.layoutPrepare();
        for (var i = 0; i < this.iterations; i++) {
            this.layoutIteration();
        }
        this.layoutCalcBounds();
    },

    layoutPrepare: function() {
        for (i in this.graph.nodes) {
            var node = this.graph.nodes[i];
            node.layoutPosX = 0;
            node.layoutPosY = 0;
            node.layoutForceX = 0;
            node.layoutForceY = 0;
        }

    },

    layoutCalcBounds: function() {
        var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;

        for (i in this.graph.nodes) {
            var x = this.graph.nodes[i].layoutPosX;
            var y = this.graph.nodes[i].layoutPosY;

            if(x > maxx) maxx = x;
            if(x < minx) minx = x;
            if(y > maxy) maxy = y;
            if(y < miny) miny = y;
        }

        this.graph.layoutMinX = minx;
        this.graph.layoutMaxX = maxx;
        this.graph.layoutMinY = miny;
        this.graph.layoutMaxY = maxy;
    },

    layoutIteration: function() {
        // Forces on nodes due to node-node repulsions

        var prev = new Array();
        for(var c in this.graph.nodes) {
            var node1 = this.graph.nodes[c];
            for (var d in prev) {
                var node2 = this.graph.nodes[prev[d]];
                this.layoutRepulsive(node1, node2);

            }
            prev.push(c);
        }

        // Forces on nodes due to edge attractions
        for (var i = 0; i < this.graph.edges.length; i++) {
            var edge = this.graph.edges[i];
            this.layoutAttractive(edge);
        }

        // Move by the given force
        for (i in this.graph.nodes) {
            var node = this.graph.nodes[i];
            var xmove = this.c * node.layoutForceX;
            var ymove = this.c * node.layoutForceY;

            var max = this.maxVertexMovement;
            if(xmove > max) xmove = max;
            if(xmove < -max) xmove = -max;
            if(ymove > max) ymove = max;
            if(ymove < -max) ymove = -max;

            node.layoutPosX += xmove;
            node.layoutPosY += ymove;
            node.layoutForceX = 0;
            node.layoutForceY = 0;
        }
    },

    layoutRepulsive: function(node1, node2) {
        if (typeof node1 == 'undefined' || typeof node2 == 'undefined')
            return;
        var dx = node2.layoutPosX - node1.layoutPosX;
        var dy = node2.layoutPosY - node1.layoutPosY;
        var d2 = dx * dx + dy * dy;
        if(d2 < 0.01) {
            dx = 0.1 * Math.random() + 0.1;
            dy = 0.1 * Math.random() + 0.1;
            var d2 = dx * dx + dy * dy;
        }
        var d = Math.sqrt(d2);
        if(d < this.maxRepulsiveForceDistance) {
            var repulsiveForce = this.k * this.k / d;
            node2.layoutForceX += repulsiveForce * dx / d;
            node2.layoutForceY += repulsiveForce * dy / d;
            node1.layoutForceX -= repulsiveForce * dx / d;
            node1.layoutForceY -= repulsiveForce * dy / d;
        }
    },

    layoutAttractive: function(edge) {
        var node1 = edge.source;
        var node2 = edge.target;

        var dx = node2.layoutPosX - node1.layoutPosX;
        var dy = node2.layoutPosY - node1.layoutPosY;
        var d2 = dx * dx + dy * dy;
        if(d2 < 0.01) {
            dx = 0.1 * Math.random() + 0.1;
            dy = 0.1 * Math.random() + 0.1;
            var d2 = dx * dx + dy * dy;
        }
        var d = Math.sqrt(d2);
        if(d > this.maxRepulsiveForceDistance) {
            d = this.maxRepulsiveForceDistance;
            d2 = d * d;
        }
        var attractiveForce = (d2 - this.k * this.k) / this.k;
        if(edge.attraction == undefined) edge.attraction = 1;
        attractiveForce *= Math.log(edge.attraction) * 0.5 + 1;

        node2.layoutForceX -= attractiveForce * dx / d;
        node2.layoutForceY -= attractiveForce * dy / d;
        node1.layoutForceX += attractiveForce * dx / d;
        node1.layoutForceY += attractiveForce * dy / d;
    }
};

Graph.Layout.Ordered = function(graph, order) {
    this.graph = graph;
    this.order = order;
    this.layout();
};
Graph.Layout.Ordered.prototype = {
    layout: function() {
        this.layoutPrepare();
        this.layoutCalcBounds();
    },

    layoutPrepare: function(order) {
        for (i in this.graph.nodes) {
            var node = this.graph.nodes[i];
            node.layoutPosX = 0;
            node.layoutPosY = 0;
        }
            var counter = 0;
            for (i in this.order) {
                var node = this.order[i];
                node.layoutPosX = counter;
                node.layoutPosY = Math.random();
                counter++;
            }
    },

    layoutCalcBounds: function() {
        var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;

        for (i in this.graph.nodes) {
            var x = this.graph.nodes[i].layoutPosX;
            var y = this.graph.nodes[i].layoutPosY;

            if(x > maxx) maxx = x;
            if(x < minx) minx = x;
            if(y > maxy) maxy = y;
            if(y < miny) miny = y;
        }

        this.graph.layoutMinX = minx;
        this.graph.layoutMaxX = maxx;

        this.graph.layoutMinY = miny;
        this.graph.layoutMaxY = maxy;
    }
};


Graph.Layout.OrderedTree = function(graph, order) {
    this.graph = graph;
    this.order = order;
    this.layout();
};

/*
 * OrderedTree is like Ordered but assumes there is one root
 * This way we can give non random positions to nodes on the Y-axis
 * it assumes the ordered nodes are of a perfect binary tree
 */
Graph.Layout.OrderedTree.prototype = {
    layout: function() {
        this.layoutPrepare();
        this.layoutCalcBounds();
    },
    
    layoutPrepare: function(order) {
        for (i in this.graph.nodes) {
            var node = this.graph.nodes[i];
            node.layoutPosX = 0;
            node.layoutPosY = 0;
        }
        //to reverse the order of rendering, we need to find out the
        //absolute number of levels we have. simple log math applies.
        var numNodes = this.order.length;
        var totalLevels = Math.floor(Math.log(numNodes) / Math.log(2));
        
        var counter = 1;
        for (i in this.order) {
            var node = this.order[i];
            //rank aka x coordinate 
            var rank = Math.floor(Math.log(counter) / Math.log(2));
            //file relative to top
            var file = counter - Math.pow(rank, 2);
            
            log('Node ' + node.id + '  #' + counter + ' is at rank ' + rank + ' file ' + file);
            node.layoutPosX = totalLevels - rank;
            node.layoutPosY = file;
            counter++;
        }
    },
    
    layoutCalcBounds: function() {
        var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;

        for (i in this.graph.nodes) {
            var x = this.graph.nodes[i].layoutPosX;
            var y = this.graph.nodes[i].layoutPosY;
            
            if(x > maxx) maxx = x;
            if(x < minx) minx = x;
            if(y > maxy) maxy = y;
            if(y < miny) miny = y;
        }

        this.graph.layoutMinX = minx;
        this.graph.layoutMaxX = maxx;

        this.graph.layoutMinY = miny;
        this.graph.layoutMaxY = maxy;
    }
};


Graph.Layout.TournamentTree = function(graph, order) {
    this.graph = graph;
    this.order = order;
    this.layout();
};

/*
 * TournamentTree looks more like a binary tree
 */
Graph.Layout.TournamentTree.prototype = {
    layout: function() {
        this.layoutPrepare();
        this.layoutCalcBounds();
    },
    
    layoutPrepare: function(order) {
        for (i in this.graph.nodes) {
            var node = this.graph.nodes[i];
            node.layoutPosX = 0;
            node.layoutPosY = 0;
        }
        //to reverse the order of rendering, we need to find out the
        //absolute number of levels we have. simple log math applies.
        var numNodes = this.order.length;
        var totalLevels = Math.floor(Math.log(numNodes) / Math.log(2));
        
        var counter = 1;
        for (i in this.order) {
            var node = this.order[i];
            var depth = Math.floor(Math.log(counter) / Math.log(2));
            var xpos = counter - Math.pow(depth, 2);
            var offset = Math.pow(2, totalLevels - depth);
            var final_x = offset + (counter - Math.pow(2,depth)) * Math.pow(2,(totalLevels - depth)+1);
            
            log('Node ' + node.id + '  #' + counter + ' is at depth ' + depth + ' offset ' + offset + ' final_x ' + final_x);
            node.layoutPosX = final_x;
            node.layoutPosY = depth;
            counter++;
        }
    },
    
    layoutCalcBounds: function() {
        var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;

        for (i in this.graph.nodes) {
            var x = this.graph.nodes[i].layoutPosX;
            var y = this.graph.nodes[i].layoutPosY;
            
            if(x > maxx) maxx = x;
            if(x < minx) minx = x;
            if(y > maxy) maxy = y;
            if(y < miny) miny = y;
        }

        this.graph.layoutMinX = minx;
        this.graph.layoutMaxX = maxx;

        this.graph.layoutMinY = miny;
        this.graph.layoutMaxY = maxy;
    }
};




/*
 * usefull JavaScript extensions,
 */

function log(a) {console.log&&console.log(a);}

/*
 * Raphael Tooltip Plugin
 * - attaches an element as a tooltip to another element
 *
 * Usage example, adding a rectangle as a tooltip to a circle:
 *
 *      paper.circle(100,100,10).tooltip(paper.rect(0,0,20,30));
 *
 * If you want to use more shapes, you'll have to put them into a set.
 *
 */
Raphael.el.tooltip = function (tp) {
    this.tp = tp;
    this.tp.o = {x: 0, y: 0};
    this.tp.hide();
    this.hover(
        function(event){
            this.mousemove(function(event){
                this.tp.translate(event.clientX -
                                  this.tp.o.x,event.clientY - this.tp.o.y);
                this.tp.o = {x: event.clientX, y: event.clientY};
            });
            this.tp.show().toFront();
        },
        function(event){
            this.tp.hide();
            this.unmousemove();
        });
    return this;
};

/* For IE */
if (!Array.prototype.forEach)
{
  Array.prototype.forEach = function(fun /*, thisp*/)
  {
    var len = this.length;
    if (typeof fun != "function")
      throw new TypeError();

    var thisp = arguments[1];
    for (var i = 0; i < len; i++)
    {
      if (i in this)
        fun.call(thisp, this[i], i, this);
    }
  };
}

{'fraction_non_alphanumeric': 0.1406313964408698, 'fraction_numerical': 0.009776771738868689, 'mean_word_length': 1.889306338273151, 'pattern_counts': {'":': 8, '<': 73, '<?xml version=': 0, '>': 59, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '190570', 'n_tokens_mistral': 13562, 'n_tokens_neox': 13095, 'n_words': 3255}