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

[HermannSW]

Now that bigger amounts of fullerenes are available for testing in the repo, I looked at "might.js" discussed before in this thread again:
viewtopic.php?t=333342&start=25#p2012054

I have to decompress the "graphs/Cxy.txt.gz" files with zcat, and using "<(zcat ...)" results in "/dev/fd/63" filename; so I removed filename output.
Also I changed "might.js" to "might_be_foldable.js", because that is what gets tested.
Finally I fixed a wrong assumption, the two eighboring faces do not need to have same number of edges for the required test to be true.
https://github.com/Hermann-SW/planar_gr ... oldable.js

Execution with zcat now shows, that the only fullerenes that might be foldable with regular pentagons and regular hexagons are C20.1(=graphs/C20.a) and C60.936(=I60.1=graphs/C60.a):

Code: Select all

pi@pi400-64:~/planar_graph_playground $ for g in graphs/[CI]*.txt.gz
> do
> echo -ne "\r$g "
> out=`./rjs might_be_foldable.js <(zcat $g)`
> echo $out
> done | grep foldable
graphs/C20.txt.gz 1 might be foldable
graphs/C60.txt.gz 936 might be foldable
graphs/I60.txt.gz 1 might be foldable
pi@pi400-64:~/planar_graph_playground $ 

Playing again with my 3D printed regular pentagons and regular hexagons with magnetic balls at the edges:
https://forum.prusa3d.com/forum/english ... ost-609403

C36.14 with three connected components of pentagons is not really foldable, as reported by might_be_foldable.js:

20220613_202816.part.33%.jpg

20220613_202816.part.33%.jpg (25.18 KiB) Viewed 1208 times

graphs/C40.a (= "./ful 40 1") was easier to see not to be foldable by the non-matching edges between both orange layers of regular hexagons in the middle:

C40.plygons.png.25%.jpg

C40.plygons.png.25%.jpg (16.91 KiB) Viewed 1208 times

P.S:
The embedding of fullerene graphs onto sphere allows to see how they might look like, at least when spring embedder work is completed:

[HermannSW]

I used "forall_graphs()" in a second program, and therefore moved it into "undirected_grpah.js":
https://github.com/Hermann-SW/planar_gr ... #L311-L330

It has new 2nd argument, that allows to filter a single graph from the graphs in 1st argument "<(zcat graphs/....txt.gz)" in plantri52 form.
The filter is now used in new "node_6colorings.js" — there is "node_6coloring.js" which reads an adjacency lists embedding "graphs/*.a".
New program uses "forall_graphs()" to itterate over all embeddings of passed 1st argument and does "six_coloring()" for each.
Then it counts the real number of colors used by algorithm "six_coloring()", which is 6 or less.

"node.convex_face_straight_line_drawing.6coloring.js" colors a graph's faces.
"six_coloring(G)" determines a 6coloring of the vertices of G.
Determining 6coloring of G's faces is simply done by doing "six_coloring(dual_graph(G))":
https://github.com/Hermann-SW/planar_gr ... lorings.js

For face colorings of fullerenes numbers of colors used are in 4..6 range, and full range happens for C32:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ for((i=20; i<=32; i+=2))
> do
> echo $i
> ./rjs node_6colorings.js <(zcat graphs/C$i.txt.gz) -dual
> done
20
5 colors: 1
22
24
4 colors: 1

Code: Select all

26
5 colors: 1
28
5 colors: 1
30
5 colors: 1
32
4 colors: 4
5 colors: 2
6 colors: 1
pi@pi400-64:~/planar_graph_playground $ 

The reported numbers mean that first C32.x graph colored with 4 colors is C32.4, first with 6 colors is C32.1.

This creates face 4coloring of C32.4:

Code: Select all

./rjs node.convex_face_straight_line_drawing.6coloring.js <(./ful 32 4) > x.ps

C32.4.face_4coloring.png

C32.4.face_4coloring.png (48.59 KiB) Viewed 1151 times

This creates face 6coloring of C32.1:

Code: Select all

./rjs node.convex_face_straight_line_drawing.6coloring.js <(./ful 32 1) > x.ps

C32.1.face_6coloring.png

C32.1.face_6coloring.png (43.12 KiB) Viewed 1151 times

For all six non-isomorphic C32 fullerenes "six_coloring(G)" creates a 3coloring of the vertices:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./ful 32 
6
pi@pi400-64:~/planar_graph_playground $ ./rjs node_6colorings.js <(zcat graphs/C32.txt.gz)
3 colors: 1
pi@pi400-64:~/planar_graph_playground $

Now using "-dual" option 3colors dual graph of C32.1 (all faces are tringles, because all vertices of C32.1 have degree 3):

Code: Select all

./rjs node.convex_face_straight_line_drawing.6coloring.js <(./ful 32 1) -dual > x.ps

C32.1.dual.face_3oloring.png

C32.1.dual.face_3oloring.png (42.4 KiB) Viewed 1151 times

[HermannSW]

