Automatically Finding Better Force Directed Layout Parameters (10x10 Grid)

.block

license: gpl-3.0
height: 600
scrolling: no
border: yes

README.md

This uses a simple grid search to find good force-directed graph layout parameters by measuring the average readability metric of each layout using Greadability.js.

See also:

• Automatically Finding Better Force Directed Layout Parameters (Les Miserables)
• Automatically Finding Better Force Directed Layout Parameters (Berlin U-Bahn)
• Force Directed Layout Quality Convergence

greadability.js

(function (global, factory) {
  typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
  typeof define === 'function' && define.amd ? define(['exports'], factory) :
  (factory((global.greadability = global.greadability || {})));
}(this, (function (exports) { 'use strict';

var greadability = function (nodes, links, id) {
  var i,
      j,
      n = nodes.length,
      m,
      degree = new Array(nodes.length),
      cMax,
      idealAngle = 70,
      dMax;

  /*
  * Tracks the global graph readability metrics.
  */
  var graphStats = {
    crossing: 0, // Normalized link crossings
    crossingAngle: 0, // Normalized average dev from 70 deg
    angularResolutionMin: 0, // Normalized avg dev from ideal min angle
    angularResolutionDev: 0, // Normalized avg dev from each link
  };

  var getSumOfArray = function (numArray) {
    var i = 0, n = numArray.length, sum = 0;
    for (; i < n; ++i) sum += numArray[i];
    return sum;
  };

  var initialize = function () {
    var i, j, link;
    var nodeById = {};
    // Filter out self loops
    links = links.filter(function (l) {
      return l.source !== l.target;
    });

    m = links.length;

    if (!id) {
      id = function (d) { return d.index; };
    }

    for (i = 0; i < n; ++i) {
      nodes[i].index = i;
      degree[i] = [];
      nodeById[id(nodes[i], i, nodeById)] = nodes[i];
    }

    // Make sure source and target are nodes and not indices.
    for (i = 0; i < m; ++i) {
      link = links[i];
      if (typeof link.source !== "object") link.source = nodeById[link.source];
      if (typeof link.target !== "object") link.target = nodeById[link.target];
    }

    // Filter out duplicate links
    var filteredLinks = [];
    links.forEach(function (l) {
      var s = l.source, t = l.target;
      if (s.index > t.index) {
        filteredLinks.push({source: t, target: s});
      } else {
        filteredLinks.push({source: s, target: t});
      }
    });
    links = filteredLinks;
    links.sort(function (a, b) {
      if (a.source.index < b.source.index) return -1;
      if (a.source.index > b.source.index) return 1;
      if (a.target.index < b.target.index) return -1;
      if (a.target.index > b.target.index) return 1;
      return 0;
    });
    i = 1;
    while (i < links.length) {
      if (links[i-1].source.index === links[i].source.index &&
        links[i-1].target.index === links[i].target.index) {
        links.splice(i, 1);
      }
      else ++i;
    }

    // Update length, if a duplicate was deleted.
    m = links.length;

    // Calculate degree.
    for (i = 0; i < m; ++i) {
      link = links[i];
      link.index = i;

      degree[link.source.index].push(link);
      degree[link.target.index].push(link);
    };
  }

  // Assume node.x and node.y are the coordinates

  function direction (pi, pj, pk) {
    var p1 = [pk[0] - pi[0], pk[1] - pi[1]];
    var p2 = [pj[0] - pi[0], pj[1] - pi[1]];
    return p1[0] * p2[1] - p2[0] * p1[1];
  }

  // Is point k on the line segment formed by points i and j?
  // Inclusive, so if pk == pi or pk == pj then return true.
  function onSegment (pi, pj, pk) {
    return Math.min(pi[0], pj[0]) <= pk[0] &&
      pk[0] <= Math.max(pi[0], pj[0]) &&
      Math.min(pi[1], pj[1]) <= pk[1] &&
      pk[1] <= Math.max(pi[1], pj[1]);
  }

  function linesCross (line1, line2) {
    var d1, d2, d3, d4;

    // CLRS 2nd ed. pg. 937
    d1 = direction(line2[0], line2[1], line1[0]);
    d2 = direction(line2[0], line2[1], line1[1]);
    d3 = direction(line1[0], line1[1], line2[0]);
    d4 = direction(line1[0], line1[1], line2[1]);

    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
      ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
      return true;
    } else if (d1 === 0 && onSegment(line2[0], line2[1], line1[0])) {
      return true;
    } else if (d2 === 0 && onSegment(line2[0], line2[1], line1[1])) {
      return true;
    } else if (d3 === 0 && onSegment(line1[0], line1[1], line2[0])) {
      return true;
    } else if (d4 === 0 && onSegment(line1[0], line1[1], line2[1])) {
      return true;
    }

    return false;
  }

  function linksCross (link1, link2) {
    // Self loops are not intersections
    if (link1.index === link2.index ||
      link1.source === link1.target ||
      link2.source === link2.target) {
      return false;
    }

    // Links cannot intersect if they share a node
    if (link1.source === link2.source ||
      link1.source === link2.target ||
      link1.target === link2.source ||
      link1.target === link2.target) {
      return false;
    }

    var line1 = [
      [link1.source.x, link1.source.y],
      [link1.target.x, link1.target.y]
    ];

    var line2 = [
      [link2.source.x, link2.source.y],
      [link2.target.x, link2.target.y]
    ];

    return linesCross(line1, line2);
  }

  function linkCrossings () {
    var i, j, c = 0, d = 0, link1, link2, line1, line2;;

    // Sum the upper diagonal of the edge crossing matrix.
    for (i = 0; i < m; ++i) {
      for (j = i + 1; j < m; ++j) {
        link1 = links[i], link2 = links[j];

        // Check if link i and link j intersect
        if (linksCross(link1, link2)) {
          line1 = [
            [link1.source.x, link1.source.y],
            [link1.target.x, link1.target.y]
          ];
          line2 = [
            [link2.source.x, link2.source.y],
            [link2.target.x, link2.target.y]
          ];
          ++c;
          d += Math.abs(idealAngle - acuteLinesAngle(line1, line2));
        }
      }
    }

    return {c: 2*c, d: 2*d};
  }

  function linesegmentsAngle (line1, line2) {
    // Finds the (counterclockwise) angle from line segement line1 to
    // line segment line2. Assumes the lines share one end point.
    // If both endpoints are the same, or if both lines have zero
    // length, then return 0 angle.
    // Param order matters:
    // linesegmentsAngle(line1, line2) != linesegmentsAngle(line2, line1)
    var temp, len, angle1, angle2, sLine1, sLine2;

    // Re-orient so that line1[0] and line2[0] are the same.
    if (line1[0][0] === line2[1][0] && line1[0][1] === line2[1][1]) {
      temp = line2[1];
      line2[1] = line2[0];
      line2[0] = temp;
    } else if (line1[1][0] === line2[0][0] && line1[1][1] === line2[0][1]) {
      temp = line1[1];
      line1[1] = line1[0];
      line1[0] = temp;
    } else if (line1[1][0] === line2[1][0] && line1[1][1] === line2[1][1]) {
      temp = line1[1];
      line1[1] = line1[0];
      line1[0] = temp;
      temp = line2[1];
      line2[1] = line2[0];
      line2[0] = temp;
    }

    // Shift the line so that the first point is at (0,0).
    sLine1 = [
      [line1[0][0] - line1[0][0], line1[0][1] - line1[0][1]],
      [line1[1][0] - line1[0][0], line1[1][1] - line1[0][1]]
    ];
    // Normalize the line length.
    len = Math.hypot(sLine1[1][0], sLine1[1][1]);
    if (len === 0) return 0;
    sLine1[1][0] /= len;
    sLine1[1][1] /= len;
    // If y < 0, angle = acos(x), otherwise angle = 360 - acos(x)
    angle1 = Math.acos(sLine1[1][0]) * 180 / Math.PI;
    if (sLine1[1][1] < 0) angle1 = 360 - angle1;

    // Shift the line so that the first point is at (0,0).
    sLine2 = [
      [line2[0][0] - line2[0][0], line2[0][1] - line2[0][1]],
      [line2[1][0] - line2[0][0], line2[1][1] - line2[0][1]]
    ];
    // Normalize the line length.
    len = Math.hypot(sLine2[1][0], sLine2[1][1]);
    if (len === 0) return 0;
    sLine2[1][0] /= len;
    sLine2[1][1] /= len;
    // If y < 0, angle = acos(x), otherwise angle = 360 - acos(x)
    angle2 = Math.acos(sLine2[1][0]) * 180 / Math.PI;
    if (sLine2[1][1] < 0) angle2 = 360 - angle2;

    return angle1 <= angle2 ? angle2 - angle1 : 360 - (angle1 - angle2);
  }

  function acuteLinesAngle (line1, line2) {
    // Acute angle of intersection, in degrees. Assumes these lines
    // intersect.
    var slope1 = (line1[1][1] - line1[0][1]) / (line1[1][0] - line1[0][0]);
    var slope2 = (line2[1][1] - line2[0][1]) / (line2[1][0] - line2[0][0]);

    // If these lines are two links incident on the same node, need
    // to check if the angle is 0 or 180.
    if (slope1 === slope2) {
      // If line2 is not on line1 and line1 is not on line2, then
      // the lines share only one point and the angle must be 180.
      if (!(onSegment(line1[0], line1[1], line2[0]) && onSegment(line1[0], line1[1], line2[1])) ||
        !(onSegment(line2[0], line2[1], line1[0]) && onSegment(line2[0], line2[1], line1[1])))
        return 180;
      else return 0;
    }

    var angle = Math.abs(Math.atan(slope1) - Math.atan(slope2));

    return (angle > Math.PI / 2 ? Math.PI - angle : angle) * 180 / Math.PI;
  }

  function angularRes () {
    var j,
        resMin = 0,
        resDev = 0,
        nonZeroDeg,
        node,
        minAngle,
        idealMinAngle,
        incident,
        line0,
        line1,
        line2,
        incidentLinkAngles,
        nextLink;

    nonZeroDeg = degree.filter(function (d) { return d.length >= 1; }).length;

    for (j = 0; j < n; ++j) {
      node = nodes[j];
      line0 = [[node.x, node.y], [node.x+1, node.y]];

      // Links that are incident to this node (already filtered out self loops)
      incident = degree[j];

      if (incident.length <= 1) continue;

      idealMinAngle = 360 / incident.length;

      // Sort edges by the angle they make from an imaginary vector
      // emerging at angle 0 on the unit circle.
      // Necessary for calculating angles of incident edges correctly
      incident.sort(function (a, b) {
        line1 = [
          [a.source.x, a.source.y],
          [a.target.x, a.target.y]
        ];
        line2 = [
          [b.source.x, b.source.y],
          [b.target.x, b.target.y]
        ];
        var angleA = linesegmentsAngle(line0, line1);
        var angleB = linesegmentsAngle(line0, line2);
        return angleA < angleB ? -1 : angleA > angleB ? 1 : 0;
      });

      incidentLinkAngles = incident.map(function (l, i) {
        nextLink = incident[(i + 1) % incident.length];
        line1 = [
          [l.source.x, l.source.y],
          [l.target.x, l.target.y]
        ];
        line2 = [
          [nextLink.source.x, nextLink.source.y],
          [nextLink.target.x, nextLink.target.y]
        ];
        return linesegmentsAngle(line1, line2);
      });

      minAngle = Math.min.apply(null, incidentLinkAngles);

      resMin += Math.abs(idealMinAngle - minAngle) / idealMinAngle;

      resDev += getSumOfArray(incidentLinkAngles.map(function (angle) {
        return Math.abs(idealMinAngle - angle) / idealMinAngle;
      })) / (2 * incident.length - 2);
    }

    // Divide by number of nodes with degree != 0
    resMin = resMin / nonZeroDeg;

    // Divide by number of nodes with degree != 0
    resDev = resDev / nonZeroDeg;

    return {resMin: resMin, resDev: resDev};
  }

  initialize();

  cMax = (m * (m - 1) / 2) - getSumOfArray(degree.map(function (d) { return d.length * (d.length - 1); })) / 2;

  var crossInfo = linkCrossings();

  dMax = crossInfo.c * idealAngle;

  graphStats.crossing = 1 - (cMax > 0 ? crossInfo.c / cMax : 0);

  graphStats.crossingAngle = 1 - (dMax > 0 ? crossInfo.d / dMax : 0);

  var angularResInfo = angularRes();

  graphStats.angularResolutionMin = 1 - angularResInfo.resMin;

  graphStats.angularResolutionDev = 1 - angularResInfo.resDev;

  return graphStats;
};

exports.greadability = greadability;

Object.defineProperty(exports, '__esModule', { value: true });

})));

grid10x10.json

{
  "nodes": [
    {
      "index": 0
    },
    {
      "index": 1
    },
    {
      "index": 2
    },
    {
      "index": 3
    },
    {
      "index": 4
    },
    {
      "index": 5
    },
    {
      "index": 6
    },
    {
      "index": 7
    },
    {
      "index": 8
    },
    {
      "index": 9
    },
    {
      "index": 10
    },
    {
      "index": 11
    },
    {
      "index": 12
    },
    {
      "index": 13
    },
    {
      "index": 14
    },
    {
      "index": 15
    },
    {
      "index": 16
    },
    {
      "index": 17
    },
    {
      "index": 18
    },
    {
      "index": 19
    },
    {
      "index": 20
    },
    {
      "index": 21
    },
    {
      "index": 22
    },
    {
      "index": 23
    },
    {
      "index": 24
    },
    {
      "index": 25
    },
    {
      "index": 26
    },
    {
      "index": 27
    },
    {
      "index": 28
    },
    {
      "index": 29
    },
    {
      "index": 30
    },
    {
      "index": 31
    },
    {
      "index": 32
    },
    {
      "index": 33
    },
    {
      "index": 34
    },
    {
      "index": 35
    },
    {
      "index": 36
    },
    {
      "index": 37
    },
    {
      "index": 38
    },
    {
      "index": 39
    },
    {
      "index": 40
    },
    {
      "index": 41
    },
    {
      "index": 42
    },
    {
      "index": 43
    },
    {
      "index": 44
    },
    {
      "index": 45
    },
    {
      "index": 46
    },
    {
      "index": 47
    },
    {
      "index": 48
    },
    {
      "index": 49
    },
    {
      "index": 50
    },
    {
      "index": 51
    },
    {
      "index": 52
    },
    {
      "index": 53
    },
    {
      "index": 54
    },
    {
      "index": 55
    },
    {
      "index": 56
    },
    {
      "index": 57
    },
    {
      "index": 58
    },
    {
      "index": 59
    },
    {
      "index": 60
    },
    {
      "index": 61
    },
    {
      "index": 62
    },
    {
      "index": 63
    },
    {
      "index": 64
    },
    {
      "index": 65
    },
    {
      "index": 66
    },
    {
      "index": 67
    },
    {
      "index": 68
    },
    {
      "index": 69
    },
    {
      "index": 70
    },
    {
      "index": 71
    },
    {
      "index": 72
    },
    {
      "index": 73
    },
    {
      "index": 74
    },
    {
      "index": 75
    },
    {
      "index": 76
    },
    {
      "index": 77
    },
    {
      "index": 78
    },
    {
      "index": 79
    },
    {
      "index": 80
    },
    {
      "index": 81
    },
    {
      "index": 82
    },
    {
      "index": 83
    },
    {
      "index": 84
    },
    {
      "index": 85
    },
    {
      "index": 86
    },
    {
      "index": 87
    },
    {
      "index": 88
    },
    {
      "index": 89
    },
    {
      "index": 90
    },
    {
      "index": 91
    },
    {
      "index": 92
    },
    {
      "index": 93
    },
    {
      "index": 94
    },
    {
      "index": 95
    },
    {
      "index": 96
    },
    {
      "index": 97
    },
    {
      "index": 98
    },
    {
      "index": 99
    }
  ],
  "links": [
    {
      "source": 0,
      "target": 1
    },
    {
      "source": 1,
      "target": 2
    },
    {
      "source": 2,
      "target": 3
    },
    {
      "source": 3,
      "target": 4
    },
    {
      "source": 4,
      "target": 5
    },
    {
      "source": 5,
      "target": 6
    },
    {
      "source": 6,
      "target": 7
    },
    {
      "source": 7,
      "target": 8
    },
    {
      "source": 8,
      "target": 9
    },
    {
      "source": 0,
      "target": 10
    },
    {
      "source": 1,
      "target": 11
    },
    {
      "source": 10,
      "target": 11
    },
    {
      "source": 2,
      "target": 12
    },
    {
      "source": 11,
      "target": 12
    },
    {
      "source": 3,
      "target": 13
    },
    {
      "source": 12,
      "target": 13
    },
    {
      "source": 4,
      "target": 14
    },
    {
      "source": 13,
      "target": 14
    },
    {
      "source": 5,
      "target": 15
    },
    {
      "source": 14,
      "target": 15
    },
    {
      "source": 6,
      "target": 16
    },
    {
      "source": 15,
      "target": 16
    },
    {
      "source": 7,
      "target": 17
    },
    {
      "source": 16,
      "target": 17
    },
    {
      "source": 8,
      "target": 18
    },
    {
      "source": 17,
      "target": 18
    },
    {
      "source": 9,
      "target": 19
    },
    {
      "source": 18,
      "target": 19
    },
    {
      "source": 10,
      "target": 20
    },
    {
      "source": 11,
      "target": 21
    },
    {
      "source": 20,
      "target": 21
    },
    {
      "source": 12,
      "target": 22
    },
    {
      "source": 21,
      "target": 22
    },
    {
      "source": 13,
      "target": 23
    },
    {
      "source": 22,
      "target": 23
    },
    {
      "source": 14,
      "target": 24
    },
    {
      "source": 23,
      "target": 24
    },
    {
      "source": 15,
      "target": 25
    },
    {
      "source": 24,
      "target": 25
    },
    {
      "source": 16,
      "target": 26
    },
    {
      "source": 25,
      "target": 26
    },
    {
      "source": 17,
      "target": 27
    },
    {
      "source": 26,
      "target": 27
    },
    {
      "source": 18,
      "target": 28
    },
    {
      "source": 27,
      "target": 28
    },
    {
      "source": 19,
      "target": 29
    },
    {
      "source": 28,
      "target": 29
    },
    {
      "source": 20,
      "target": 30
    },
    {
      "source": 21,
      "target": 31
    },
    {
      "source": 30,
      "target": 31
    },
    {
      "source": 22,
      "target": 32
    },
    {
      "source": 31,
      "target": 32
    },
    {
      "source": 23,
      "target": 33
    },
    {
      "source": 32,
      "target": 33
    },
    {
      "source": 24,
      "target": 34
    },
    {
      "source": 33,
      "target": 34
    },
    {
      "source": 25,
      "target": 35
    },
    {
      "source": 34,
      "target": 35
    },
    {
      "source": 26,
      "target": 36
    },
    {
      "source": 35,
      "target": 36
    },
    {
      "source": 27,
      "target": 37
    },
    {
      "source": 36,
      "target": 37
    },
    {
      "source": 28,
      "target": 38
    },
    {
      "source": 37,
      "target": 38
    },
    {
      "source": 29,
      "target": 39
    },
    {
      "source": 38,
      "target": 39
    },
    {
      "source": 30,
      "target": 40
    },
    {
      "source": 31,
      "target": 41
    },
    {
      "source": 40,
      "target": 41
    },
    {
      "source": 32,
      "target": 42
    },
    {
      "source": 41,
      "target": 42
    },
    {
      "source": 33,
      "target": 43
    },
    {
      "source": 42,
      "target": 43
    },
    {
      "source": 34,
      "target": 44
    },
    {
      "source": 43,
      "target": 44
    },
    {
      "source": 35,
      "target": 45
    },
    {
      "source": 44,
      "target": 45
    },
    {
      "source": 36,
      "target": 46
    },
    {
      "source": 45,
      "target": 46
    },
    {
      "source": 37,
      "target": 47
    },
    {
      "source": 46,
      "target": 47
    },
    {
      "source": 38,
      "target": 48
    },
    {
      "source": 47,
      "target": 48
    },
    {
      "source": 39,
      "target": 49
    },
    {
      "source": 48,
      "target": 49
    },
    {
      "source": 40,
      "target": 50
    },
    {
      "source": 41,
      "target": 51
    },
    {
      "source": 50,
      "target": 51
    },
    {
      "source": 42,
      "target": 52
    },
    {
      "source": 51,
      "target": 52
    },
    {
      "source": 43,
      "target": 53
    },
    {
      "source": 52,
      "target": 53
    },
    {
      "source": 44,
      "target": 54
    },
    {
      "source": 53,
      "target": 54
    },
    {
      "source": 45,
      "target": 55
    },
    {
      "source": 54,
      "target": 55
    },
    {
      "source": 46,
      "target": 56
    },
    {
      "source": 55,
      "target": 56
    },
    {
      "source": 47,
      "target": 57
    },
    {
      "source": 56,
      "target": 57
    },
    {
      "source": 48,
      "target": 58
    },
    {
      "source": 57,
      "target": 58
    },
    {
      "source": 49,
      "target": 59
    },
    {
      "source": 58,
      "target": 59
    },
    {
      "source": 50,
      "target": 60
    },
    {
      "source": 51,
      "target": 61
    },
    {
      "source": 60,
      "target": 61
    },
    {
      "source": 52,
      "target": 62
    },
    {
      "source": 61,
      "target": 62
    },
    {
      "source": 53,
      "target": 63
    },
    {
      "source": 62,
      "target": 63
    },
    {
      "source": 54,
      "target": 64
    },
    {
      "source": 63,
      "target": 64
    },
    {
      "source": 55,
      "target": 65
    },
    {
      "source": 64,
      "target": 65
    },
    {
      "source": 56,
      "target": 66
    },
    {
      "source": 65,
      "target": 66
    },
    {
      "source": 57,
      "target": 67
    },
    {
      "source": 66,
      "target": 67
    },
    {
      "source": 58,
      "target": 68
    },
    {
      "source": 67,
      "target": 68
    },
    {
      "source": 59,
      "target": 69
    },
    {
      "source": 68,
      "target": 69
    },
    {
      "source": 60,
      "target": 70
    },
    {
      "source": 61,
      "target": 71
    },
    {
      "source": 70,
      "target": 71
    },
    {
      "source": 62,
      "target": 72
    },
    {
      "source": 71,
      "target": 72
    },
    {
      "source": 63,
      "target": 73
    },
    {
      "source": 72,
      "target": 73
    },
    {
      "source": 64,
      "target": 74
    },
    {
      "source": 73,
      "target": 74
    },
    {
      "source": 65,
      "target": 75
    },
    {
      "source": 74,
      "target": 75
    },
    {
      "source": 66,
      "target": 76
    },
    {
      "source": 75,
      "target": 76
    },
    {
      "source": 67,
      "target": 77
    },
    {
      "source": 76,
      "target": 77
    },
    {
      "source": 68,
      "target": 78
    },
    {
      "source": 77,
      "target": 78
    },
    {
      "source": 69,
      "target": 79
    },
    {
      "source": 78,
      "target": 79
    },
    {
      "source": 70,
      "target": 80
    },
    {
      "source": 71,
      "target": 81
    },
    {
      "source": 80,
      "target": 81
    },
    {
      "source": 72,
      "target": 82
    },
    {
      "source": 81,
      "target": 82
    },
    {
      "source": 73,
      "target": 83
    },
    {
      "source": 82,
      "target": 83
    },
    {
      "source": 74,
      "target": 84
    },
    {
      "source": 83,
      "target": 84
    },
    {
      "source": 75,
      "target": 85
    },
    {
      "source": 84,
      "target": 85
    },
    {
      "source": 76,
      "target": 86
    },
    {
      "source": 85,
      "target": 86
    },
    {
      "source": 77,
      "target": 87
    },
    {
      "source": 86,
      "target": 87
    },
    {
      "source": 78,
      "target": 88
    },
    {
      "source": 87,
      "target": 88
    },
    {
      "source": 79,
      "target": 89
    },
    {
      "source": 88,
      "target": 89
    },
    {
      "source": 80,
      "target": 90
    },
    {
      "source": 81,
      "target": 91
    },
    {
      "source": 90,
      "target": 91
    },
    {
      "source": 82,
      "target": 92
    },
    {
      "source": 91,
      "target": 92
    },
    {
      "source": 83,
      "target": 93
    },
    {
      "source": 92,
      "target": 93
    },
    {
      "source": 84,
      "target": 94
    },
    {
      "source": 93,
      "target": 94
    },
    {
      "source": 85,
      "target": 95
    },
    {
      "source": 94,
      "target": 95
    },
    {
      "source": 86,
      "target": 96
    },
    {
      "source": 95,
      "target": 96
    },
    {
      "source": 87,
      "target": 97
    },
    {
      "source": 96,
      "target": 97
    },
    {
      "source": 88,
      "target": 98
    },
    {
      "source": 97,
      "target": 98
    },
    {
      "source": 89,
      "target": 99
    },
    {
      "source": 98,
      "target": 99
    }
  ]
}

index.html

<!DOCTYPE html>
<meta charset="utf-8">
<style>

html, body {
  font: 12px sans-serif;
}

svg {
  display: block;
}

.links line {
  stroke: #999;
  stroke-opacity: 0.6;
  stroke-width: 2px;
}

.nodes circle {
  fill: #d30000;
  stroke: #fff;
  stroke-width: 1px;
}

.chart circle {
  fill: #aaa;
  fill-opacity: 0.1;
  stroke: #aaa;
  stroke-opacity: 0.4;
  cursor: pointer;
}

.chart circle.selected {
  fill: #d30000;
  fill-opacity: 0.6;
  stroke: #d30000;
  stroke-opacity: 0.8;
}

.column {
  float: left;
  margin: 0 10px;
}

</style>
<div class="column">
<svg class="chart"></svg>
<svg class="graph"></svg>
</div>
<div class="column">
<p class="progress">Testing</p>
<p>Best parameters so far:</p>
<ul class="best"></ul>
</div>
<script src="greadability.js"></script>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>

var width = 600;
var height = 500;

var chartWidth = 600;
var chartHeight = 60;
var margin = {left: 10, right: 10, top: 10, bottom: 40};

var numTicks = 150;

var selectedParams;
var bestParams;

var dispatch = d3.dispatch('layoutend');

var svg = d3.select('svg.graph')
  .attr('width', width)
  .attr('height', height);

var chartSvg = d3.select('svg.chart')
  .attr('width', chartWidth)
  .attr('height', chartHeight)
  .append('g')
  .attr('transform', 'translate(' + margin.left + ',' + margin.top + ')');

chartWidth = chartWidth - margin.left - margin.right;
chartHeight = chartHeight - margin.top - margin.bottom;

var x = d3.scaleLinear()
  .domain([0, 1])
  .range([0, chartWidth]);

chartSvg.append('g')
    .attr('transform', 'translate(0,' + chartHeight + ')')
    .call(d3.axisBottom(x).ticks(7))
  .append("text")
    .attr("fill", "#000")
    .attr('transform', 'translate(' + chartWidth/2 + ',' + 0 + ')')
    .attr("y", chartHeight + 10)
    .attr("dy", "0.71em")
    .attr("text-anchor", "middle")
    .text("Average readability score");

var readabilityCircles = chartSvg.append('g').selectAll('circle');

d3.json('grid10x10.json', function (error, graph) {
  if (error) throw error;

  var link = svg.append('g')
    .attr('class', 'links')
    .selectAll('line')
    .data(graph.links)
    .enter().append('line');

  var node = svg.append('g')
    .attr('class', 'nodes')
    .selectAll('circle')
    .data(graph.nodes)
    .enter().append('circle')
    .attr('r', 4);

  node.append('title').text(function (d) { return d.name; });

  var paramGroups = [
    {name: 'chargeStrength', values: [-30, -80]},
    {name: 'linkDistance', values: [30, -80]},
    {name: 'linkStrength', values: [null, 0.25]},
    {name: 'gravity', values: [0, 0.5]},
    {name: 'iterations', values: [1, 2]},
    {name: 'alphaDecay', values: [0, 0.0228, 0.05]},
    {name: 'velocityDecay', values: [0.4, 0.8]}
  ];

  var paramList = generateParams(paramGroups);

  var bestSoFar = d3.select('.best').selectAll('li')
    .data(paramGroups.map(function (d) { return d.name; }))
    .enter().append('li')
    .text(function (d) { return d; });

  dispatch.on('layoutend', function (params, i) {
    if (!bestParams || params.graphReadability > bestParams.graphReadability) {
      bestParams = params;
      selectedParams = bestParams;

      bestSoFar
        .data(d3.map(bestParams).keys().filter(function (d) { return d !== 'positions' && d !== 'graphReadability'; }))
        .text(function (d) { return d + ' = ' + bestParams[d]; });
    }

    d3.select('.progress').text('Testing ' + (i + 1) + ' of ' + paramList.length + ' parameter settings');

    // Plot the number line.
    readabilityCircles = readabilityCircles
      .data(readabilityCircles.data().concat(params))
      .enter().append('circle')
      .attr('cx', function (d) { return x(d.graphReadability); })
      .attr('cy', 5)
      .attr('r', 4)
      .on('click', function (d) {
        selectedParams = d;
        readabilityCircles.classed('selected', false);
        d3.select(this).classed('selected', true).raise();

        bestSoFar
          .data(d3.map(selectedParams).keys().filter(function (d) { return d !== 'positions' && d !== 'graphReadability'; }))
          .text(function (d) { return d + ' = ' + selectedParams[d]; });

        drawGraph();
      })
      .merge(readabilityCircles)
      .classed('selected', function (d) { return d === selectedParams; });

    readabilityCircles.filter(function (d) { return d === selectedParams; })
      .raise();

    drawGraph();
  });

  var i = 0;
  var stepper = d3.timer(function () {
    var p = paramList[i];
    var forceSim = getForceSimFromParams(p);

    // Reset node attributes.
    graph.nodes.forEach(function (n) {
      n.x = n.y = n.vx = n.vy = 0;
    });

    forceSim.nodes(graph.nodes)
      .stop();

    forceSim.force('link')
      .links(graph.links);

    for (var t = 0; t < numTicks; ++t) {
      forceSim.tick();
    }

    p.graphReadability = greadability.greadability(graph.nodes, graph.links);
    p.graphReadability = (p.graphReadability.crossing + p.graphReadability.crossingAngle +
      p.graphReadability.angularResolutionMin + p.graphReadability.angularResolutionDev) / 4

    p.positions = graph.nodes.map(function (n) { return {x: n.x, y: n.y}; });

    dispatch.call('layoutend', forceSim, p, i);

    ++i;
    if (i >= paramList.length) {
      stepper.stop();
    }
  });

  function drawGraph () {
    graph.nodes.forEach(function (n, i) {
      n.x = selectedParams.positions[i].x;
      n.y = selectedParams.positions[i].y;
    });

    var xDistance = d3.extent(graph.nodes, function (n) { return n.x; });
    var xMin = xDistance[0];
    xDistance = xDistance[1] - xDistance[0];

    var yDistance = d3.extent(graph.nodes, function (n) { return n.y; });
    var yMin = yDistance[0];
    yDistance = yDistance[1] - yDistance[0];

    graph.nodes.forEach(function (n, i) {
      n.x = (height - 10) * (n.x - xMin) / Math.max(xDistance, yDistance);
      n.y = (height - 10) * (n.y - yMin) / Math.max(xDistance, yDistance);
    });

    xDistance = d3.extent(graph.nodes, function (n) { return n.x; });
    xMid = (xDistance[1] + xDistance[0]) / 2;
    yDistance = d3.extent(graph.nodes, function (n) { return n.y; });
    yMid = (yDistance[1] - yDistance[0]) / 2;

    graph.nodes.forEach(function (n, i) {
      n.x = n.x + width/2 - xMid;
      n.y = n.y + height/2 - yMid;
    });

    link
      .attr('x1', function (d) { return d.source.x; })
      .attr('x2', function (d) { return d.target.x; })
      .attr('y1', function (d) { return d.source.y; })
      .attr('y2', function (d) { return d.target.y; });

    node
      .attr('cx', function (d) { return d.x; })
      .attr('cy', function (d) { return d.y; });
  }
});

function generateParams (paramGroups, paramList, currParam) {
  var p = paramGroups[0];

  if (!paramList) paramList = [];

  if (!currParam) currParam = {};

  p.values.forEach(function (v) {
    var setting = {};
    setting[p.name] = v;
    if (paramGroups.length === 1) {
      paramList.push(Object.assign(setting, currParam));
    } else {
      generateParams(paramGroups.slice(1), paramList, Object.assign(setting, currParam));
    }
  });

  return paramList;
}

function getForceSimFromParams (params) {
  var forceSim = d3.forceSimulation()
    .force('link', d3.forceLink().iterations(params.iterations))
    .force('charge', d3.forceManyBody().strength(params.chargeStrength))
    .force('x', d3.forceX(0).strength(params.gravity))
    .force('y', d3.forceY(0).strength(params.gravity))
    .force('center', d3.forceCenter(0, 0))
    .alphaDecay(params.alphaDecay)
    .velocityDecay(params.velocityDecay);

  if (params.linkStrength !== null) {
    forceSim.force('link').strength(params.linkStrength);
  }

  return forceSim;
}

</script>

preview.png

thumbnail.png