## JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

I wanted to add an indicator at the vertices, where the "next_incident_edge" can be found.
I wanted to use "/parrow" PostScript define, a line and an arc.
It turned out to be harder than thought to get things right, but now it works as it should.
Currently it is a hack, with all the calculations in modified "embedding_demo.2.js".
Later there will be a "/parrow" like definition in "ps.js" that will be easy to use.

Here again is single-face non-embedding from previous posting, with the new (blue) face traversal indicators
K4-e.single_face.enhanced.png
K4-e.single_face.enhanced.png (27.47 KiB) Viewed 2264 times

P.S:
As already said, not nice right now:

Code: Select all

...
ps.straight_line_drawing(G, coords, [], size, r, [], false);

function draw_vertex_edge_label(G, v, e, coords, l) {
var w = opposite(G, v, e);
var cx = (ps.scrx(coords[0][v]) + ps.scrx(coords[0][w])) / 2;
var cy = (ps.scry(coords[1][v]) + ps.scry(coords[1][w])) / 2;
var deg = Math.atan2(coords[1][v] - coords[1][w], coords[0][w] - coords[0][v]) * 180 / Math.PI;
v = w;
e = next_incident_edge(G, v, e);
w = opposite(G, v, e);
var deg2 = Math.atan2(coords[1][v] - coords[1][w], coords[0][w] - coords[0][v]) * 180 / Math.PI;
console.log("0 0 0 setrgbcolor");
console.log("12 " + ps.frm(deg) + " (" + l + ") " + ps.frm(cx) + " " + ps.frm(cy) + " txtdistdeg");
console.log("0 0 1 setrgbcolor");
deg2 += da;
deg -= da;
console.log("gsave " + ps.frm(ps.scrx(coords[0][v]) + r*Math.cos((deg - 180)/180*Math.PI)) + " " + ps.frm(ps.scry(coords[1][v]) + r * Math.sin((deg - 180)/180*Math.PI)) + " translate 0 0 moveto " + (deg - 180 + da) + " rotate " + r + " 0 lineto stroke grestore");
console.log("newpath " + ps.frm(ps.scrx(coords[0][v])) + " " + ps.frm(ps.scry(coords[1][v])) + " " + r + " " + ps.frm(deg2) + " " +ps.frm(deg -180) + " arc stroke");
console.log(ps.frm(2*r) + " 0 0 0 1 " + ps.frm(deg2 - da) + " " + ps.frm(ps.scrx(coords[0][v]) + r*Math.cos(deg2/180*Math.PI)) + " " + ps.frm(ps.scry(coords[1][v]) + r * Math.sin(deg2/180*Math.PI)) + " parrow");
}

r = 18;
last_face = -1;
cnt = -1;
pftv = planar_face_traversal_visitor();
pftv.begin_face = function () {
last_face += 1;
cnt = 0;
};
pftv.next_vertex_edge = function (v, e) {
draw_vertex_edge_label(G, v, e, coords, last_face + "_" + String.fromCharCode(97 + cnt));
cnt += 1;
};
planar_face_traversal(G, pftv);

console.log("0 0 0 setrgbcolor");

console.log("0 0 (is_embedding=" + is_embedding(G) + ",");
...
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

It took some time, but now I was able to compute the angle each arc is drawn in previous screenshot.
Why was it so difficult?
Because it is not a single formula, but difference building of "180-deg" (because angle deg is from wrong side of edge) and "deg2", and two while loops for getting angle into 0°..359.99° range. Without the while loops at least one of the angles was always outside of the range:

Code: Select all

...
var t = deg - 180 - deg2;
while (t < 0) {
t = t + 360;
}
while (t >=360) {
t = t - 360;
}
console.log("0 0 0 setrgbcolor");
console.log("12 " + ps.frm(deg) + " (" + l + ": " + ps.frm(t) + ") " + ps.frm(cx) + " " + ps.frm(cy) + " txtdistdeg");
...

As you can see I just appended formatted "t" value to edge label, so that I can see debug output "in place" during dev:
K4-e.single_face.enhanced.debug.png
K4-e.single_face.enhanced.debug.png (39.29 KiB) Viewed 1781 times

So now that I have the angle, the reason why I need it is, that I need to check for too small angle. For too pointed angle start and end of the arc are on wrong sides, and drawing arc needs to be skipped. In addition the line and parrow need to be moved so that they meet at a point, and do not cross each other. That point is dependent of the angle (15° in example) the line and parrow are distant from the real edges.

Computing the minimal angle and doing that computation of line and parrow join point is next. After that will work, the logic needs to be moved into a PostScript define in order not to pollute JavaScript code.

P.S:
These are the two bad cases for pointed angle I talked about (I moved up rightmost vertex a bit; right with "if (t >= 2*da)" guarding arc output):
bad_cases.pointed_angles.png (3.92 KiB) Viewed 1757 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Short interrupt, I have 3Dprinted connectors for paper drinking straws, toothpicks and match sticks and built C60 fullerenes with them.
Here is 92cm high paper drinking straw C60 fullerene, hanging 3m high at ceiling:
C60_92cm.20%.jpg
C60_92cm.20%.jpg (24.67 KiB) Viewed 1579 times
Lately I am printing polygons with small magnets in middle of edges for creating C60 as well:

After 32h(!) of 3Dprint I have 12 complete pentagons, 12 compete hexagons and 8 hexagon tops.
When current 5h print will have finished I will be able to complete C60.
This is the C60 part that I am able to build as of now:

I played with the polygons, and was able to complete a design with 8 hexagons and 12 pentagons I had not seen before:
C36.1.png.50%.jpg
C36.1.png.50%.jpg (24.84 KiB) Viewed 1583 times
One hexagon at bottom, surrounded by 6 pentagons, with 6 hexagon ring on top, then symmetric top like the bottom.

8 hexagons and 12 pentagons fullerene has (8*6+12*5)/3=36 vertices, so it looks like a C36 fullerene.
To be sure it is, I used fulgen.c …
http://users.cecs.anu.edu.au/~bdm/plantri/
… to compute the 15 non-isomorphic C36 fullerenes

Code: Select all

./fullgen 36 code 6 stdout > c36.txt
and just commited and pushed them (after quite some conversions):
https://github.com/Hermann-SW/planar_gr ... 3e1761a404

