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 for a detailed explanation, but 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.


Using the code

It's a typical NodeJS library, and so install with:

npm install jsdigraph

The build a simple example, such as:

 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());

Then type

node example.js >example_results.dot
The code outputs a dot file, which looks like this:
digraph G {
  "_1" [label="One" ];
  "_2" [label="Two" ];
  "_3" [label="Three" ];
  "_1" -> "_2";
  "_1" -> "_3";
}
That can be rendered into an image with:
dot -Tpng ex1.dot -o ex1.png
and appears as:


Becoming meta

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


Example 1 - Jet Set Willy

I had originally written the library (link below) to generate a map of all the levels in Jet Set Willy. Firstly, I created a 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 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;
}


Example 4 - Fighing Fantasy (City of Thieves)

When I was a kid, I was a massive fan of these books, and would draw maps of the game to try and beat it. As an adult, I explored the opportunity to work on a modern updating of these game books. I wrote a lot of prototypal code, built some things, and had some assets created. Furthermore, I spent hours and hours typing in all the data from book. It looked something like this:

/* page 69 */ {
  actions: [
    {attime: 'end', process: "testskill"}
  ],
  options: [
    {text: "You manage to release yourself", page: 355, condition: "true", process: "null"},
    {text: "You fail to release yourself", page: 151, condition: "true", process: "null"}
  ],
  monsters: [
  ]
},

Unfortunately, the deal never happened. So, on a quiet Sunday morning, I decided to build a digraph of the entire game world. Click on the image below for a full (very large) version!




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!