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.
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.
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 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>
As a scientist I studied the physics of the very small quantum world. As a computer hacker I distill code. Software is eating the world, and less code means less errors, less problems. Millions of lines of legacy code demand attention and have to be understood and simplified for future reliable operation.