Then I realized that the only selectable graph embedding demo I have that does not add arrows is 6coloring demo.
I viewed all C36 graphs, starting with C36.15.a and then decrementing.
I searched for embedding with a ring of 6 hexagons and two hexagons completely surrounded by pentagons.
And I found it, it was the 15th fullerene inspected, C36.1.a ...

The 6 hexagon ring is faces 1+2+4+6+8+10. The two isolated hexagons are faces 18 and 19:
C36.1.col.png
C36.1.col.png (27 KiB) Viewed 1583 times

Having found what I constructed among the enumerated 15 non-isomorphic C36 fullerenes confirmed that my construction was good and no cheat.

P.S:
I removed the ring of 6 hexagons, and C24 fullerene resulted:

There is a unique non-isomorphic C24 only:

Code: Select all

pi@pi400-64:~/plantri52 $./fullgen 24 code 6 stdout > c24.txt Time for generating the patches: 0.0 seconds Time for case 1 (Jordan-Curve Petrie Path): 0.0 seconds Time for case 2 (Dumb-bell): 0.0 seconds Time for case 3 (Sandwich): 0.0 seconds MAPLIST: number of patches: 16 BBLIST: number of items in list: 3 number of patches: 5 Generated 2 maps on 24 vertices -- reduced to 1 non-isomorphic maps. Total generation time: 0.0 seconds end of program pi@pi400-64:~/plantri52$


P.P:S:
Converted and 6colored C24, with hexagon faces 12 and 13:
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Back to the planar face traversal angle indicators.
I am done with it in JavaScript, what remains is to move the (horrible right now) JavaScript code into a clean and neat PostScript define.

I was able to determine the radius factor for the point where the line and parrow meat at angle t/2, and that factor is "interesting":
angle_point.tex.dvi.pdf.png
angle_point.tex.dvi.pdf.png (10.01 KiB) Viewed 1405 times
I used Latex a lot in 1st half of the 90s, and every few years in between then and now, last 8 months ago:
https://gist.github.com/Hermann-SW/d20a ... 1d05d07833

That was on 32bit Raspberry Pi OS of my Pi400, today I had to install Latex on my 64bit OS with:

Code: Select all

sudo apt install texlive-latex-recommended
This command does display the formula:

Code: Select all

latex angle_point.tex && dvipdf angle_point.dvi && evince angle_point.pdf
The formula is just:

Code: Select all

R =& r \sin(da) \sqrt{\frac{1}{\tan(t)^2}\left(1 + \sqrt{\tan(t)^2 + 1}\right)^2 + 1}

And here you can see that the angle indicators in case "t < 2*da" work nicely — I intentionally created three differently pointed angles.
The biggest factor is 3.44 for edge 0_a into vertex 1, and out via edge 0_b:
K4-e.single_face.enhanced2.debug.png
K4-e.single_face.enhanced2.debug.png (33.98 KiB) Viewed 1405 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Instead of PostScript define, I moved the code to function "ps.vertex_indicator()".
So new "embedding_demo.4.js" using that looks not bloated anymore:
https://github.com/Hermann-SW/planar_gr ... js#L28-L35

Code: Select all

    function draw_vertex_edge_label(G, v, e, coords, l) {
var w = opposite(G, v, e);
var deg = r2d(Math.atan2(coords[1][v] - coords[1][w], coords[0][w] - coords[0][v]));
var cx = (ps.scrx(coords[0][v]) + ps.scrx(coords[0][w])) / 2;
var cy = (ps.scry(coords[1][v]) + ps.scry(coords[1][w])) / 2;
console.log("12 " + ps.frm(deg) + " (" + l + ") " + ps.frm(cx) + " " + ps.frm(cy) + " txtdistdeg");
ps.vertex_indicator(G, v, e, coords, r, da);
}

Output is similar to that of previous posting, with debug output on edges removed.
All is ported to Python as well, more details in this Python thread posting:
viewtopic.php?p=2010618#p2010618

HermannSW wrote:
Thu Jun 09, 2022 11:15 pm
Then I realized that the only selectable graph embedding demo I have that does not add arrows is 6coloring demo.
Today I enhanced that 6coloring demo in order to allow for (12) pentagon only coloring.

Code: Select all

node.convex_face_straight_line_drawing.pentagons.js -> node.convex_face_straight_line_drawing.6coloring.js
and

Code: Select all

python/python.convex_face_straight_line_drawing.pentagons.py -> python.convex_face_straight_line_drawing.6coloring.py
in order to be able to select pentagon code, without touching existing argument processing.

All is committed and pused, so you can play with it:
https://github.com/Hermann-SW/planar_graph_playground

I had to export the file to execute as "ARGV0" environment variable in rjs and rpy scripts:

Code: Select all

pi@pi400-64:~/planar_graph_playground $cat rjs #!/bin/bash file=$1
shift
export ARGV0=$file gcc -E -x c -nostdinc$file | grep -v "^#"  | nodejs - $* pi@pi400-64:~/planar_graph_playground$ 

node.convex_face_straight_line_drawing.6coloring.js does use that information like this:

Code: Select all

var do_pent = process.env.ARGV0.includes("pent");

graphs/C36.1.a viewed with pentagon coloring by this command:

Code: Select all

rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C36.1.a | gv -
looks like this:
C36.1.pentagons.jpg
C36.1.pentagons.jpg (54.41 KiB) Viewed 1265 times
Here the 6-cycle of hexagons 1+2+4+6+8+10 is much easier to spot, as well as isolated hexagons 18 and 19.

I looked at the other C36.x fullerenes and graphs/C36.4.a looked interesting:
C36.4.pentagons.jpg
C36.4.pentagons.jpg (57.84 KiB) Viewed 1265 times
In this fullerene there is a 8-cycle of hexagons, faces 0+2+4+5+7+8+10+11 (0 is the outer face).
I disassembled C60 built from 3Dprinted polygons and built C36.4, and it worked.
I took photos from both sides, the 8.cycle of orange hexagons is easy to spot:
C36.4.both_sides.50%.jpg
C36.4.both_sides.50%.jpg (26.35 KiB) Viewed 1265 times
I was surprised that the fullerene was able to safely stand on a polyhedron edge.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

As provisional end of C36.x fullerene investigations I created all 15 pentagon colorings. Unlike before, where I did screenshot of "gv" displaying PostScript file, and then manually cutting the output, this time all is done automatically, with this script:

Code: Select all

