About

Digraphs are short for directed graphics - a method to represent data in terms of nodes (or vertices) and how they're connected, via edges. As usual, read the Wiki page. Here are some simple examples:

Example 1:

Example 2:

This page demonstrates a JavaScript/NodeJS library I wrote that lets you program a graph, generate a dot file, which can then be turned into an image, as shown above.

In fact, you can describe the process of creating digraphs in a digraph itself!

I had originally written the library (link below) to generate a map of all the levels in Jet Set Willy. I created one version with text labels, and another with images. (Both too big for this page, so click to enlarge.)


[Click to enlarge]


[Click to enlarge]

From here I did what any self-respecting geek would do - write a disassembler for the Z80 chip, retrieve the ROM image from a ZX81, create nodes for each Z80 instruction in the ROM, collapse the nodes that didn't get interupted by jumps, and build a digraph from that!


[Click to enlarge]


Example 1

This is how we can, programmatically, generate a digraph.

  var di = new digraph();

  var n1 = di.addNode('One');
  var n2 = di.addNode('Two');
  var n3 = di.addNode('Three');

  di.addConnection(n1, n2);
  di.addConnection(n1, n3);

  di.setOption('rankdir', 'LR');

  console.log(di.generateDot());
Which outputs a dot file:
digraph G {
  "_1" [label="One" ];
  "_2" [label="Two" ];
  "_3" [label="Three" ];
  "_1" -> "_2";
  "_1" -> "_3";
}
That renders with
dot -Tpng ex1.dot -o ex1.png
as:

Example 2 - Pascal's Triangle

As you might have guessed, recursion lends itself very well to this type of graph.

function ex2() {
  var di = new digraph();

  addPascal(di, 0, 0, 3);

  console.log(di.generateDot());
}

function addPascal(di, a, b, max_depth) {
  var label = '(' + a + ' ' + b + ')';
  var us = di.findOrAddNode(label);

  if (--max_depth) {
    var left = addPascal(di, a+1, b, max_depth);
    var right = addPascal(di, a+1, b+1, max_depth);
    di.addConnection(us, left);
    di.addConnection(us, right);
  }

  return us;
}
Which outputs a dot file:
digraph G {
  "_1" [label="(0 0)" ];
  "_2" [label="(1 0)" ];
  "_3" [label="(2 0)" ];
  "_4" [label="(2 1)" ];
  "_5" [label="(1 1)" ];
  "_6" [label="(2 2)" ];
  "_2" -> "_3";
  "_2" -> "_4";
  "_5" -> "_4";
  "_5" -> "_6";
  "_1" -> "_2";
  "_1" -> "_5";
}

That renders as:

Example 3 - Pascal's Triangle

Obviously, recursion only gets you so far. Specifically, it gets you as far as your stack will allow! Therefore, we now support a non-recursion version where your function must 'request' each new item to be generated. Your function is then called to generate a new node, and return it to the library.

Here is the same Pascal's triangle example, using this mechanism. Since I don't want duplicate connections (or nodes containing the same data) I use checks to prevent this via findOrAddNode and isConnected.

function ex3() {
  var di = new digraph();
  di.traverse({a:1,b:1}, {max_depth:5}, cbhandler)
  .then(function() {
    console.log(di.generateDot());  
  })
}

function cbhandler(ref, userdata, handler) {
  var label = '(' + ref.a + ' ' + ref.b + ')';
  var us = handler.findOrAddNode(label); // in this case there is a 1:1 mapping between the label and its contents

  if (userdata.max_depth) {
    handler.request({a:ref.a+1, b:ref.b}, {max_depth:userdata.max_depth-1})
    .then(function(node) {
      if (!handler.isConnected(us,node))
        handler.addConnection(us, node);
    });

    handler.request({a:ref.a+1, b:ref.b+1}, {max_depth:userdata.max_depth-1})
    .then(function(node) {
      if (!handler.isConnected(us,node))
       handler.addConnection(us, node);
    });
  }

  return us;
}

Links

digraph NPM modules - The module written for this analysis

digraph NPM modules - The module, also on github

Generate images in the browser - A great way to test out your dot files

Jet Set Willy maps and digraphs - Generated with this library

Digraph in a digraph, in a digraph... - 8 levels deep!