Now we know we have a diagram (possibly a set of diagrams, but we will deal with them one at a time) which has a set of fully connected nodes and we want to lay it out on a two-dimensional grid.
As I said before, I am no expert on graph theory or layout, so I'm not going to do anything complicated. I am going to lay out the nodes on a rectangular grid with "standard" coordinates starting at 0 and going right and down. It will be the job of the rendering engine to make that look nice by adapting those coordinates to something in real space.
The abstract model will have "shapes" and "connectors". A shape is simply at a point in this 2D space, and connectors run between them in the "gaps". This is slightly more difficult to describe, but I view the space between the shapes as being like rivers or canals, and in that there are "channels". The rule is that any given channel (that is, a specific segment of a specific vertical or horizontal line between the shapes) may only have one connector line running down it. They may, however, cross an arbitrary number of times. A connector will always join at least two shapes (or quite possibly more); each limb will ultimately reach a shape; in between it will always run down channels between the shapes, never crossing a shape; the various limbs of a connector connecting more than 2 shapes must be connected in some way at some point so that they can be seen not to be crossing.
My approach for trying to get the graph as "tight" as possible (that is, as many shapes close to their friends as possible, thus reducing the length of the connectors) is to place first the shape with the most number of connectors to it, then to try and place all the shapes connected to it (again, going from the most connections to the least), and then (recursively) working our way down the list. This may or may not work out well. It may also present additional challenges as and when we introduce constraints (such as a desire to have certain shapes all be on the same row).
Before we get started, I should (perhaps) clarify that I did not write this in the order in which I presented it, but did some layout and some rendering and slowly worked my way to this algorithm. Also, I worked up to it using unit tests for some simple cases and, if and when I come back to add more complex cases, the algorithm will change again.
Layout is kicked off from inside the
Diagram, but it basically just delegates to the
LayoutAlgorithm to first lay the diagram out and then to render it. Obviously to do that, it passes in the knowledge it has collected about the diagram.
layout(render) {
var alg = new LayoutAlgorithm(this.errors, this.nodes, this.nodeNames, this.edges);
alg.layout();
alg.render(render);
}
The layout algorithm comes in two parts: we first place the nodes on a hypothetical grid, and then we connect them with the edges.
layout() {
// handle the empty diagram
if (this.nodes.length == 0) return;
this.placeNodes();
this.connectNodes();
}
Placing the nodes is, of course, where all the meaty stuff happens. We want to lay the nodes out in such a way that nodes which are connected are close together and then connecting them via the edges should be relatively easy. We need to place the nodes one at a time; the first node is chosen to be the one with the most connections; after that, we can choose any node which is connected to a node already in the diagram. In practice, we try to choose the one with the
most connections to nodes already in the diagram.
To make this code simpler, we delegate the process of tracking which nodes are eligible for selection (and the appropriate order) to a class called
PushFrontier (so named because it is continually pushing forward the frontier of the graph which has been chosen) and the process of placing the nodes to a class called
Placement.
With these in place, the function to place the nodes is not
too awful:
placeNodes() {
// The frontier model is designed to provide us with the nodes in a "most connected" order
var frontier = new PushFrontier(this.nodes, this.edges);
// First place the most connected node
var name = frontier.first();
this.placement.place(0, 0, this.nameMap[name]);
// Now, iteratively consider all the remaining nodes
// Each node we receive will be connected to one or more (preferably more) nodes already in the diagram
while (frontier.push(name)) {
name = frontier.next();
// try and figure out where it's near ...
var avgpos = this.findNear(frontier, name);
// noew place it somewhere near there that isn't occupied
this.placement.place(avgpos.x, avgpos.y, this.nameMap[name]);
}
}
Selecting the next node
The
PushFrontier code works by first analyzing all the nodes and edges to build an inverted table of all the nodes with their connections. It then sorts these to find the nodes with the greatest number of connections and then identifies the list of connection arities. It turns out that this is a very good fit for a radix sort.
class PushFrontier {
constructor(nodes, edges) {
this.conns = this.groupByConnections(nodes, edges);
this.sorted = this.sortConnections(this.conns);
this.radices = this.gatherRadices(this.sorted);
this.done = [];
this.frontier = [];
}
The code to choose the first node simply looks for the first node in the list of nodes with the highest radix.
first() {
var r = this.radices[0];
var node = this.sorted[r][0];
return node;
}
Once the node has been added to the graph, the
push method is called, which adds it to the list of nodes that have been used (both so that it will not be returned again, and so that we can see which nodes are already in the graph). It then looks at all the nodes which are connected to this node (and which have not already been placed) and adds those to the expanding frontier.
push(node) {
this.done.push(node);
var add = this.conns[node];
for (var i=0;i<add.length;i++) {
if (!this.done.includes(add[i]))
this.frontier.push(add[i]);
}
return this.frontier.length > 0;
}
And finally, when we are asked to provide the next node, we scan through the list of frontier nodes (all of which have the property that they have not yet been placed, but are connected to a node which has been placed) and choose the one which:
- has the most connections to a node in the graph; or, failing that
- is tied for the most connections in the graph and, among those, has the most total connections; or, failing that
- is tied for the most number of connections, and has the alphabetically first name.
next() {
var mostInGraph = -1;
var mostTotal = -1;
var ret = null;
var pos = -1;
for (var i=0;i<this.frontier.length;i++) {
var node = this.frontier[i];
var total = this.conns[node].length;
var inGraph = this.chooseDone(this.conns[node]);
var chooseMe = false;
if (inGraph > mostInGraph) { // it is connected to the most already in the graph
chooseMe = true;
} else if (inGraph == mostInGraph && total > mostTotal) { // it is connected to the most other total nodes
chooseMe = true;
} else if (inGraph == mostInGraph && total == mostTotal && node < ret) { // it is at least as good and has an earlier name
chooseMe = true;
}
if (chooseMe) {
mostInGraph = inGraph;
mostTotal = total;
ret = node;
pos = i;
}
}
this.frontier.splice(pos, 1);
return ret;
}
Placing the Nodes on a Grid
The other half of the task is to figure out where to put each node once we have identified it as the next node to be placed on the grid. For the first node, this is easy: we just say we want to place it at
(0,0) and we're done. For all subsequent nodes, what we really want to do is to place them at the average position of all the nodes they are connected to.
// Look at all the nodes connected to this one which have already been placed and figure out their average position
// We want to be somewhere near there
findNear(frontier, name) {
var sx = 0, sy = 0, cnt = 0;
var conns = frontier.connectedTo(name);
for (var i=0;i<conns.length;i++) {
var c = conns[i];
var pl = this.placement.isPlaced(c);
if (pl) {
sx += pl.x;
sy += pl.y;
cnt++;
}
}
return { x: sx/cnt, y: sy/cnt };
}
Of course, there is a significant probability that that space is already taken, and we need to put it somewhere else "near" there. The
Placement class is responsible for handling that. For the cases I have added tests for so far, this code is adequate, but clearly there will be the need to do more later.
// find a slot for the node to go in, ideally the one it asked for
findSlot(x, y) {
// rounding is good from the perspective of trying something, but we possibly should try "all 4" (if not an integer) before trying neighbouring squares.
x = Math.round(x);
y = Math.round(y);
// if that slot is free, go for it!
if (!this.haveNodeAt(x, y)) return { x, y };
// first try the four cardinal points
if (!this.haveNodeAt(x+1, y)) return { x: x+1, y: y };
if (!this.haveNodeAt(x, y+1)) return { x: x, y: y+1 };
if (!this.haveNodeAt(x-1, y)) return { x: x-1, y: y };
if (!this.haveNodeAt(x, y-1)) return { x: x, y: y-1 };
this.errors.raise("can't handle this case in layout");
}
Connecting Nodes
Once we have placed all the nodes, we need to go back and look at all the edges and figure out how to connect them. My thought for a connector is that it is a series of line segments which are joined together in such a way as to make a continuous line between two nodes. In order to trace such a path, it must have a series of points, all of which are relative to the grid. The ultimate idea (not yet in code) is that between the main grid nodes are a set of "canals" divided into "channels" through which the edges can flow. This means that there are two distinct types of points: those where the point is attached to a side of a node; and those where the point is in a canal. For now, we only have the points connected to the side of a node (called a
ShapeEdge). This point is identified by the
(x,y) grid position of the node, which side of the node it is attached to, and which "channel" it is going to use (here, the same idea of a channel is to be able to distinguish between two different edges both coming into the same side of a node).
For now, I have only written the code to handle connections between two nodes which are on the same horizontal or vertical line (the only cases I have considered as yet). In this case, the connector has exactly two points, each of which is a
ShapeEdge. I have also not handled the case with multiple connectors from the same side of the same node.
connectNodes() {
for (var i=0;i<this.edges.length;i++) {
var e = this.edges[i];
if (e.ends.length != 2) {
this.errors.raise("cannot handle this case yet");
continue;
}
var f = e.ends[0];
var t = e.ends[1];
var fn = this.placement.isPlaced(f.name);
var tn = this.placement.isPlaced(t.name);
// This is nothing like sophisticated enough for 90% of cases. But it passes all current unit tests
this.placement.connect([ new ShapeEdge(fn.x, fn.y, tn.x-fn.x, tn.y - fn.y, 0), new ShapeEdge(tn.x, tn.y, fn.x - tn.x, fn.y - tn.y, 0) ]);
}
}