#!/bin/bash
for((i=1; i<=15; ++i))
do
./rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C36.$i.a > /tmp/x.ps pstopnm /tmp/x.ps pnmcut -top 92 -bottom 696 /tmp/x001.ppm > /tmp/x.ppm pnmtopng /tmp/x.ppm > ful.$i.png
echo $f done  I then used pngs2anim script to create an animated .gif from then 15 created ful.*.png files, here with 0.5fps: viewtopic.php?p=1773897&hilit=pngs2anim#p1773897 graphs/C36.14.a did stand out, because it has 3 connected pentagon only components (the other have 1 or 2): ful.14.png ful.14.png (6.85 KiB) Viewed 1168 times I assembled C36.14 with the polygons, again it stands safe on a polyhedron edge: 20220613_202816.part.33%.jpg (25.18 KiB) Viewed 1168 times P.S: Below small diffs do color pentagons white and hexagons orange, to match colors of 3Dprinted polygons: orange.png orange.png (6.77 KiB) Viewed 1128 times node.convex_face_straight_line_drawing.6coloring.js: Code: Select all  if (do_pent) { + console.log("1.0 0.66 0.0 setrgbcolor"); + console.log(' 0 0'); + console.log(' ' + size + ' 0'); + console.log(' ' + size + ' ' + size); + console.log(' 0 ' + size); + console.log('poly fill'); + pent = pentagons(G); ps.py: Code: Select all  pent.forEach(function (face) { - console.log(".75 setgray"); + console.log("1 setgray"); face.forEach(function (v) { console.log(' ' + frm(scrx(coords[0][v])) + ' ' + frm(scry(coords[1][v]))); }); @@ -92,7 +92,7 @@ if (true) { }); if (pent.length !== 12) { - exports.fill_outer_face(outer, coords, "0.75 0.75 0.75"); + exports.fill_outer_face(outer, coords, "1 1 1"); }  https://hermann-sw.github.io/planar_graph_playground https://stamm-wilbrandt.de/en#raspcatbt https://github.com/Hermann-SW/memrun https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter https://stamm-wilbrandt.de/en/Raspberry_camera.html HermannSW Posts: 5254 Joined: Fri Jul 22, 2016 9:09 pm Location: Eberbach, Germany ### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface HermannSW wrote: Sun May 22, 2022 4:56 pm Without OpenSCAD debug output and being able to turn/scale 3D view, I would not have reached this state … Currently pentagon is not regular as it should when folding correctly: I really need to get this fold check code working. graphs/C40.a embedding looks normal: C40.png C40.png (6.37 KiB) Viewed 1092 times But building that C40, with two joining 5-rings of hexagons (1+2+4+6+8 and 11+10+14+13+12) with 3Dprinted polygons shows, that the magnets match, but the hexagon sides do not match. So this is an example of "not foldable with matching sides" fullerene: C40.plygons.png.25%.jpg C40.plygons.png.25%.jpg (16.91 KiB) Viewed 1092 times There is a simple reason why this cannot be foldable: 3 hexagons joining with each angle of 120° sum up top 360° full circle. That means all three hexagons have to stay in the same plane in 3D space. https://hermann-sw.github.io/planar_graph_playground https://stamm-wilbrandt.de/en#raspcatbt https://github.com/Hermann-SW/memrun https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter https://stamm-wilbrandt.de/en/Raspberry_camera.html HermannSW Posts: 5254 Joined: Fri Jul 22, 2016 9:09 pm Location: Eberbach, Germany ### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface Easier than doing complete folding if possible, it is to determine whether a planar fullerene embedding is not foldable. A fullerene consists of pentagons and hexagons only, and it is a cubic graph (all vertices have degree 3). With three faces joining, there is always a pair of faces sharing an edge with same number of vertices. The dual edge of that edge has same vertex degree for both of its vertices. Next, however the two faces are folded, there is either a pentagon of hexagon possible on both sides because of symmetry. So "not_foldable.js" just checks this necessary condition for all edges of dual graph: Code: Select all #include "assert.js" #include "util.js" #include "fullerenes.js" #include "undirected_graph.js" function prev_incident_edge(G, v, e) { var j = ind(G, v, e); return G.V[v][(G.E[e][j][1] + degree(G, v) - 1) % degree(G, v)]; } var D; var sel = ( (process.argv.length > 2) ? process.argv[2] : "graphs/C40.a" ); var L = parse2file(sel); var G = from_adjacency_list(L); assert.assert(is_embedding(G)); D = dual_graph(G); assert.assert(is_embedding(D)); assert.assert(is_embedding(dual_graph(D))); forall_edges(D, function(e) { var v = source(D, e); var w = target(D, e); if (degree(D, v) === degree(D, w)) { var f = next_incident_edge(D, v, e); var g = prev_incident_edge(D, v, e); if (degree(D, opposite(D, v, f)) !== degree(D, opposite(D, v, g))) { console.log(sel, "not foldable"); process.exit(0); } } }); console.log(sel, "might be foldable");  Running it for all fullerenes stored sofar in graphs directory identified many fullerenes as "not foldable with regular pentagons and hexagons": Code: Select all pi@pi400-64:~/planar_graph_playground$ for f in graphs/C*.a
> do
> ./rjs not_foldable.js $f > done graphs/C20.a might be foldable graphs/C24.a not foldable graphs/C30.a not foldable graphs/C36.10.a not foldable graphs/C36.11.a might be foldable graphs/C36.12.a not foldable graphs/C36.13.a not foldable graphs/C36.14.a not foldable graphs/C36.15.a not foldable graphs/C36.1.a might be foldable graphs/C36.2.a not foldable graphs/C36.3.a not foldable graphs/C36.4.a not foldable graphs/C36.5.a not foldable graphs/C36.6.a not foldable graphs/C36.7.a not foldable graphs/C36.8.a not foldable graphs/C36.9.a not foldable graphs/C40.a not foldable graphs/C50.a not foldable graphs/C60.a might be foldable graphs/C70.a not foldable pi@pi400-64:~/planar_graph_playground$


So only C20, C36.11, C36.1 and C60 are "foldable with regular pentagons and hexagons" candidates.

We now that C20 is foldabe (it is the dodecahedron consisting of 12 pentagons).
And we know that C60 is foldable ("football" fullerene with 20 hexagons and 12 pentagons).

C36.1 looks as if it is foldable (6-cycle of white/orange hexagons with two isolated hexagons):
C36.1.pentagons.photo.jpg
C36.1.pentagons.photo.jpg (64.77 KiB) Viewed 1022 times

I just built C36.11, and it looks foldable, but that has to be verified (it has 12-cycle of grey/white pentagons):
C36.11.pentagons.photo.png.50%.jpg
C36.11.pentagons.photo.png.50%.jpg (25.84 KiB) Viewed 1022 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

New "might.js" does iterate over all graphs stored in "fullgen" output enumerating all non-isomorphic fullerenes with a given number of vertices. And it outputs all "might be foldable" candidates:

Code: Select all

#include "assert.js"
#include "util.js"
#include "undirected_graph.js"

function forall_graphs(name, f) {

var l = 1;
var i = 0;
while (l < F.length-1) {
var L = [];
while (F[l] !== "0") {
var v = F[l].trim().replace(/ +/g, " ").split(" ")
L.push([Number(v[4])-1, Number(v[5])-1, Number(v[6])-1]);
l = l + 1;
}
i = i + 1;
f(G, i);
l = l + 1;
}
}

var D;
assert.assert(process.argv.length > 2);
var sel = process.argv[2];

forall_graphs(sel, function (G, i) {

assert.assert(is_embedding(G));
D = dual_graph(G);
assert.assert(is_embedding(D));
assert.assert(is_embedding(dual_graph(D)));

var good = true;
forall_edges(D, function(e) {
var v = source(D, e);
var w = target(D, e);
if (degree(D, v) === degree(D, w))
{
var f = next_incident_edge(D, v, e);
var g = prev_incident_edge(D, v, e);
if (degree(D, opposite(D, v, f)) !== degree(D, opposite(D, v, g))) {
good = false;
}
}
});

if (good) {
console.log(sel, i, "might be foldable");
}
});

Bash loop around gives an overview of all candidates, takes more and more time the more vertices:
Peek_2022-06-16_14-47.gif
Peek_2022-06-16_14-47.gif (38.52 KiB) Viewed 977 times
Last edited by HermannSW on Fri Jun 17, 2022 5:52 am, edited 1 time in total.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Determining the "might be foldable" candidates up to 60 vertices took only 18 seconds.
I did run search up to 100 vertices, and found no further candidate — that search took more than 78 minutes on 64bit OS Pi400:

Code: Select all

pi@pi400-64:~/planar_graph_playground $time ( for((i=60; i<=100; i+=2)); do echo -en "c$i.txt\r"; ./rjs might.js ~/plantri52/fullgen $i code 6 stdout 2>/dev/null > c$i.txt; echo c$i.txt; done ) c60.txt 936 might be foldable c100.txt real 78m30.533s user 81m58.393s sys 1m55.847s pi@pi400-64:~/planar_graph_playground$


I mentioned that in case three regular hexagons are joining at a vertex, they need to stay in same plane in 3D because their (120°) angles sum up to 360°.
I wrote search code "full.js" that finds fullerenes with three joining hexagons:

Code: Select all