I want to be able to access the nearly 32,000 fullerene embeddings in online browser demo (currently only 6 can be selected):
https://hermann-sw.github.io/planar_graph_playground/

I learned that a <select> having 100s of <option> childs is OK, but not more than 8,000.
So for "C46.102" I did split the number 102 into div hundred part and mod 100 part, and have a <select> for each part:

new_fullerene_select.png

new_fullerene_select.png (7.72 KiB) Viewed 1066 times

I have the JavaScript code for that already (there are 116 non-isomorphic C46 fullerenes):

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./ful 46
116
pi@pi400-64:~/planar_graph_playground $ 

Next I need to be able to do "zcat C30.txt.gz" in browser JavaScript, and just posted on how to do that:
viewtopic.php?t=340149



Now all the pieces need to be glued together, and then online browser planar_graph_playground will have access to all those fullerenes.
After that I will add "face coloring" selection with options "pentagons/6colorring/none".

[HermannSW]

It was more difficult to store the 32,000 fullerenes on "https://hermann-sw.github.io/".

I verified that github.io does automatically transfer .html as well as .js files gzipped (with Wireshark).
But I did not want to rely on that, so I stored .gz files.
But I did not want to store 32,000 files on github.io, so I packked 100 fullerenes into one file and gzipped that.
Eg. "a.gz/C60.17xy.js.gz" contains C60.1700..C60.1799 fullerenes.

Biggest flle is "a.gz/I96.1xy.js.gz" of size 8529 bytes, smallest file "a.gz/C22.0xy.js.gz" of size 35 bytes (there are no C22 fullerenes):

Code: Select all

$ zcat ../a.gz/C22.0xy.js.gz; echo
[[]]
$

Total size of "a.gz" directory is 1692KB.

With latest planar_graph_playground commit, new "to_adjacency_lists()" became available, to convert a graph into list of adjacency lists for writing embedding information to file:
https://github.com/Hermann-SW/planar_gr ... 22f7ecb43a

to_adjacency_lists.png

to_adjacency_lists.png (42.53 KiB) Viewed 994 times

In "graphs/a.gz" script "generate.100.js" reads uncompressed plantri file and iterates over the read graphs, writing a single file for each set of 100 fullerenes:
https://github.com/Hermann-SW/planar_gr ... ate.100.js

Bash script "generate" makes use of that NodeJS script and creates all 352 files:
https://github.com/Hermann-SW/planar_gr ... z/generate

Code: Select all

#!/bin/bash
rm -f C* I*
for((i=20; i<=70; i+=2))
do
  ../../rjs generate.100.js <(zcat ../C$i.txt.gz) C$i
done
for((i=60; i<=100; i+=2))
do
  ../../rjs generate.100.js <(zcat ../I$i.txt.gz) I$i
done
gzip C*js I*js

No need to use pako here, simply using Linux zcat and gzip commands for decompression/compression.


After "git submodule update --init --remote -- planar_graph_playground" in "hermann-sw.github.io" repo and generating the 352 files, I learned that I could not commit those to "hermann-sw.github.io" repo. So I copied a.gz graph files under "hermann-sw.github.io" repo and committed and pushed there:
https://github.com/Hermann-SW/Hermann-S ... aster/a.gz

Under github.io repo file "planar_graph_playground/convex_face_straight_line_drawing.js" accesses the new files via "../a.gz/...":

Code: Select all

...
    const req = new XMLHttpRequest();
    req.addEventListener("load", reqListener);
    req.open("GET", "../a.gz/"+t.value+"."+n1.value+"xy.js.gz");
    req.responseType = "arraybuffer";
    req.send();
...

Files get loaded from browser only on 1st request, afterwards they are retrieved from memory or disk cache.

[HermannSW]

Back in April I started to work on cuboid surface shortest path problem, and found an example where shortest path between two points needs to visit 4 faces:
https://twitter.com/HermannSW/status/15 ... 5390921729
The screenshot was created with planar_graph_playground example using htmlsvg.js, online here:
https://hermann-sw.github.io/planar_gra ... rtest_path



In the last days I got the idea how to solve that problem, for cuboid with different size lengths, and with OpenSCAD output.
New "scad.header3()" (only 37 lines) provides what is needed to embed a graph onto cuboid surface (instead of sphere):
https://github.com/Hermann-SW/planar_gr ... 54da49a154

Nearly no geometry is needed, I just discretize the 12 edges of the cuboid by introducing variable numer of vertices.
After creating the required graph, just calling "floyd_warshall[_path](G, w)" all pairs shortest path problem does the job.
Until today these functions worked on unit edge length, I added optional passing wheight edge mapping "w" today:
https://github.com/Hermann-SW/planar_gr ... f934041d22

I used this command for generating below explanation screenshots (modifying code to display the edges of interest only).
Start point is (0.4, 0.2, 0), target points are 2*2 points on top (z=1) because of dividing into 3 parts (last arg).
Cube edges are divided into 4 parts.
X direction length is always 1, lengths for Y and Z are passed after start point:

Code: Select all

