Dijkstra on node-link diagram

README.md

A node-link diagram running a javascript implementation of the Dijkstra algorithm. Every time the visualization is refreshed two nodes are selected as start (in red) and end point (in blue). Then the shortest path is computed and shown on the diagram by highlighting the edges.

dijkstra.js

var Graph = (function (undefined) {

  var extractKeys = function (obj) {
    var keys = [], key;
    for (key in obj) {
        Object.prototype.hasOwnProperty.call(obj,key) && keys.push(key);
    }
    return keys;
  }

  var sorter = function (a, b) {
    return parseFloat (a) - parseFloat (b);
  }

  var findPaths = function (map, start, end, infinity) {
    infinity = infinity || Infinity;

    var costs = {},
        open = {'0': [start]},
        predecessors = {},
        keys;

    var addToOpen = function (cost, vertex) {
      var key = "" + cost;
      if (!open[key]) open[key] = [];
      open[key].push(vertex);
    }

    costs[start] = 0;

    while (open) {
      if(!(keys = extractKeys(open)).length) break;

      keys.sort(sorter);

      var key = keys[0],
          bucket = open[key],
          node = bucket.shift(),
          currentCost = parseFloat(key),
          adjacentNodes = map[node] || {};

      if (!bucket.length) delete open[key];

      for (var vertex in adjacentNodes) {
          if (Object.prototype.hasOwnProperty.call(adjacentNodes, vertex)) {
          var cost = adjacentNodes[vertex],
              totalCost = cost + currentCost,
              vertexCost = costs[vertex];

          if ((vertexCost === undefined) || (vertexCost > totalCost)) {
            costs[vertex] = totalCost;
            addToOpen(totalCost, vertex);
            predecessors[vertex] = node;
          }
        }
      }
    }

    if (costs[end] === undefined) {
      return null;
    } else {
      return predecessors;
    }

  }

  var extractShortest = function (predecessors, end) {
    var nodes = [],
        u = end;

    while (u) {
      nodes.push(u);
      u = predecessors[u];
    }

    nodes.reverse();
    return nodes;
  }

  var findShortestPath = function (map, nodes) {
    var start = nodes.shift(),
        end,
        predecessors,
        path = [],
        shortest;

    while (nodes.length) {
      end = nodes.shift();
      predecessors = findPaths(map, start, end);

      if (predecessors) {
        shortest = extractShortest(predecessors, end);
        if (nodes.length) {
          path.push.apply(path, shortest.slice(0, -1));
        } else {
          return path.concat(shortest);
        }
      } else {
        return null;
      }

      start = end;
    }
  }

  var toArray = function (list, offset) {
    try {
      return Array.prototype.slice.call(list, offset);
    } catch (e) {
      var a = [];
      for (var i = offset || 0, l = list.length; i < l; ++i) {
        a.push(list[i]);
      }
      return a;
    }
  }

  var Graph = function (map) {
    this.map = map;
  }

  Graph.prototype.findShortestPath = function (start, end) {
    if (Object.prototype.toString.call(start) === '[object Array]') {
      return findShortestPath(this.map, start);
    } else if (arguments.length === 2) {
      return findShortestPath(this.map, [start, end]);
    } else {
      return findShortestPath(this.map, toArray(arguments));
    }
  }

  Graph.findShortestPath = function (map, start, end) {
    if (Object.prototype.toString.call(start) === '[object Array]') {
      return findShortestPath(map, start);
    } else if (arguments.length === 3) {
      return findShortestPath(map, [start, end]);
    } else {
      return findShortestPath(map, toArray(arguments, 1));
    }
  }

  return Graph;

})();

index.coffee

circle_radius = 12

nodes = [{id: 'a'},{id: 'b'},{id: 'c'},{id: 'd'},{id: 'e'},{id: 'f'},{id: 'g'},{id: 'h'},{id: 'i'},{id: 'j'},{id: 'k'},{id: 'l'},{id: 'm'},{id: 'n'},{id: 'o'},{id: 'p'},{id: 'q'},{id: 'r'},{id: 's'},{id: 't'},{id: 'u'},{id: 'v'},{id: 'w'},{id: 'x'},{id: 'y'},{id: 'z'}]

a = nodes[Math.floor Math.random()*nodes.length]
a.start = true
a = a.id

b = nodes[Math.floor Math.random()*nodes.length]
b.end = true
b = b.id

links = [
  {source: 'a', target: 'b', value: Math.floor(Math.random()*10+1)}
  {source: 'a', target: 'c', value: Math.floor(Math.random()*10+1)}
  {source: 'd', target: 'n', value: Math.floor(Math.random()*10+1)}
  {source: 'c', target: 'b', value: Math.floor(Math.random()*10+1)}
  {source: 'c', target: 'e', value: Math.floor(Math.random()*10+1)}
  {source: 'e', target: 'g', value: Math.floor(Math.random()*10+1)}
  {source: 'f', target: 'h', value: Math.floor(Math.random()*10+1)}
  {source: 'h', target: 'm', value: Math.floor(Math.random()*10+1)}
  {source: 'i', target: 'z', value: Math.floor(Math.random()*10+1)}
  {source: 'z', target: 'l', value: Math.floor(Math.random()*10+1)}
  {source: 'r', target: 'b', value: Math.floor(Math.random()*10+1)}
  {source: 's', target: 'r', value: Math.floor(Math.random()*10+1)}
  {source: 'a', target: 's', value: Math.floor(Math.random()*10+1)}
  {source: 'c', target: 'o', value: Math.floor(Math.random()*10+1)}
  {source: 'o', target: 'b', value: Math.floor(Math.random()*10+1)}
  {source: 'x', target: 't', value: Math.floor(Math.random()*10+1)}
  {source: 't', target: 'm', value: Math.floor(Math.random()*10+1)}
  {source: 'w', target: 'd', value: Math.floor(Math.random()*10+1)}
  {source: 'y', target: 'k', value: Math.floor(Math.random()*10+1)}
  {source: 'i', target: 'k', value: Math.floor(Math.random()*10+1)}
  {source: 'x', target: 'z', value: Math.floor(Math.random()*10+1)}
  {source: 'm', target: 'e', value: Math.floor(Math.random()*10+1)}
  {source: 'j', target: 'h', value: Math.floor(Math.random()*10+1)}
  {source: 'i', target: 'j', value: Math.floor(Math.random()*10+1)}
  {source: 'u', target: 'e', value: Math.floor(Math.random()*10+1)}
  {source: 'm', target: 'a', value: Math.floor(Math.random()*10+1)}
  {source: 'x', target: 'l', value: Math.floor(Math.random()*10+1)}
  {source: 'l', target: 'n', value: Math.floor(Math.random()*10+1)}
  {source: 'n', target: 'a', value: Math.floor(Math.random()*10+1)}
  {source: 'v', target: 'm', value: Math.floor(Math.random()*10+1)}
  {source: 'q', target: 'a', value: Math.floor(Math.random()*10+1)}
  {source: 'p', target: 'l', value: Math.floor(Math.random()*10+1)}
  {source: 'q', target: 'n', value: Math.floor(Math.random()*10+1)}
  {source: 'y', target: 'f', value: Math.floor(Math.random()*10+1)}
]

graph = {nodes: nodes, links: links}

### Shortest Path
###
convert_graph = (graph) ->
  map = {}

  for n in graph.nodes
    for l in links
      if n.id is l.source

        if !(n.id of map)
          map[n.id] = {}
        
        map[n.id][l.target] = l.value

  return map

map = convert_graph graph

lib_graph = new Graph map
shortest_path = lib_graph.findShortestPath(a, b)

if shortest_path?
  for n,i in shortest_path
    if i < shortest_path.length-1
      link = {source: n, target: shortest_path[i+1]}

      for l in links
        if l.source is link.source and l.target is link.target
          l.covered = true

### Visualization
###
width = d3.select('body').node().getBoundingClientRect().width
height = d3.select('body').node().getBoundingClientRect().height

svg = d3.select 'svg'
  .attrs
    width: width
    height: height

defs = svg.append 'defs'

zoomable_layer = svg.append 'g'

zoom = d3.zoom()
  .scaleExtent([-Infinity,Infinity])
  .on 'zoom', () ->
    zoomable_layer
      .attrs
        transform: d3.event.transform

svg.call zoom

arrowheads = defs.append 'marker'
  .attrs
    class: 'arrowhead'
    id: 'arrow'
    viewBox: '0 0 10 10'
    refX: 6.5+circle_radius
    refY: 5
    orient: 'auto'

arrowheads.append 'path'
  .attrs
    d: 'M0,0 L0,10 L10,5 z'
    fill: '#dddddd'

sp_arrowheads = defs.append 'marker'
  .attrs
    class: 'arrowhead'
    id: 'sp_arrow'
    viewBox: '0 0 10 10'
    refX: 6.5+circle_radius
    refY: 5
    orient: 'auto'
    
sp_arrowheads.append 'path'
  .attrs
    d: 'M0,0 L0,10 L10,5 z'
    fill: '#ff9999'

### Force simulation
###
ticked = () ->
  zoomable_layer.selectAll '.node'
    .attrs
      transform: (d) -> "translate(#{d.x},#{d.y})"
      
  zoomable_layer.selectAll '.link'
    .attrs
      x1: (d) -> d.source.x
      y1: (d) -> d.source.y
      x2: (d) -> d.target.x
      y2: (d) -> d.target.y

  zoomable_layer.selectAll '.label'
    .attrs
      transform: (d) -> "translate(#{(d.source.x+d.target.x)/2},#{(d.source.y+d.target.y)/2})"

charge = d3.forceManyBody()
  .strength -300

simulation = d3.forceSimulation()
  .force 'link', d3.forceLink().id((d) -> d.id)
  .force 'charge', charge
  .force 'center', d3.forceCenter(width / 2, height / 2)

simulation
  .nodes graph.nodes
  .on 'tick', ticked

simulation.force 'link'
  .links graph.links

### Links
###
links = zoomable_layer.selectAll '.link'
  .data(graph.links, (d) -> d.id)
        
links.enter().append 'line'
  .attrs
    class: 'link'
    'marker-end': (d) -> if d.covered? and d.covered is true then 'url(#sp_arrow)' else 'url(#arrow)'
    stroke: (d) -> if d.covered? and d.covered is true then '#ff9999' else '#dddddd'
    
links.exit().remove()

# label links
labels = zoomable_layer.selectAll '.label'
  .data(graph.links, (d) -> d.id)
        
labels.enter().append 'text'
  .attrs
    class: 'label'
    'text-anchor': 'middle'
  .text (d) -> d.value

### Nodes
###
nodes = zoomable_layer.selectAll '.node'
  .data(graph.nodes, (d) -> d.id)
        
new_nodes = nodes.enter().append 'g'
  .attrs
    class: 'node'
    
new_nodes.append 'circle'
  .attrs
    r: circle_radius
    fill: (d) ->
      if d.start?
        '#ff9999'
      else if d.end?
        '#9999ff'
      else if d.id
        '#404040'

new_nodes.append 'text'
  .text (d) -> d.id
  .attr 'dy', '0.35em'
    
nodes.exit().remove()

index.css

html, body {
  padding: 0;
  margin: 0;
  width: 100%;
  height: 100%;
}

.node > text {
  font-family: sans-serif;
  text-anchor: middle;
  pointer-events: none;
  fill: #fff;
}

.link {
  stroke-width: 4px;
}

.label {
  font-size: 13px
}

index.html

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>Dijkstra on node-link diagram</title>
  <link type="text/css" href="index.css" rel="stylesheet"/>
  <script src="dijkstra.js"></script>
  <script src="https://d3js.org/d3.v4.min.js"></script>
  <script src="https://d3js.org/d3-selection-multi.v0.4.min.js"></script>
</head>
<body>
  <svg></svg>
  <script src="index.js"></script>
</body>
</html>

index.js

// Generated by CoffeeScript 1.10.0
(function() {
  var a, arrowheads, b, charge, circle_radius, convert_graph, defs, graph, height, i, j, k, l, labels, len, len1, lib_graph, link, links, map, n, new_nodes, nodes, shortest_path, simulation, sp_arrowheads, svg, ticked, width, zoom, zoomable_layer;

  circle_radius = 12;

  nodes = [
    {
      id: 'a'
    }, {
      id: 'b'
    }, {
      id: 'c'
    }, {
      id: 'd'
    }, {
      id: 'e'
    }, {
      id: 'f'
    }, {
      id: 'g'
    }, {
      id: 'h'
    }, {
      id: 'i'
    }, {
      id: 'j'
    }, {
      id: 'k'
    }, {
      id: 'l'
    }, {
      id: 'm'
    }, {
      id: 'n'
    }, {
      id: 'o'
    }, {
      id: 'p'
    }, {
      id: 'q'
    }, {
      id: 'r'
    }, {
      id: 's'
    }, {
      id: 't'
    }, {
      id: 'u'
    }, {
      id: 'v'
    }, {
      id: 'w'
    }, {
      id: 'x'
    }, {
      id: 'y'
    }, {
      id: 'z'
    }
  ];

  a = nodes[Math.floor(Math.random() * nodes.length)];

  a.start = true;

  a = a.id;

  b = nodes[Math.floor(Math.random() * nodes.length)];

  b.end = true;

  b = b.id;

  links = [
    {
      source: 'a',
      target: 'b',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'a',
      target: 'c',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'd',
      target: 'n',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'c',
      target: 'b',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'c',
      target: 'e',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'e',
      target: 'g',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'f',
      target: 'h',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'h',
      target: 'm',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'i',
      target: 'z',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'z',
      target: 'l',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'r',
      target: 'b',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 's',
      target: 'r',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'a',
      target: 's',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'c',
      target: 'o',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'o',
      target: 'b',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'x',
      target: 't',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 't',
      target: 'm',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'w',
      target: 'd',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'y',
      target: 'k',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'i',
      target: 'k',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'x',
      target: 'z',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'm',
      target: 'e',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'j',
      target: 'h',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'i',
      target: 'j',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'u',
      target: 'e',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'm',
      target: 'a',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'x',
      target: 'l',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'l',
      target: 'n',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'n',
      target: 'a',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'v',
      target: 'm',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'q',
      target: 'a',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'p',
      target: 'l',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'q',
      target: 'n',
      value: Math.floor(Math.random() * 10 + 1)
    }, {
      source: 'y',
      target: 'f',
      value: Math.floor(Math.random() * 10 + 1)
    }
  ];

  graph = {
    nodes: nodes,
    links: links
  };


  /* Shortest Path
   */

  convert_graph = function(graph) {
    var j, k, l, len, len1, map, n, ref;
    map = {};
    ref = graph.nodes;
    for (j = 0, len = ref.length; j < len; j++) {
      n = ref[j];
      for (k = 0, len1 = links.length; k < len1; k++) {
        l = links[k];
        if (n.id === l.source) {
          if (!(n.id in map)) {
            map[n.id] = {};
          }
          map[n.id][l.target] = l.value;
        }
      }
    }
    return map;
  };

  map = convert_graph(graph);

  lib_graph = new Graph(map);

  shortest_path = lib_graph.findShortestPath(a, b);

  if (shortest_path != null) {
    for (i = j = 0, len = shortest_path.length; j < len; i = ++j) {
      n = shortest_path[i];
      if (i < shortest_path.length - 1) {
        link = {
          source: n,
          target: shortest_path[i + 1]
        };
        for (k = 0, len1 = links.length; k < len1; k++) {
          l = links[k];
          if (l.source === link.source && l.target === link.target) {
            l.covered = true;
          }
        }
      }
    }
  }


  /* Visualization
   */

  width = d3.select('body').node().getBoundingClientRect().width;

  height = d3.select('body').node().getBoundingClientRect().height;

  svg = d3.select('svg').attrs({
    width: width,
    height: height
  });

  defs = svg.append('defs');

  zoomable_layer = svg.append('g');

  zoom = d3.zoom().scaleExtent([-Infinity, Infinity]).on('zoom', function() {
    return zoomable_layer.attrs({
      transform: d3.event.transform
    });
  });

  svg.call(zoom);

  arrowheads = defs.append('marker').attrs({
    "class": 'arrowhead',
    id: 'arrow',
    viewBox: '0 0 10 10',
    refX: 6.5 + circle_radius,
    refY: 5,
    orient: 'auto'
  });

  arrowheads.append('path').attrs({
    d: 'M0,0 L0,10 L10,5 z',
    fill: '#dddddd'
  });

  sp_arrowheads = defs.append('marker').attrs({
    "class": 'arrowhead',
    id: 'sp_arrow',
    viewBox: '0 0 10 10',
    refX: 6.5 + circle_radius,
    refY: 5,
    orient: 'auto'
  });

  sp_arrowheads.append('path').attrs({
    d: 'M0,0 L0,10 L10,5 z',
    fill: '#ff9999'
  });


  /* Force simulation
   */

  ticked = function() {
    zoomable_layer.selectAll('.node').attrs({
      transform: function(d) {
        return "translate(" + d.x + "," + d.y + ")";
      }
    });
    zoomable_layer.selectAll('.link').attrs({
      x1: function(d) {
        return d.source.x;
      },
      y1: function(d) {
        return d.source.y;
      },
      x2: function(d) {
        return d.target.x;
      },
      y2: function(d) {
        return d.target.y;
      }
    });
    return zoomable_layer.selectAll('.label').attrs({
      transform: function(d) {
        return "translate(" + ((d.source.x + d.target.x) / 2) + "," + ((d.source.y + d.target.y) / 2) + ")";
      }
    });
  };

  charge = d3.forceManyBody().strength(-300);

  simulation = d3.forceSimulation().force('link', d3.forceLink().id(function(d) {
    return d.id;
  })).force('charge', charge).force('center', d3.forceCenter(width / 2, height / 2));

  simulation.nodes(graph.nodes).on('tick', ticked);

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


  /* Links
   */

  links = zoomable_layer.selectAll('.link').data(graph.links, function(d) {
    return d.id;
  });

  links.enter().append('line').attrs({
    "class": 'link',
    'marker-end': function(d) {
      if ((d.covered != null) && d.covered === true) {
        return 'url(#sp_arrow)';
      } else {
        return 'url(#arrow)';
      }
    },
    stroke: function(d) {
      if ((d.covered != null) && d.covered === true) {
        return '#ff9999';
      } else {
        return '#dddddd';
      }
    }
  });

  links.exit().remove();

  labels = zoomable_layer.selectAll('.label').data(graph.links, function(d) {
    return d.id;
  });

  labels.enter().append('text').attrs({
    "class": 'label',
    'text-anchor': 'middle'
  }).text(function(d) {
    return d.value;
  });


  /* Nodes
   */

  nodes = zoomable_layer.selectAll('.node').data(graph.nodes, function(d) {
    return d.id;
  });

  new_nodes = nodes.enter().append('g').attrs({
    "class": 'node'
  });

  new_nodes.append('circle').attrs({
    r: circle_radius,
    fill: function(d) {
      if (d.start != null) {
        return '#ff9999';
      } else if (d.end != null) {
        return '#9999ff';
      } else if (d.id) {
        return '#404040';
      }
    }
  });

  new_nodes.append('text').text(function(d) {
    return d.id;
  }).attr('dy', '0.35em');

  nodes.exit().remove();

}).call(this);

thumbnail.png

Hi,
very interesting example. Is there a way for use it with undirected graphs?
Thanks