...
var good = false;
forall_vertices(D, function(v) {
if (degree(D, v) === 6) {
forall_incident_edges(D, v, function(e) {
if (6 === degree(D, opposite(D, v, e))) {
{
var f = next_incident_edge(D, v, e);
if (6 === degree(D, opposite(D, v, f))) {
good = true;
...
Here is full code:

Code: Select all

#include "assert.js"
#include "util.js"
#include "undirected_graph.js"

function forall_graphs(name, f) {

var l = 1;
var i = 0;
while (l < F.length-1) {
var L = [];
while (F[l] !== "0") {
var v = F[l].trim().replace(/ +/g, " ").split(" ")
L.push([Number(v[4])-1, Number(v[5])-1, Number(v[6])-1]);
l = l + 1;
}
i = i + 1;
f(G, i);
l = l + 1;
}
}

var D;
assert.assert(process.argv.length > 2);
var sel = process.argv[2];

forall_graphs(sel, function (G, i) {

assert.assert(is_embedding(G));
D = dual_graph(G);
assert.assert(is_embedding(D));
assert.assert(is_embedding(dual_graph(D)));

var good = false;
forall_vertices(D, function(v) {
if (degree(D, v) === 6) {
forall_incident_edges(D, v, function(e) {
var w = opposite(D, v, e);
if (6 === degree(D, w))
{
var f = next_incident_edge(D, v, e);
if (6 === degree(D, opposite(D, v, f))) {
good = true;
}
}
});
}
});

if (good) {
console.log(sel, i, "three joining hexagons found");
}
});


It did find a lot of such fullerenes up to 60 vertices:

Code: Select all

pi@pi400-64:~/planar_graph_playground $time ( for((i=4; i<=60; i+=2)); do echo -en "c$i.txt\r"; rjs full.js ~/plantri52/fullgen $i code 6 stdout 2>/dev/null > c$i.txt; echo c$i.txt; done > out ) real 0m21.175s user 0m22.259s sys 0m2.378s pi@pi400-64:~/planar_graph_playground$ wc --lines out
5731 out
pi@pi400-64:~/planar_graph_playground $ Next I tested whether any of the "might be foldable" graphs is among those found, expecting none, and confirming none: Code: Select all pi@pi400-64:~/planar_graph_playground$ grep c20 out | grep " 1 "
pi@pi400-64:~/planar_graph_playground $grep c36 out | grep " 1 " pi@pi400-64:~/planar_graph_playground$ grep c36 out | grep " 11 "
pi@pi400-64:~/planar_graph_playground $grep c38 out | grep " 7 " pi@pi400-64:~/planar_graph_playground$ grep c40 out | grep " 18 "
pi@pi400-64:~/planar_graph_playground $grep c40 out | grep " 19 " pi@pi400-64:~/planar_graph_playground$ grep c42 out | grep " 39 "
pi@pi400-64:~/planar_graph_playground $grep c44 out | grep " 51 " pi@pi400-64:~/planar_graph_playground$ grep c44 out | grep " 53 "
pi@pi400-64:~/planar_graph_playground $grep c50 out | grep "105 " pi@pi400-64:~/planar_graph_playground$ grep c60 out | grep " 936 "
pi@pi400-64:~/planar_graph_playground $ So I extracted smallest fullerene with 3 hexagons joining, C32.2.a: Code: Select all pi@pi400-64:~/planar_graph_playground$ head -1 out
c32.txt 2 three joining hexagons found
pi@pi400-64:~/planar_graph_playground $ Just as visual confirmation I did pentagons coloring view of that graph, and it has two such joining 3-hexagon groups. But it is not "foldable" with regular pentagons/hexagons. A reason is that joining hexagons 9 and 10 have hexagon 8 and pentagon 11 on both sides of joining edge: C32.2.a.png C32.2.a.png (6.83 KiB) Viewed 917 times https://hermann-sw.github.io/planar_graph_playground https://stamm-wilbrandt.de/en#raspcatbt https://github.com/Hermann-SW/memrun https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter https://stamm-wilbrandt.de/en/Raspberry_camera.html HermannSW Posts: 5254 Joined: Fri Jul 22, 2016 9:09 pm Location: Eberbach, Germany ### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface Still no fold code, but 1st time straight line drawing in 3D. I used "tutte.convex_face_coordinates()" as before to get 2D coordinates for planar convex face straight line drawing: The outer face has coordinates on unit circle around 2D origin, so length=1, and all inner vertices have length <1. I used this code to map the 2D coordinates onto unit sphere in 3D, and scale coordinates before OpenSCAD drawing: https://github.com/Hermann-SW/planar_gr ... js#L70-L79 Code: Select all forall_vertices(G, function (v) { coords[v] = map_3D(coords2D[0][v], coords2D[1][v]); }); forall_vertices(G, function (v) { coords[v] = scale_3D(coords[v], Math.sqrt(n_vertices(G))); }); straight_line_drawing_3D(G); The trick is in function "map_3D()": https://github.com/Hermann-SW/planar_gr ... js#L30-L34 Code: Select all function map_3D(x, y) { var a = Math.atan2(y, x); var l = 0.8 * Math.PI * Math.sqrt(length_2D(x, y)); return [Math.sin(a) * Math.sin(l), Math.cos(a) * Math.sin(l), Math.cos(l)]; } The factor of 0.8 and using "Math.sqrt()" have no mathematical reason besides that fullerenes look nice with them: Code: Select all pi@pi400-64:~/planar_graph_playground$ rjs node.straight_line_drawing.3D.js graphs/C32.2.a > x.scad && openscad x.scad

I know of no equivalent to Tutte's algorithm for determining 2D coordinates for creating unit sphere 3D coordinates.
But with "map_3D()" I have unit sphere coordinates covering big part of unit sphere.
So an iterative spring simulation iterative method should end in similar state of equilibrium as with Tutte's formula in 2D.

Here you can see executing the command just shown and zooming and 3D rotation OpenSCAD allows for:

This view shows the 3 joining hexagons of graphs/C32.2.a in front, one in center, the other two hexagons left and right below:
C32.2.3D.png
C32.2.3D.png (69.33 KiB) Viewed 804 times

P.S:
The vertices and edges in background are sometimes a bit confusing.
So I added option "white", which adds a white sphere inside the fullerene.
https://github.com/Hermann-SW/planar_gr ... js#L54-L56

Code: Select all

    if (white) {
console.log("color([1,1,1]) translate([0,0,0]) sphere(", Math.sqrt(n_vertices(G)) - 1, ");");
}
Viewing with the white sphere inside is much easier, at least for my eyes:
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

I learned how to use OpenSCAD builtin animation and posted about that, with white sphere in fullerene as example:
viewtopic.php?t=336334

Then I realized how to use OpenSCAD as 3D viewer for different scenes, and "see" debug output for the new iterative unit sphere spring embedder I want to program. Details in this posting, here just the selected red vertex auto rotated in front of origin animation (iterating over all 20 vertices of C20 fullerene (dodecahedron)):
viewtopic.php?t=336334#p2013157
Peek_2022-06-20_21-00.gif
Peek_2022-06-20_21-00.gif (249.25 KiB) Viewed 729 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

I had the 3D visualization tools and tried to get iterative spring embedder to work.
Problem was that "move vertex to normalized (for ending on unit sphere) center of its neighbors" did nearly no moves.
The factor 0.8 and using Math.sqrt() created something too good.

So I replaced factor 0.8 with 0.9, and removed Math.sqrt() to get a worse start situation, here two views:
C32.2.candidate_before_move.png
C32.2.candidate_before_move.png (60.53 KiB) Viewed 641 times

What I did to get bigger moves was "to move vertex into center of vertices of its three faces, without the vertex itself":
https://github.com/Hermann-SW/planar_gr ... wing.3D.js
These lines compute 3D sum of the 12..15 vertices "around" the three faces of vertex v, and the normalized value (on sphere):

Code: Select all

sum = filled_array(n_vertices(G), 1, [0,0,0]);
nor = filled_array(n_vertices(G), 1, [0,0,0]);

forall_vertices(G, function (v) {
var visited = filled_array(n_edges(G), 2, false);
var face = [];
forall_incident_edges(G, v, function(e) {
traverse_face(G, visited, v, e, ind(G, v, e), {next_vertex: function (w) {
if (v !== w) {
face.push(w);
}

Code: Select all

        }});
});
face.forEach(function (x) {
});
nor[v] = norm_3D(sum[v]);
});

This code determines the vertex with largest distance move (largest distance on unit sphere is 2 between north and south pole). The $vpr line rotates so that the not moved vertex V is in front of origin. Then V gets new coordinate: Code: Select all V = 0; forall_vertices(G, function (v) { if (dist_3D(nor[V], coords[V]) < dist_3D(nor[v], coords[v])) { V = v; } }); console.log("$vpr = [",-rad2deg(Math.acos(coords[V][2])),",0,",

coords[V] = nor[V];

Here you can see the maximal possible initial move (0.6462312041926355 distance):
C32.2.candidate_do_move.png
C32.2.candidate_do_move.png (41.02 KiB) Viewed 641 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Today I posted on "OpenSCAD animation" again, with pure NodeJS external animation, and small demo code "wlog.js":
viewtopic.php?p=2014370#p2014370

I had problems to get animation done with "node.straight_line_drawing.js".
So I did same single call to async function "amain()" as in demo code "wlog.js", and then it worked.
I just commited+pushed latest changes:
https://github.com/Hermann-SW/planar_gr ... 199000548d

Need to verify that calculations are correct at all.
I had replaced call of "traverse_face()" with call of more efficient constant time "face_vertices()" (for constant length faces like pentagons and hexagons as for fullerenes).
I did update the up to maximal 15 vertices of a moved vertex' neighbor faces wrt the move, making this a constant time operation as well.

What I saw and this animated .gif shows is, that the new move is "too heavy" — finally al vertices end up in south half of unit sphere which is not what I want:
Peek_2022-06-26_01-14.gif
Peek_2022-06-26_01-14.gif (183.8 KiB) Viewed 542 times

P.S:
I gave animation more time, and finally all vertices are close to south pole:
finally.1.png
finally.1.png (16.64 KiB) Viewed 522 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

I used factor 0.8 and Math.sqrt() again to get a better start vertex distribution.
This time vertices kept in north and south half sphere, but completely moved into east half sphere.

I thought again on Tutte's algorithm for determining vertex coordinates for planar convex face straight line drawing.
That worked because the vertex coordinates of outer face are fixed.

So I wanted to fixate as few vertices as possible on unit sphere for avoiding all vertices moving together.
Minimal number of vertices is 4, vertices of tetrahedron.

I created new "floyd_warshall(G)" all pairs shortest path algorithm:
https://en.wikipedia.org/wiki/Floyd%E2% ... #Algorithm
https://github.com/Hermann-SW/planar_gr ... #L449-L471

Code: Select all

function floyd_warshall(G) {
var dist = filled_array(n_vertices(G), n_vertices(G), Infinity);

forall_edges(G, function(e) {
dist[source(G, e)][target(G, e)] = 1;
dist[target(G, e)][source(G, e)] = 1;
});
forall_vertices(G, function(v) {
dist[v][v] = 0;
});


Code: Select all

    forall_vertices(G, function(k) {
forall_vertices(G, function(i) {
forall_vertices(G, function(j) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
});
});
});
return dist;
}
It is not the most efficient algorithm for sparse graphs like planar graphs for the task, but it is very simple, and can deal with negative cycles (not needed here).

So I wanted vertices of tetrahedron in a given input fullerene, with sum of six "tetrahedron edge" shortest paths being maximal.
And I wanted all vertices to be far, so I searched for such 4-tuples where shortest path lengths are either x or x-1:

Code: Select all

function ok(a,b,c,d,e,f) {
var m = Math.max(a, b, c, d, e, f);
return (((m - a) <= 1) && ((m - b) <= 1) && ((m - c) <= 1) &&
((m - d) <= 1) && ((m - e) <= 1) && ((m - f) <= 1));
}

https://github.com/Hermann-SW/planar_gr ... js#L25-L47

Code: Select all

var dist = floyd_warshall(G);
var max = 0;
var M = [0,0,0,0];

forall_vertices(G, function(a) {
forall_vertices_after(G, a, function(b) {
forall_vertices_after(G, b, function(c) {
forall_vertices_after(G, c, function(d) {
if (dist[a][b] + dist[a][c] + dist[a][d] +
dist[b][c] + dist[b][d] + dist[c][d] > max) {
if (ok(dist[a][b], dist[a][c], dist[a][d],

Code: Select all

                               dist[b][c], dist[b][d], dist[c][d])) {

max = dist[a][b] + dist[a][c] + dist[a][d] +
dist[b][c] + dist[b][d] + dist[c][d];
M = [a, b, c, d];
}
}
});
});
});
});

I had spotted sum as 18 for C20 before, here confirmd:

Code: Select all

pi@pi400-64:~/planar_graph_playground $./rjs node.tetra.js graphs/C20.a 12 pentagons for graph 0 non-pentagons for graph vertices: [ 0, 3, 12, 18 ] max: 18 dists: 3 3 3 3 3 3 pi@pi400-64:~/planar_graph_playground$


I ported to Python as well, here for C60:

Code: Select all

pi@pi400-64:~/planar_graph_playground/python $./rpy python.tetra.py ../graphs/C60.a 12 pentagons for graph 20 non-pentagons for graph vertices: [0, 5, 35, 48] max: 34 dists: 5 5 6 6 6 6 pi@pi400-64:~/planar_graph_playground/python$


I wanted to "see" the vertices in planar embedding, and enhanced (node|python).convex_face_straight_line_drawing.pentagons, allowing to just pass the vertex numbers to be marked. Here with "0 5 35 48" from last example, with shortest path lengths 5 and 6 for the six tetrahedron shortest paths:

Code: Select all

$./rpy python.convex_face_straight_line_drawing.pentagons.py ../graphs/C60.a 0 5 35 48 | gv - C60.tetra.png C60.tetra.png (37.79 KiB) Viewed 459 times Here for C20, with all 6 shortest paths between the 4 vertices of length 3 marked blue (with gimp): Code: Select all pi@pi400-64:~/planar_graph_playground$ ./rjs node.tetra.js graphs/C20.a
12 pentagons for graph
0 non-pentagons for graph
vertices: [ 0, 3, 12, 18 ]
max: 18
dists: 3 3 3 3 3 3
pi@pi400-64:~/planar_graph_playground $./rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C20.a 0 3 12 18 | gv -  C20.tetra.png C20.tetra.png (41.64 KiB) Viewed 459 times Instead of using 3-dimensional coordinates on unit sphere, my older son proposed to use polar coordinates instead (two angles). I can see how to solve system of linear equations for one of the 4 faces of the tetrahedron and fixate all shortest path and inner vertices. I can also see how to do the same for two faces together, and that would move the vertices of shortest path between both tetrahedron faces combined. Will try out something next. P.S: Using gimp "Paths" tool and "Stroke Path" gives nicer "tetrahedron edge" visualization: Code: Select all max: 34 dists: 5 5 6 6 6 6 C60.tetra.paths.png C60.tetra.paths.png (55.94 KiB) Viewed 400 times https://hermann-sw.github.io/planar_graph_playground https://stamm-wilbrandt.de/en#raspcatbt https://github.com/Hermann-SW/memrun https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter https://stamm-wilbrandt.de/en/Raspberry_camera.html HermannSW Posts: 5254 Joined: Fri Jul 22, 2016 9:09 pm Location: Eberbach, Germany ### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface If the path coloring would be needed for illustration purposes only, gimp would be good enough. But the paths need to be determined for splitting graph and solving systems of linear equations. There is a modification "floyd_warshall_path(G)" that allows to determine the shortest path between a pair of vertices: https://en.wikipedia.org/wiki/Floyd%E2% ... nstruction That algorithm stores vertices for the paths. For planar graphs I could compute a 5-compaction to determine the intermediate edges in constant time for each edge. But for non-planar graphs with more edges that is not true anymore. Therefore new function "fw_path()" returns array of edges. Intermediate vertices can be easily determined using "opposite()" from start vertex: https://github.com/Hermann-SW/planar_gr ... #L502-L513 Code: Select all function fw_path(next, u, v) { var path = []; if (next[u][v] == -1) { return path; } while (u !== v) { var e = next[u][v]; path.push(e); u = opposite(G, u, e); } return path; } New function "floyd_warshall_path()" returns dist as well as next array: https://github.com/Hermann-SW/planar_gr ... #L473-L500 Code: Select all ... return [dist, next]; } They can be easily split: Code: Select all var dist; var next; [dist, next] = floyd_warshall_path(G); "node.convex_face_straight_line_drawing.pentagons.js" is modified to mark passed vertices as well as edges. For this purpose vertices and edges are passed comma-separated: Code: Select all pi@pi400-64:~/planar_graph_playground$ ./rjs node.tetra.js graphs/C20.a
12 pentagons for graph
0 non-pentagons for graph
vertices: 0,3,12,18
max: 18
dists: 3 3 3 3 3 3
edges: 2,3,6,1,20,22,0,19,29,7,9,23,8,27,28,13,14,16
pi@pi400-64:~/planar_graph_playground $ ""edges:" output done by: https://github.com/Hermann-SW/planar_gr ... js#L55-L61 Code: Select all var edges = [].concat(fw_path(next, M[0], M[1]), fw_path(next, M[0], M[2]), fw_path(next, M[0], M[3]), fw_path(next, M[1], M[2]), fw_path(next, M[1], M[3]), fw_path(next, M[2], M[3])); console.log("edges:", String(edges)); Now passing both ... Code: Select all ./rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C20.a 0,3,12,18 2,3,6,1,20,22,0,19,29,7,9,23,8,27,28,13,14,16 | gv - ... shows the 6 tetrahedron shortest paths edges bold: C20.tetra.paths.png C20.tetra.paths.png (29.82 KiB) Viewed 374 times And for C60: Code: Select all pi@pi400-64:~/planar_graph_playground$ ./rjs node.tetra.js graphs/C60.a
12 pentagons for graph
20 non-pentagons for graph
vertices: 0,5,35,48
max: 34
dists: 5 5 6 6 6 6
edges: 2,3,6,7,10,1,36,38,40,59,0,34,31,32,78,76,11,13,49,50,61,60,12,68,70,87,88,77,43,42,25,23,24,75
pi@pi400-64:~/planar_graph_playground $./rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C60.a 0,5,35,48 2,3,6,7,10,1,36,38,40,59,0,34,31,32,78,76,11,13,49,50,61,60,12,68,70,87,88,77,43,42,25,23,24,75 | gv - C60.tetra.paths.png C60.tetra.paths.png (37.19 KiB) Viewed 374 times https://hermann-sw.github.io/planar_graph_playground https://stamm-wilbrandt.de/en#raspcatbt https://github.com/Hermann-SW/memrun https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter https://stamm-wilbrandt.de/en/Raspberry_camera.html HermannSW Posts: 5254 Joined: Fri Jul 22, 2016 9:09 pm Location: Eberbach, Germany ### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface Running node.tetra.js for graphs/C32.2.a shows that edges can be shared by different tetrahedron shortest paths, here edge between faces 10 and 11 for shortest path from vertex surrounded by face 0(the outer face), 2 and 3 and vertex surrounded by 12, 13, 15 to vertex surrounded by 9, 10, 11: C32.2.tetra.paths.png C32.2.tetra.paths.png (22.9 KiB) Viewed 307 times Next, there can be several different shortest paths between two vertices, here between top vertex and vertex surrounded by faces 13, 28, 29: C20.tetra.paths.0_48.png C20.tetra.paths.0_48.png (18.87 KiB) Viewed 307 times It was not clear to me, since floyd_warschal algorithm was an algorithm for directed graphs, whether always the shortest path from a to b has same edges as shortest path from b to a for undirected graph. I created this test script: Code: Select all pi@pi400-64:~/planar_graph_playground$ cat n.js

#include "assert.js"
#include "util.js"
#include "undirected_graph.js"

function forall_graphs(name, f) {

var l = 1;
var i = 0;
while (l < F.length-1) {
var L = [];
while (F[l] !== "0") {
var v = F[l].trim().replace(/ +/g, " ").split(" ")
L.push([Number(v[4])-1, Number(v[5])-1, Number(v[6])-1]);
l = l + 1;
}
i = i + 1;
f(G, i);
l = l + 1;
}
}

assert.assert(process.argv.length > 2);

forall_graphs(process.argv[2], function (G, i) {
console.log(i);

assert.assert(is_embedding(G));

var dist;
var next;
[dist, next] = floyd_warshall_path(G);

forall_vertices(G, function(a) {
forall_vertices_after(G, a, function(b) {
if (new Set(fw_path(G, next, a, b).concat(fw_path(G, next, b, a))).size !== dist[a][b]) {
console.log("edges2:", fw_path(G, next, a, b), fw_path(G, next, b, a));
process.exit(1);
}
});
});
});
pi@pi400-64:~/planar_graph_playground $ I applied the algorith to the 8149 non-isomorphic C70 fullerenes, and tested all choose(80, 2) = 70*69/2 = 2415 pairs of vertices (more than 19 million tests in total). This just iterates over all 8149 graphs, asserts each read adjacency lists being an embedding and determines shortest paths: Code: Select all forall_graphs(process.argv[2], function (G, i) { console.log(i); assert.assert(is_embedding(G)); var dist; var next; [dist, next] = floyd_warshall_path(G);  Here for all pairs of vertices a,b it is checked whether shortest pasth from a to b and b to a have same edges. If not, edges of shortest paths get reported, and algorithm terminates: Code: Select all  forall_vertices(G, function(a) { forall_vertices_after(G, a, function(b) { if (new Set(fw_path(G, next, a, b).concat(fw_path(G, next, b, a))).size !== dist[a][b]) { console.log("edges2:", fw_path(G, next, a, b), fw_path(G, next, b, a)); process.exit(1); } }); }); }); Obviously algorithm does not teminate early, and finishes in 1:44min: c70.8149.all_pairs_paths.bidirectional.png c70.8149.all_pairs_paths.bidirectional.png (33.43 KiB) Viewed 307 times https://hermann-sw.github.io/planar_graph_playground https://stamm-wilbrandt.de/en#raspcatbt https://github.com/Hermann-SW/memrun https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter https://stamm-wilbrandt.de/en/Raspberry_camera.html HermannSW Posts: 5254 Joined: Fri Jul 22, 2016 9:09 pm Location: Eberbach, Germany ### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface I started investigating using spherical coordinates for unit sphere: https://en.wikipedia.org/wiki/Spherical ... ate_system Instead of 3-dimensional space ℝ³ coordinate for a point on unit sphere, I used 2-dimensional spherical coordinates (not 3-dimensional since radius r=1 for unit sphere). tutte.js "convex_face_coordinates()" create x/y coordinates for outer face vertices like this: Code: Select all  var angle = Math.PI; var delta = factor * (2 * Math.PI) / face.length; assert.assert(is_embedding(Emb)); face.forEach(function (v) { x[v] = Math.sin(angle); y[v] = Math.cos(angle); angle -= delta; });  I did not want to change that code, so in modified "node.straight_line_drawing.3D.js" Code: Select all function map_3D(x, y) { // var a = Math.atan2(y, x); // var l = 0.9 * Math.PI * length_2D(x, y); // return [Math.sin(a) * Math.sin(l), Math.cos(a) * Math.sin(l), Math.cos(l)]; var a = Math.asin(x); var l = Math.acos(y); return [Math.sin(a) * Math.sin(l), Math.cos(a) * Math.sin(l), Math.cos(l)]; }  I used asin() and acos() to undo that and get back azimuthal angle a and polar angle l in radians. The mapping to 3D coordinates in function "map_3D()" is described as last in "Cartesian coordinates" section: https://en.wikipedia.org/wiki/Spherical ... oordinates Depending on whether number of vertices on outer face is odd (pentagon, left) or even (hexagon, right) 1/2 vertices have y=0, all others have y>0: C30_C60.y=0.png C30_C60.y=0.png (44.46 KiB) Viewed 177 times Now investigating options on how to get all outer face coordinates on equator, or at least some below as well. Reason is that I want to determine Tutte barycentric coordinates based on the 2-angle coordinates two times, once for blue circle and all vertices inside, and once for blue circle and all vertices outside, with blue circle as "outer face" (around two of the 4 tetrahedron shortest path triangles). And finally combine the determined coordinates for complete embedding of the graph onto unit sphere: C60.two_triangles.png C60.two_triangles.png (48.36 KiB) Viewed 177 times https://hermann-sw.github.io/planar_graph_playground https://stamm-wilbrandt.de/en#raspcatbt https://github.com/Hermann-SW/memrun https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter https://stamm-wilbrandt.de/en/Raspberry_camera.html HermannSW Posts: 5254 Joined: Fri Jul 22, 2016 9:09 pm Location: Eberbach, Germany ### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface OK, next step, this is how the cycle around two shortest path triangles will look like from front: two_triangles.3D.png two_triangles.3D.png (9.88 KiB) Viewed 113 times With this commit cycle around two shortest path triangles gets determined, and all inner vertices get marked: https://github.com/Hermann-SW/planar_gr ... bffb4e823a Where special case handling is missing for valid cases, an assertion makes sure to abort if needed. This is new output of enlarged "vertices", the 4 tetrahedron vertices on cycle, and all inner vertices: Code: Select all pi@pi400-64:~/planar_graph_playground$ ./rjs node.tetra.js graphs/C60.a
12 pentagons for graph
20 non-pentagons for graph
vertices: 0,5,35,48
max: 34
dists: 5 5 6 6 6 6
edges: 2,3,6,7,10,0,34,31,32,78,76,11,13,49,50,61,60,43,42,25,23,24,75
vertices: 0,5,35,48,18,19,20,21,14,13,34,33,32,31,30,29,38
pi@pi400-64:~/planar_graph_playground \$ 

Using the last two edges and vertices outputs

Code: Select all

./rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C60.a 0,5,35,48,18,19,20,21,14,13,34,33,32,31,30,29,38 2,3,6,7,10,0,34,31,32,78,76,11,13,49,50,61,60,43,42,25,23,24,75 > x.ps && gv x.ps

results in this wanted output (for debugging):
C60.two_triangles.marked_vertices.png
C60.two_triangles.marked_vertices.png (25.54 KiB) Viewed 113 times

For solving Tutte system of linear equations all vertices on cycle have to be marked.
The vertices on cycle get assigned coordinates determined from 4 tetrahedron vertices coordinates.
All inner vertices coordinates get computed by solving system of linear equations.

With the method how cycle vertices get coordinates, some will be above and some below equator, so all should be fine.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5254
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Short interrupt in "draw fullerene on unit sphere" efforts.

Yesterday I committed and pushed Raspberry Pi Pico-W (new, with Wifi) Access Point static file webserver:
https://github.com/Hermann-SW/pico-w
Main demo serves planar_graph_playground, the Pico-W is AP with IP address 192.168.4.1:

In graphs directory there are many maximal planar graphs, from maximal planar graph on 10 vertices 10.a to 2 million vertices maximal planar graph 2000000.a. Even small maximal planar graphs do not look nice in convex face straight line planar embedding, here "graphs/50.a":
50.pentagons.png
50.pentagons.png (30.74 KiB) Viewed 48 times

So I built new "node.to_dual.js" tool, that converts an embedding in adjacency list format to same format dual graph.
The main code is this:
https://github.com/Hermann-SW/planar_gr ... js#L16-L37
Parse input file, convert to graph, assert that it is an embedding and then create dual graph.
Later there will be a graph input/output format different from adjacency lists.
So the "write adjacency lists code" is not part of undirected_graph.js yet:

Code: Select all

L = parse2file(sel);

assert.assert(is_embedding(G));

D = dual_graph(G);

console.log("[");
var first = true;
forall_vertices(D, function(v) {
var a = [];

Code: Select all

    forall_incident_edges(D, v, function(e) {
a.push(opposite(D, v, e));
});
if (!first) {
console.log(",", a);
} else {
first = false;
console.log(a);
}
});
console.log("]");

I created dual graphs of maximal planar graphs on 10/20/50/100 vertices D10.a/D20.a/D50.a/D100a.
And I had to do a small fix wrt ".pentagons" outer face drawing code.
All this is committed and pushed:
https://github.com/Hermann-SW/planar_gr ... 14f2f9ef90

Dual graph of maximal planar graph on 50 vertices (with 3*50-6=144 vertices) looks quite nice as cubic graph (because all maximal planar faces are triangles):
D50.pentagons.png
D50.pentagons.png (39 KiB) Viewed 48 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html