./rjs node.cuboid_surface_shortest_path.js 0.4 0.2 1 1 4 3

Left shows start point, it is connected to each vertex of bottom face.
Middle shows top target points, each is connected to all top corner and cube edge vertices.
Both get done by "mk_complete_bipartite()":
https://github.com/Hermann-SW/planar_gr ... js#L87-L93

cube.shortest_path.png

cube.shortest_path.png (116.61 KiB) Viewed 916 times

Right shows the dges for a side face, just complete graph of all vertices, done with "mk_complete()":
https://github.com/Hermann-SW/planar_gr ... js#L78-L85

All edges get 3D distance between its source and target vertex coordinates as weight:
https://github.com/Hermann-SW/planar_gr ... #L114-L122

Code: Select all

function dist3D(p, q) {
    var d = [p[0] - q[0], p[1] - q[1], p[2] - q[2]];
    return Math.sqrt(d[0]*d[0] + d[1]*d[1] + d[2]*d[2]);
}

var w = filled_array(n_edges(G), 1, -1);
forall_edges(G, function(e) {
    w[e] = dist3D(coords[source(G, e)], coords[target(G, e)]);
});

Running for cube (X=Y=Z=1) with this command, start point at (0.4, 0.2, 0).
Cube edges get divided into 100 pieces, resulting in 99 vertices.
Top face gets divided into 20 poices, resulting in 19*19 top face target vertices in topc:

Code: Select all

./rjs node.cuboid_surface_shortest_path.js 0.4 0.2 1 1 100 20

This is bottom view of start point:

cube.shortest_path.bottom_big.png

cube.shortest_path.bottom_big.png (39.51 KiB) Viewed 916 times

Determining number of edges on shortest path is done with "nedges()":
https://github.com/Hermann-SW/planar_gr ... #L147-L155

Following shortest path from each target point (vertex) is done by iterationg "topc" and following shortest path (with "next" array) to start point s, and draring all edges with the determined color:
https://github.com/Hermann-SW/planar_gr ... #L157-L167

Code: Select all

topc.forEach(function (v) {
    var cnt = nedges(v, s);
    assert.assert( (cnt > 2) && (cnt < 5) );
    var col = (cnt === 4) ? [0,0,1] : [1,0.666666,0];

    while (v !== s) {
        var e = next[v][s];
        scad.wlog("color(",col,") edge(",source(G, e),",",target(G, e),",",0.005,");");
        v = opposite(G, v, e);
    }
});

And here is top view animation, blue shortest paths have 4 edges, orange shortest paths have 3 edges.
Wonderful example showing that there can be 3 distint regions on top face with 4 edges shortest paths (blue)!



Demonstration that algorithm works for X=1, Y=0.8, Z=1.2 cuboid as well:

Code: Select all

./rjs node.cuboid_surface_shortest_path.js 0.65 0.1 0.8 1.2 100 20

cuboid.shortest_path.png

cuboid.shortest_path.png (70.63 KiB) Viewed 916 times

P.S:
I forgot to mention, that execution for N=100 and n=20 takes less than 1 minute runtime:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ time ./rjs node.cuboid_surface_shortest_path.js 0.4 0.2 1 1 100 20

real	0m47.210s
user	0m49.777s
sys	0m1.548s
pi@pi400-64:~/planar_graph_playground $ 

I appended this line, and learned that the generated graph consists of n=1558 vertices and m=464000(!) edges:

Code: Select all

console.log(n_vertices(G), n_edges(G));

The inner loop of "floyd_warshall_path()" for updating shortest path distances is executed n³ = 3,781,833,112 times:
https://github.com/Hermann-SW/planar_gr ... #L547-L556

[HermannSW]

First, there was a small error that I resolved with single character fix (few edges in generated graph were wrong).
https://github.com/Hermann-SW/planar_gr ... c19ba0914f
This time I verified that all generated edges are as they should.

Next I tried to construct a cuboid that has shortest paths that pass through 5 faces — and I found some!

Small diff adds a "mirror" below cuboid (described previously here) that allows to "see" bottom face as well. And doubles edge width to before:
https://github.com/Hermann-SW/planar_gr ... f5e09b691b

I am pretty sure that no shortest path can pass through 6 faces of cuboid, just to be sure I added red color for that case:

3-6.colors.png

3-6.colors.png (24.6 KiB) Viewed 838 times

After having found nice start point (0.2, 0.4, 0) for 1×1×3 cuboid with lower N (cube edge division) and lower n (with (n--1)*(n-1) top face target points), I increased both to 150/50 and that computation took nearly 13 minutes on my Pi400. Generated graph has 4198 vertices this time, and more than 2 million edges. Maximal path length determined and reported is 5:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ time ./rjs node.cuboid_surface_shortest_path.js 0.2 0.45 1 3 150 50
maximal path edges: 5
n: 4198 m: 2160000

real	12m43.355s
user	12m52.712s
sys	0m3.006s
pi@pi400-64:~/planar_graph_playground $

Here is the result, orange/blue/yellow shortest paths pass through 3/4/5(!) faces: