During my PhD I always wanted to have an interactive way of plotting a nice looking Bethe Lattice and particular to my work a Dimer Bethe lattice. Because this visualization wasn’t an essential part of my research I never investigated into it. It is enough to draw them on paper for any practical purpose. I was then confronted with my PhD oral presentation, great opportunity to procrastinate and get the nice unessential plots done. They didn’t end in the final version of the presentation(again is not the fundamental part of my work), but I wanted to share them anyway.

I first found this project vis.js for browser based visualization, which has an entire section of examples dedicated to drawing networks. That is all I need. Doing things on the browser is great, it allows to publish many documents with user interactivity, which then can be openly shared as a webpage instead of a PDF document or other presentation files. With vis.js being able to plot networks the only task left is to find the good algorithm that solves the generation of the lattice problem.

Returning to JavaScript

The language of the web. Good that is a simple language, bad that is a simple language. I haven’t programmed in JavaScript in years(I was probably still in high school that time), other languages like PHP, C++, Python took over. But programming is one thing, the language syntax is another, so working again on JavaScript wasn’t to much of a problem.

The logic of vis.js to draw a network is that it takes a list of nodes and a list of edges, so I just need to generate them. A recursive algorithm was to me the most intuitive way to describe the Bethe Lattice , which is a connected cycle-free graph where each node is connected to a certain number of neighbors. In the end it is just a tree. I just need a function that creates a node, links that node to a head and then calls the function again for the amount of remaining neighbors the node has.

The Bethe Lattice

This algorithm lets itself be expressed by the following code:

 1function gen_Bethe(generations, neighbors) {
 2    var nodes = [];
 3    var edges = [];
 4    var counter = -1;
 5
 6    // Recursive function to create a new node and call itself to generate
 7    // the branches(subtree) structure of the graph
 8    function tree(level, neighbors, head) {
 9        counter++;
10        nodes.push({
11            id: counter,
12            label: String(counter),
13            group:level
14            });
15        var current_node = counter;
16        if (head != current_node) {
17            edges.push({
18                from: head,
19                to: current_node
20            });
21        }
22
23        if (level == 0) {
24            return 0;
25        }
26
27        var childs = neighbors - 1;
28        // Only the first/central node is special. For the recursive call
29        // it has all neighbors
30        if (current_node == 0) {
31            childs = neighbors;
32        }
33
34        var low = level - 1;
35        for (var i = 0; i < childs; i++) {
36            tree(low, neighbors, current_node);
37        }
38
39        return 0;
40    }
41
42    tree(generations, neighbors, 0);
43
44    return {
45        nodes: nodes,
46        edges: edges
47    };
48}

There are maybe better ways to solve this in JavaScript, I don’t know. The reduced amount of code makes me happy about it. The little amount of code does not reflect the amount of time I spent trying to make this work. I save it in a file /js/bethe_lattice_generator.js to be able to use it later.

In the head of the webpage I’ll import the vis.js JavaScript and CSS modules. Then I import the file with the previous algorithm to the bethe lattice and define a CSS #id to contain the plot.

 1<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/vis/4.21.0/vis.min.js"></script>
 2<link href="https://cdnjs.cloudflare.com/ajax/libs/vis/4.21.0/vis.min.css" rel="stylesheet" type="text/css">
 3
 4<script type="text/javascript" src="/js/bethe_lattice_generator.js"></script>
 5
 6<style type="text/css">
 7 #bethe-lattice {
 8    height: 450px;
 9    border: 1px solid lightgray;
10    align: center;
11  }
12</style>

The next JavaScript section goes also in the webpage, it declares how vis.js is to be used to draw the lattice. I need to setup variables of nodes, edges, network (that is the lattice), and configuration options.

 1<script type="text/javascript">
 2  var nodes = null;
 3  var edges = null;
 4  var network = null;
 5  var setSmooth = true;
 6
 7  // cleans the canvas where the lattice is plotted
 8  function destroy(net) {
 9    if (net !== null) {
10      net.destroy();
11      net = null;
12    }
13  }
14
15  function draw_bethe(level, neighbors) {
16    destroy(network);
17    // create a network
18    level = (typeof level == 'number') ?  level : 2;
19    neighbors = (typeof neighbors == 'number') ?  neighbors : 3;
20    var container = document.getElementById('bethe-lattice');
21    var data = gen_Bethe(level, neighbors);
22    var options = {
23      physics: { stabilization: false }
24    };
25    network = new vis.Network(container, data, options);
26  }
27</script>

Finally, in the content of the website I embed the HTML where to draw the Bethe Lattice and propose some options of configurations.

1<div id="bethe-lattice"></div>
2<form onsubmit="draw_bethe(3,3); return false;">
3  <input type="button" value="chain" onclick="draw_bethe(8, 2);">
4  <input type="button" value="2,3" onclick="draw_bethe(2, 3);">
5  <input type="button" value="3,3" onclick="draw_bethe(3, 3);">
6  <input type="button" value="3,4" onclick="draw_bethe(3, 4);">
7  <input type="button" value="4,4" onclick="draw_bethe(4, 4);">
8</form>

The dimer Bethe lattice

The can be understood as the Bethe lattice but placing two closely connected nodes at each place where the original Bethe lattice only has one node. An alternative view of it is to think of two independent Bethe lattices that are placed side by side and coupled at each node.

When extending the previous algorithm to plot the dimer lattice I’ll join both views. I start generating the Bethe lattice, but for each node I generate I immediately create its neighbor and link them to compose the dimer. In that way I build the second lattice at the same time.

 1function gen_dimerBethe(generations, neighbors) {
 2    var nodes = [];
 3    var edges = [];
 4    var counter = -1;
 5
 6    function tree(level, neighbors, head) {
 7        counter++;
 8        var current_node = counter;
 9        // first node
10        nodes.push({
11            id: counter,
12            label: String(counter),
13            group:20
14        });
15        // second node
16        counter++;
17        nodes.push({
18            id: counter,
19            label: String(counter),
20            group:100
21        });
22        // link the two nodes to build the dimer
23        edges.push({
24            from: counter-1,
25            to: counter,
26            dashes: true
27        });
28
29        if (head != current_node) {
30            edges.push({from: head, to: current_node, arrows:'to'});
31            // The second lattice
32            edges.push({from: head+1, to: current_node+1, arrows:'to'});
33        }
34
35
36        if (level == 0) {
37            return 0;
38        }
39
40        var childs = neighbors - 1;
41        if (current_node == 0) {
42            childs = neighbors;
43        }
44
45        var low = level - 1;
46        for (var i = 0; i < childs; i++) {
47            tree(low, neighbors, current_node);
48        }
49
50        return 0;
51    }
52
53    tree(generations, neighbors, 0);
54
55    return {
56        nodes: nodes,
57        edges: edges
58    };
59}

Setting up vis.js is the same as in the previous section,

 1<style type="text/css">
 2 #dimer-bethe-lattice {
 3    height: 450px;
 4    border: 1px solid lightgray;
 5    align: center;
 6}
 7</style>
 8
 9<script type="text/javascript">
10  var nodes = null;
11  var edges = null;
12  var setSmooth = true;
13  var network_dimer = null;
14  function draw_dimer_bethe(level, neighbors) {
15    destroy(network_dimer);
16    // create a network
17    level = (typeof level == 'number') ?  level : 2;
18    neighbors = (typeof neighbors == 'number') ?  neighbors : 3;
19    var container = document.getElementById('dimer-bethe-lattice');
20    var data = gen_dimerBethe(level, neighbors);
21    var options = {
22      physics: { stabilization: false }
23    };
24    network_dimer = new vis.Network(container, data, options);
25  }
26
27  // This draws the default lattices on window load
28  window.onload=function(){draw_bethe();draw_dimer_bethe();};
29</script>

Drawing the dimer Bethe lattice.

1<div id="dimer-bethe-lattice"></div>
2<form onsubmit="draw_dimer_bethe(3,3); return false;">
3  <input type="button" value="ladder" onclick="draw_dimer_bethe(8, 2);">
4  <input type="button" value="2,3" onclick="draw_dimer_bethe(2, 3);">
5  <input type="button" value="3,3" onclick="draw_dimer_bethe(3, 3);">
6  <input type="button" value="3,4" onclick="draw_dimer_bethe(3, 4);">
7</form>