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

[HermannSW]

In thread "C/C++(JavaScript) | planar graphs | draw fullerene in 2D/3D"
viewtopic.php?t=332496

the original plan was to use Boost graph library to do the job.
But for quick prototyping and interaction I did planar_graph_playground for browser with JavaScript and SVG output first.
Can be played with live here:
https://hermann-sw.github.io/planar_graph_playground/

I created several small JavaScript libraries in the repo, the biggest being undirected_graph.js.

Yesterday I posted about small tool rjs to run the library with C includes on the command line with nodejs:
viewtopic.php?t=333272

I updated node_test.js from yesterday to make use of new "print_graph()":

Code: Select all

#include "assert.js"
#include "fullerenes.js"
#include "undirected_graph.js"
#include "gauss-jordan.js"

var lookup = [];
var G = from_adjacency_list(F[0]);
assert.assert(is_embedding(G));

console.log("is_embedding(C20) verified, has " + n_faces_planar(G) + " faces");
print_graph(G, "C20: ");

This is the output for fullerene graph C20 (dodecahedron):

Code: Select all

pi@pi400-64:~/planar_graph_playground $ rjs node_test.js 
is_embedding(C20) verified, has 12 faces
C20: 20 vertices, 30 edges
0: (0)9 (1)10 (2)1
1: (2)0 (3)2 (4)15
2: (3)1 (5)14 (6)3
3: (6)2 (7)4 (8)16
4: (7)3 (9)13 (10)5
5: (10)4 (11)6 (12)17
6: (11)5 (13)12 (14)7
7: (14)6 (15)8 (16)18
8: (15)7 (17)11 (18)9
9: (18)8 (0)0 (19)19
10: (1)0 (20)11 (21)14
11: (20)10 (17)8 (22)12
12: (22)11 (13)6 (23)13
13: (23)12 (9)4 (24)14
14: (24)13 (5)2 (21)10
15: (4)1 (25)16 (26)19
16: (25)15 (8)3 (27)17
17: (27)16 (12)5 (28)18
18: (28)17 (16)7 (29)19
19: (29)18 (19)9 (26)15
pi@pi400-64:~/planar_graph_playground $ 

The browser tool I linked to above displays C20 like this:

C20.png

C20.png (55.82 KiB) Viewed 5516 times

The tool colors all pentagon faces in embedding.
For fullerenes there are always 12 pentagons and "2 + n_edges(G) - n_vertices(G) - 12" hexagons.
So what you see is regular dodecahedron as planar embedding, Wikipedia shows it in 3D:
https://en.wikipedia.org/wiki/Regular_dodecahedron



I made use of "planar face traversal visitor" concept from Boost graph library, just for the naming:
https://www.boost.org/doc/libs/1_79_0/b ... versal.hpp

Instead of defining all functions in a struct, I used JSON object for JavaScript with only defining the functions I want to use. Only cost for that is having to check for undefined before calling:

Code: Select all

        if (pftv.next_vertex_edge) {
            pftv.next_vertex_edge(v, e);
        }

"next_vertex_edge(v, e)" is the only function I added to the 6 Boost functions. I need that in order to know in which direction the undirected edge e is traversed (from v). I made use of that in new "D = dual_graph(G)", which constructs the dual graph of a planar graph G (which needs to be embedded, that is order of edges in its vertex adjacency lists corresponds to a counter clockwise traversal of a fixed embedding of the graph into the plane). Vertices and edges in current JavaScript implementation are just 0 based indices into arrays G.V and G.E. I keep the bijection between G's and D's edges simply by using identical edge numbers. Vertices of new dual graph D correspond to faces of G, and vertices in D are connected if and only if corresponding faces are neighbor faces in G.

"dual_graph(G)" is here on github:
https://github.com/Hermann-SW/planar_gr ... #L237-L257

The function turned out to be so simple, now that planar face traversal visitors are used (all JavaScript code in the repo is JSlinted, which forced me to write code the way I did.) I like what JSlint forced me to do with passed planar face traversal visitor functions, but what it requires wrt ternary operators is a bit too line consuming for me, here for auxiliary function:

Code: Select all

function ud2st(str) {
    return (
        (str === undefined)
        ? ""
        : str
    );
}

last_face is initialized to "undefined" as 0 base number.
e2f is edge to face mapping, with two entries per edge for the different traversal directions, initialized with -1 as "undefined" as well.
"n_planar_faces(G)" returns the number of faces in embedded graph G, and is used to create new graph D with just as many vertices and without edges:

Code: Select all

function dual_graph(G) {
    var last_face = -1;
    var e2f = linear.fill(n_edges(G), 2, -1);
    var D = new_graph(n_faces_planar(G));

    full_traverse(G, {begin_face: function () {
        last_face += 1;
    }, next_vertex_edge: function (v, e) {
        e2f[e][ind(G, v, e)] = last_face;
    }});

"full_traverse()" just increments last_face when traversal of a new face starts.
"ind(G, v, e)" returns index (0 or 1) to be used in e2f array.
For current face traversal the new face number (last_face) gets stored for all edges of the face.

Normally new edge gets created with "new_edge(G, v, w)", but that is no option here since it will not result in an embedding of D.
For the graph representation, for vertex v G.V[v] is array of the edges adjacent to v.
For edge e G.E[e] is array containg of two arrays of 2 elements.
First of the elements in 2-arrays is a vertex, 2nd is index of edge e in that vertex' adjacency list array.
In order to get the control of the ordering in the vertex adjacency lists G.E[e] needs to be initialized as empty array for all edges e:

Code: Select all

    forall_edges(G, function () {
        D.E.push([]);
    });

    full_traverse(G, {next_vertex_edge: function (v, e) {
        new_edge_vertex(D, e2f[e][ind(G, v, e)], e);
    }});

    return D;
}

Finally, 2nd full traversal of the graph just needs to insert edge e into D's adjacency list with "new_vertex_edge()" function that exists for just this purpose. And the newly created dual graph D is returned.

I created new nodejs test script with C includes for "dual_graph()" testing (by asserting that created dual graph is an embedding as well):
https://github.com/Hermann-SW/planar_gr ... de_dual.js

After including all that is needed, array lookup needs to be initialized as empty array, used in "from_adjacency_list(L)". It uses O(n²) space for graph with n vertices which is not nice for planar graphs which have at most m=3n-6 edges, so linear in number of vertices. This array is needed for perfect hash table for the edges — in "dual_graph()" lookup is not needed since edge e is retrieved from planar face traversal and does not need "to be remembered for 2nd time edge is traversed". Full graph on 5 vertices K5 is not planar, but removing one edge (K5me) makes it planar, and K5me is adjacency list representation of an embedding with vertices in the lists instead of edges in graph representation. Graph G is created from K5me then:

Code: Select all

#include "assert.js"
#include "fullerenes.js"
#include "undirected_graph.js"
#include "gauss-jordan.js"

var lookup = [];
var K4 = [[1, 3, 2], [2, 3, 0], [0, 3, 1], [0, 1, 2]];
var K5me = [[1, 2, 3, 4], [2, 0, 4], [4, 3, 0, 1], [4, 0, 2], [1, 0, 3, 2]];
var D;
var G = from_adjacency_list(K5me);

First it is asserted that graph G is an embedding, implementation of that function with planar face traversal is so nice:
https://github.com/Hermann-SW/planar_gr ... #L210-L218
Then graph is printed, with name and number of faces additionally:

Code: Select all

assert.assert(is_embedding(G));
console.log("is_embedding(K5-e) verified, has " + n_faces_planar(G) + " faces");
print_graph(G, "K5-e: ");

D = dual_graph(G);
assert.assert(is_embedding(D));
console.log("is_embedding(dual_graph(K5-e)) verified, has " + n_faces_planar(D) + " faces");
print_graph(D, "dual_graph(K5-e): ");

Next dual graph D is computed, and is_embedding() is asserted for it as well.
Finally same output as for graph G is created for dual graph.

And this is execution:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ rjs node_dual.js 
is_embedding(K5-e) verified, has 6 faces
K5-e: 5 vertices, 9 edges
0: (0)1 (1)2 (2)3 (3)4
1: (4)2 (0)0 (5)4
2: (6)4 (7)3 (1)0 (4)1
3: (8)4 (2)0 (7)2
4: (5)1 (3)0 (8)3 (6)2
is_embedding(dual_graph(K5-e)) verified, has 5 faces
dual_graph(K5-e): 6 vertices, 9 edges
0: (0)1 (5)4 (3)3
1: (0)0 (1)2 (4)4
2: (1)1 (2)3 (7)5
3: (2)2 (3)0 (8)5
4: (4)1 (6)5 (5)0
5: (6)4 (7)2 (8)3
pi@pi400-64:~/planar_graph_playground $ 

planar_graph_playground has htmlsvg.js JavaScript that does the drawing of graph as SVG in browser HTML.

I just started "ps.js", which will do similar output as postscript file.
This will allow to view generated PostScript with a viewer (eg. evince), of just print on printer.

P.S:
In the early 90s as researcher I gave computer science programming courses, and the C code students had to write was required to create PostScript file with the computed results (eg. a random maze). I saw really creative ideas in student homeworks. So back to the (generate postscript) roots ...

[HermannSW]

Wow, 21 line "dual_graph()" can be reduced by another 5 lines ...

I looked at code discussed in previous posting (left).

Filename File comment Size Status
another_5_lines_eliminated.png

another_5_lines_eliminated.png (65.72 KiB) Viewed 5456 times

First I realized that I could move line 253 command into line 244 "next_vertex_edge()" if I would move D.E initialization loop up, which is no problem.

With that code there was no need to use e2f edge array anymore, so I removed it.

Then JSlint complained that variable v in "next_vertex_edge()" was unused now.
So I switched to using "next_edge()" function of the 6 Boost functions — I will keep "next_vertex_edge()" for now.

Then I wanted to fix D.E initialization sloppy function "forall_edges(G, function () {", since implementation of "forall_edges()" passes the current edge as argument to the function. I don't know what JavaScript does with excess arguments — while it worked, it is at least not clean.

So I tried "D.E = new Array(n_edges(G)).fill([])" to get array with n_edges(G) empty arrays inside, but that did not work.
Next I tried "D.E = new Array(n_edges(G)).map(function () { return []; })", but map does not work on indices not used before.
So finally I inserted "fill(0)" before map function call, and then it worked.
Again JSlint forced the single line of code to become 3 lines (241-243), but they look nice.

I already committed and pushed the change, new 16 line dual_graph() is here (right side of above image):
https://github.com/Hermann-SW/planar_gr ... #L237-L252

[HermannSW]

Just found better command than "new Array(n_edges(G)).fill(0).map(...)" in previous implementation I used for "new_graph(n)", using "Array.from(...)":

Code: Select all

function new_graph(n) {
    const A = Array.from(new Array(n), function () {
        return [];
    });
    return {E: [], V: A};
}

Just added optional 2nd argument m as number of edges. If not passed (undefined), m is changed to 0. New code:
https://github.com/Hermann-SW/planar_gr ... js#L79-L89

Code: Select all

function new_graph(n, m) {
    if (m === undefined) {
        m = 0;
    }
    return {E: Array.from(new Array(m), function () {
        return [];
    }),
        V: Array.from(new Array(n), function () {
        return [];
    })};
}

With that "dual_graph()" again was reduced, from 16 to only 12 lines of code — seems pretty minimal right now:
https://github.com/Hermann-SW/planar_gr ... #L242-L253

Code: Select all

function dual_graph(G) {
    var last_face = -1;
    var D = new_graph(n_faces_planar(G), n_edges(G));

    full_traverse(G, {begin_face: function () {
        last_face += 1;
    }, next_edge: function (e) {
        new_edge_vertex(D, last_face, e);
    }});

    return D;
}

P.S:
Renamed "full_traverse()" to "planar_face_traversal()" …
https://github.com/Hermann-SW/planar_gr ... ea5b3d6c43
… for getting closer to Boost graph library naming. Boost "planar_face_traversal()" has more arguments than current undirected_graph.js implementation:
https://www.boost.org/doc/libs/1_79_0/l ... ersal.html

[HermannSW]

I extended "node_dual.js" to become first "undirected_graph.js" validation code.
It uses new "is_identical_graph()" to verify that "K5-e" and "dual_graph(dual_graph(K5-e))" are identical:

Code: Select all

$ git diff node_dual.js
...
+
+assert.assert(is_identical_graph(G, dual_graph(D)));
+console.log("is_identical(K5-e, dual_graph(dual_graph(K5-e))) verified");
+
$ 

Implementaion of "is_identical_graph()" uses deeply nested "Array.every()" calls for the job:

Code: Select all

function is_identical_graph(G, H) {
...
    if (!G.E.every(function (e, i) {
        return e.every(function (v, j) {
            return v.every(function (x, k) {
                return x === H.E[i][j][k];
            });
        });
    })) {
        return false;
    }
    return true;
}

Validation is succeessful:

Code: Select all

$ rjs node_dual.js 
is_embedding(K5-e) verified, has 6 faces
K5-e: 5 vertices, 9 edges
...
4: (5)1 (3)0 (8)3 (6)2
is_embedding(dual_graph(K5-e)) verified, has 5 faces
dual_graph(K5-e): 6 vertices, 9 edges
...
5: (6)4 (7)2 (8)3
is_identical(K5-e, dual_graph(dual_graph(K5-e))) verified
$ 

Available with this pushed commit:
https://github.com/Hermann-SW/planar_gr ... bd65ffdbbf

[HermannSW]

I just started "ps.js", which will do similar output as postscript file.
This will allow to view generated PostScript with a viewer (eg. evince), of just print on printer.

Done with the basics of postscript functionality to be able to draw similar to this browser screenshot created from htmlsvg.js JavaScript code:



This is screenshot of "ps_done.ps" viewed in "evince" viewer:

ps_done.ps.png

ps_done.ps.png (12.45 KiB) Viewed 5316 times

ps_done.ps is here:
https://gist.github.com/Hermann-SW/973b ... 86f85814c2

Setting line width, selecting font and size, and drawing square around the area that will be used (fits A4 as well as letter formats):

Code: Select all

%!

0 setlinewidth

/Times-Roman findfont 12 scalefont setfont

newpath 8 99 moveto 601 99 lineto 601 692 lineto 8 692 lineto closepath stroke

/vertex definition just draws a circle with white filled inside.
In case radius is ≥12, centered string is drawn inside that vertex, otherwise superfluous stack entries get "pop"ed away:

Code: Select all

/vertex { 2 copy 5 4 roll dup 4 1 roll
  newpath 0 360 arc closepath
  gsave 1.0 setgray fill grestore
  stroke
  12 ge { 
    newpath moveto
    gsave dup false charpath flattenpath pathbbox grestore
    exch 4 1 roll exch sub -.5 mul 3 1 roll sub -.5 mul exch
    rmoveto show
  } { pop pop pop } ifelse
} def

This was tricky, I looked at many PostScript tutorials, articles, ebooks — and all missed to describe "count" function I needed to check whether stack is empy. /poly loops over n points for stack of size 2n, and creates a "newpath moveto lineto lineto … lineto" path from them, regardless how long:

Code: Select all

/poly {
  newpath
  moveto
  {
    count 0 eq { exit } if
    lineto
  } loop
} def

Here is the demo code using /vertex and /poly, for drawing a filled face with vertices bigger and smaller than radius 12:

Code: Select all

.75 setgray 300 400 200 400 200 300 275 325 poly fill

0 setgray 300 400 200 400 200 300 275 325 poly closepath stroke 

(89) 18 300 400 vertex
(123) 12 200 400 vertex
(3) 6 200 300 vertex
(55) 9 275 325 vertex

showpage

So next step is make use of /poly and /vertex in ps.js, and define few more that might be useful. But this was the needed big first step for ps.js.


P.S:
I just checked my 42 repos on github.com and was surprised that 21 had a license. That was most likely by starting work with forking other peoples projects.

When I started planar_graph_playground I intentionally selected permissive MIT license, so you can make use of this library:
https://mit-license.org/


I did not think much about licenses, until I started publishing 3D models on printables.com — there you have to select a license from few available before being able to publish a new model:
https://www.printables.com/social/23696 ... nsw/models

[HermannSW]

With latest commits+push PostScript output is available, conterpart to htmlsvg.js is ps.js:
https://github.com/Hermann-SW/planar_gr ... round#psjs

New demo application "node.convex_face_straight_line_drawing.js" creates C30.ps for now ("rjs" command line argument handling is currently missing):
https://github.com/Hermann-SW/planar_gr ... _drawingjs

Code: Select all

$ rjs node.convex_face_straight_line_drawing.js > C30.ps
$ 

Here is created PostScript file for inspection:
https://github.com/Hermann-SW/planar_gr ... ain/C30.ps

I created 3 laser printouts, left with checked in linewidth 1, right with linewidth 2/0 top/bottom:

20220421_155813.part.16pc.jpg

20220421_155813.part.16pc.jpg (27.29 KiB) Viewed 5211 times

P.S:
I added "G is identical to dual(dual(G))" tests for C20, C30, ...., C70 fullerenes to node_dual.js.
So works for non toy graphs as well (C70 has 70 vertices, 3*70/2=105 edges and 2+105-70=37 faces):

Code: Select all

$ rjs node_dual.js 
...
5: (6)4 (7)2 (8)3
is_identical(K5-e, dual_graph(dual_graph(K5-e))) verified
is_identical(C20, dual_graph(dual_graph(C20))) verified
is_identical(C30, dual_graph(dual_graph(C30))) verified
is_identical(C40, dual_graph(dual_graph(C40))) verified
is_identical(C50, dual_graph(dual_graph(C50))) verified
is_identical(C60, dual_graph(dual_graph(C60))) verified
is_identical(C70, dual_graph(dual_graph(C70))) verified
$ 

[HermannSW]

I added a "dual" checkbox to browser convex_face_straight_line_drawing demo.
That checkbox determines whether the fullerene selected, or its dual graph should be drawn.
While at adding new input element, I arranged the sliders and new checkbox horizontally.

Committed and pushed changes to repo (https://github.com/Hermann-SW/planar_graph_playground) and published online tool got updated as well, for playing with new feature:
https://hermann-sw.github.io/planar_graph_playground/

Because fullerenes are 3-regular graphs (all vertex degrees are 3), their dual graphs are maximal planar graphs (all faces are triangles). The twelve fullerene pentagon faces become 12 vertices of degree 5 in dual graph. So if dual is checked, vertices of degree 5 are filled with the color the pentagons are filled with without dual checked.

Not much changes needed, this is the new logic for handling dual graph vertex coloring (JSlint forced ternary expression onto 5 lines):
https://github.com/Hermann-SW/planar_gr ... 228f934835

Code: Select all

            vcol = (
                (dual && (degree(G, v) === 5))
                ? "#00ced1"
                : "white"
            );
            document.write('<circle cx="' + cx + '" cy="' + cy + '" r="' + r + '" stroke="black" fill="' + vcol + '"></circle>');

Here is a small demo presenting C30 fullerene and its dual:

Peek_2022-04-22_11-53.gif

Peek_2022-04-22_11-53.gif (152.33 KiB) Viewed 5144 times

[HermannSW]

Two days ago I learned that Python Mathplotlib with networkx draw_planar() allows for planar straight line drawing with integer coordinates. The angles can become quite small, so I prefer the convex face drawing from this thread. Most interesting for me was, that Matplotlib has builtin zoom capabilities! Here my C30.py fullerene demo screenrecording from Friday's tweet:
https://twitter.com/HermannSW/status/15 ... 2681232386



Interestingly networkx graph datatype has no representation for edges like my lib had as well in the beginning. So I wanted to see whether I could port the current library to Python, and it was possible after a whole Python port day yesterday. Only dual_graph() has a small problem currently. Like with nodejs rjs tool, I did need a nonstandard include mechanism for Python as well. Used same C #include technique as with rjs:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ cat rpy
#!/bin/bash
gcc -E -x c -nostdinc $1 | grep -v "^#"  | python
pi@pi400-64:~/planar_graph_playground $ 

From start I used pylint as well, but wanted to make both libraries looking as similar as possible. So I excluded a lot of the Python camelCase warnings using this script, that does know #include handling as well:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ cat rpylint 
#!/bin/bash
gcc -E -x c -nostdinc $1 | grep -v "^#" > /tmp/rpylint
pylint --docstring-min-length=100 --argument-naming-style=any --variable-naming-style=any --attr-naming-style=any --function-naming-style=any --class-naming-style=any --min-public-methods=0 /tmp/rpylint
pi@pi400-64:~/planar_graph_playground $ 

And test code verifying C20 fullerene is_embedding

Code: Select all

#include "fullerenes.py"
#include "ug.py"

lookup = []
K4 = [[1, 3, 2], [2, 3, 0], [0, 3, 1], [0, 1, 2]]

#pragma H = from_adjacency_list(K4)
H = from_adjacency_list(F[0])
print_graph(H, "foo: ")
print("is_embedding:", is_embedding(H))
print(nfaces, "faces")

works:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./rpy t.py
foo: 20 vertices, 30 edges
0: (0)9 (1)10 (2)1
1: (2)0 (3)2 (4)15
2: (3)1 (5)14 (6)3
3: (6)2 (7)4 (8)16
4: (7)3 (9)13 (10)5
5: (10)4 (11)6 (12)17
6: (11)5 (13)12 (14)7
7: (14)6 (15)8 (16)18
8: (15)7 (17)11 (18)9
9: (18)8 (0)0 (19)19
10: (1)0 (20)11 (21)14
11: (20)10 (17)8 (22)12
12: (22)11 (13)6 (23)13
13: (23)12 (9)4 (24)14
14: (24)13 (5)2 (21)10
15: (4)1 (25)16 (26)19
16: (25)15 (8)3 (27)17
17: (27)16 (12)5 (28)18
18: (28)17 (16)7 (29)19
19: (29)18 (19)9 (26)15
is_embedding: True
12 faces
pi@pi400-64:~/planar_graph_playground $ 

When complete I will create Python graph library thread in Python forum with details and design decisions. What I want to show here is how similar JavaScript (left) and Python (right) implementation of same functions looks:
function --> def or lambda
...) { --> ...):
closing func } --> nothing
unfortunately lambda is much less powerful than JavaScript anonymous functions, so global variables are needed for callbacks

python_port.png

python_port.png (89.08 KiB) Viewed 5084 times

P.S:
Normal "#" Python comments do not work with C preprocessor involved in rpy tool, but "#pragma this is some comment" works with rpy.

[HermannSW]

unfortunately lambda is much less powerful than JavaScript anonymous functions, so global variables are needed for callbacks

I have to correct myself, NO globals are needed with Python lambda as seen in "planar_face_traversal()" in previous posting.
Solution to get "is_ebedding()" work without global variables, is to pass integer variable "nfaces" by reference.
There might be a better way, but just passing 1-element array "nfaces" does the job!

python_port.2.png

python_port.2.png (37.74 KiB) Viewed 5050 times

I am so happy to get away with lambda callbacks without global variables ...

P.S:
Generic "incr(arr, i=0)" function incrementing index i in array arr is better:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ diff --width=118 --side-by-side old new
def is_embedding(G):						def is_embedding(G):
    nfaces = [0]						    nfaces = [0]
    def incnfaces(nfaces):				  |	    def incr(arr, i=0):
        nfaces[0] += 1					  |	        arr[i] += 1

    pftv = planar_face_traversal_visitor()			    pftv = planar_face_traversal_visitor()
    pftv.begin_face = lambda: incnfaces(nfaces)		  |	    pftv.begin_face = lambda: incr(nfaces)
    planar_face_traversal(G, pftv)				    planar_face_traversal(G, pftv)

    return n_vertices(G) - n_edges(G) + nfaces[0] == 2		    return n_vertices(G) - n_edges(G) + nfaces[0] == 2
pi@pi400-64:~/planar_graph_playground $ 

[HermannSW]

It was good to have ported to Python, because that identified a JavaScript bug in assert.js.
Assertion code worked when run from browser, but not when executed via "rjs" tool on command line, that is fixed now:
https://github.com/Hermann-SW/planar_gr ... af7d902a9d

With working assertion, "is_identical_graph(G, dual_graph(dual_graph(G))" failed.
Reason is simple, computing two times the dual graph does not result in original graph.
From execution of new "node_dual.js" below, this is K5me:

Code: Select all

K5-e: 5 vertices, 9 edges
0: (0)1 (1)2 (2)3 (3)4
1: (4)2 (0)0 (5)4
2: (6)4 (7)3 (1)0 (4)1
3: (8)4 (2)0 (7)2
4: (5)1 (3)0 (8)3 (6)2

And this is dual graph of dual graph of K5me:

Code: Select all

dual_graph(dual_graph(K5-e)): 5 vertices, 9 edges
0: (0)1 (1)2 (2)3 (3)4
1: (0)0 (5)4 (4)2
2: (1)0 (4)1 (6)4 (7)3
3: (2)0 (7)2 (8)4
4: (3)0 (8)3 (6)2 (5)1

As can be seen the graphs are not identical.
But for each vertex you can see same edges in same order appearing after some offset.
Eg. for vertex 1 edge sequence is 4,0,5.
Same edge sequence is in dual(dual(K5me)), but only when starting at offset 2.
So I implemented new function "is_same_embedding(G,H)", which tests that vertices, edges sequences and more are identical.
https://github.com/Hermann-SW/planar_gr ... #L286-L324

As shown above, that function returns true for K5me and dual(dual(K5me)), but not for any fullerene graph.
So for fullerenes C20, C30, ..., C70 only is_embedding() is asserted for dual of dual of the fullerene.

node_dual.js.new.png

node_dual.js.new.png (68.21 KiB) Viewed 4972 times

[HermannSW]

Just created new thread "Python(+JavaScript) graph library, for embedding and drawing planar graphs in 2D and/or sphere surface" in Python forum on initial Python library commit.
viewtopic.php?t=333536

What does work already is the equivalent to "node_dual.js" described in previous posting — "python_dual.py":

python_dual.py.png

python_dual.py.png (59.03 KiB) Viewed 4939 times

[HermannSW]

Postscript output ps.js got refreshment (new map() function).
https://github.com/Hermann-SW/planar_graph_playground
And enhancement, new /txtdistdeg define allowing for edge lables, developed and tested in ps_done.ps:
https://gist.github.com/Hermann-SW/973b ... 86f85814c2

Code: Select all

() 0.3 390 270 vertex
12 60 (60 deg) 390 270 txtdistdeg
12 240 (240 deg) 390 270 txtdistdeg

txtdistdeg.png

txtdistdeg.png (6.06 KiB) Viewed 4880 times

The new end of node.convex_face_straight_line_drawing.js highlights the new features.
ps.header call remained the same, ternary expression got forced onto 5 lines by JSLint, and new "false" last argument tells ps.js not to output "showpage" at the end. That allows to add PostScript output after execution of "ps.straight_line_drawing()".

Code: Select all

    ps.header(selInd, slider, slider2, "");

    ps.straight_line_drawing(G, coords, pent, size, r, (
        (face.length === 5)
        ? face
        : []
    ), false);

Finally iteration over all edges determines source and target of each edge.
cx/cy is midpoint of the already drawn edge.
Simplest way to draw a small circle is to use /vertex define.
Then atan2() function determines the angle of the edge, which scaled from radian to degree shows the edge label.
Since "from_adjacency_list()" creates (undirected) graph where always edge source number is less than target vertex, text sits "on top" of edge in direction from smaller to higher number below.

Code: Select all

    forall_edges(G, function (e) {
        v = source(G, e);
        w = target(G, e);
        cx = (map(coords[0][v]) + map(coords[0][w])) / 2;
        cy = (map(coords[1][v]) + map(coords[1][w])) / 2;
        console.log("() 1 " + cx + " " + cy + " vertex");
        deg = Math.atan2(coords[1][w] - coords[1][v], coords[0][w] - coords[0][v]) * 180 / Math.PI;
        console.log("9 " + deg + " (" + e + ") " + cx + " " + cy + " txtdistdeg");
    });

    console.log("showpage");

Finally output of "showpage" is needed.

The output looks nice, here screenshot from evince 50% display:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ rjs node.convex_face_straight_line_drawing.js > x.ps
pi@pi400-64:~/planar_graph_playground $ evince x.ps 

postscript_edge_labels.png

postscript_edge_labels.png (50.09 KiB) Viewed 4880 times

P.S:
Face traversal is started with edge e=9:
https://github.com/Hermann-SW/planar_gr ... js#L25-L31

Unlike the browser display, the edge here is bottom right edge, not top right. Perhaps later vertical flip of Postscipt coordinate system makes sense to make displays match.

[HermannSW]

Unlike the browser display, the edge here is bottom right edge, not top right. Perhaps later vertical flip of Postscipt coordinate system makes sense to make displays match.

I did that, now edge 9 is top right edge:
https://github.com/Hermann-SW/planar_gr ... _drawingjs

ps_top_right_edge.png

ps_top_right_edge.png (36.92 KiB) Viewed 4772 times

Because "map()" is a defined function name in Python, I renamed it to "scr()" first (for "screen" coordinate conversion).
After above mentioned flipping of coordinates, two different functions are needed, "scrx()" and "scry()".

Today I posted on new "embedding_demo.py" in Python thread of this graph library. It made use of ported to Python ps.py and makes more sophisticated use of edge labels. The cenerated 2-page PostScript file cannot be viewed completely with "evince", so I switched to use GhostView (gv) for viewing Postscript files that I used in the early 90s for same reason, view code generated Postscript files.

For details how this new demo explains how "is_embedding()" works see the other posting ...
viewtopic.php?p=1997468#p1997468
... and the repo documentation:
https://github.com/Hermann-SW/planar_gr ... ing_demopy

Here is just the 2nd page, demonstration that "is_embedding()" tells that K4noemb graph is no embedding, since planar face traversal visits only 2 faces, while a planar embedding needs 2+n_edges(G)-n_vertices(G)=4 faces:
(the edge labels have the face number first, and letters in order of traversal of the face at the end)



I will port embedding_demo.py to JavaScript, since functional parity is goal from now on.


What definitely will come to this lib is testing planarity and computing an embedding for maximal planar graphs, which I created a technical report on back in 1993 as researcher at computer science department of University Bonn/Germany. That report has an algorithm for creating random maximal planar graphs as well, which will definitely be implemented here as well:
"A simple linear time algorithm for embedding maximal planar graphs"
https://stamm-wilbrandt.de/en/TR/IAI-TR-93-10.ps.pdf

[HermannSW]

I will port embedding_demo.py to JavaScript, since functional parity is goal from now on.

Before doing that, I created embedding_demo.2.py demonstrating output of the labels on the fly during planar_face_traversal(), without eface edge array.

Finallly I created new /parrow define for Postscript output, that allows to place colored vectors parallel to undirected edge in direction of edge traversal:

With that /parrow embedding_demo.3.py created 2-page Postscript file, with this screenshot of 1st page:




I just backported the three demos to JavaScript, and did an extra step with embedding_demo.3.js:
https://github.com/Hermann-SW/planar_gr ... ng_demo3js

The central code for colored vector output in embedding_demo.3.py looks like this:

embedding_demo.3.py.png

embedding_demo.3.py.png (49.47 KiB) Viewed 4693 times

This got straight directly ported to first similar code version of embedding_demo.3.js:

embedding_demo.3.js.png

embedding_demo.3.js.png (53.63 KiB) Viewed 4693 times

Finally inlining "planar_face_traversal()" visitor functions results in this only 11 line code, with layout fixated by JSLint:

embedding_demo.3.js.2.png

embedding_demo.3.js.2.png (39.37 KiB) Viewed 4693 times

/parrow is called with these arguments:

Code: Select all

%% len dist cr cg cb angle x1 y1
/parrow {

[HermannSW]

Nearly done with 5-bounded compaction code that allows for "from_adjacency_list()" to run with linear time+space.
Although the n*(n+1)/2 lookup table used sofar for the job of identifying the edge e when inserting it into vertex w with v<w would not need to be initialized, I think both JavaScript and Python do initialize and have runtime O(n²) for that.

The new method with linear space and time will allow to process 1,000,000 vertex planar graphs with no issues ... maximal planar embedding examples for 10, 100, ..., 10,000,000 vertices will be checked in soon.

The title says explicitely "and/or sphere surface", so 3D was always a target.

I would not have thought that I would see dodecahedron in analog 3D first
https://forum.prusa3d.com/forum/english ... ost-605278

20220429_021306.30%.jpg

20220429_021306.30%.jpg (39.48 KiB) Viewed 4625 times

Today I bough 900 toothpicks for 2.11$ in total, and only used 30 of them for the dodecahedron sofar — at least C60 (football) Buckminster fullerene is on 3Dprint todo list; just need to modify OpenSCAD file for 5-5-5 dodecahedron connector to sixty 5-6-6 connectors of C60.

[HermannSW]

With latest commits "from_adjacency_list()" does run in linear time and space, using new "compact5()" function converting a graph into a 5-bounded compaction (each edge is stored at only one of its vertices, vertex max_degree <= 5):
https://github.com/Hermann-SW/planar_gr ... #L111-L201

The 5-bounded compaction is used to provide this new constant time function, allowing to check whether vertices v and w are connected, and return the corresponding edge in case. Because maximal vertex degree in compaction is 5, at most 10 iterations can happen in both for loops:

Code: Select all

function compact5_find(C, v, w) {
    var ret = -1;
    forall_incident_edges(C, v, function (e) {
        if (opposite(C, v, e) === w) {
            ret = e;
        }
    });
    forall_incident_edges(C, w, function (e) {
        if (opposite(C, w, e) === v) {
            ret = e;
        }
    });
    return ret;
}

playground got new "graphs" directory, with the used sofar fullerenes C20, C30, ... C70, and maximal planar graph examples with 10, 100, ..., 100,000, 500,000 vertices (.a suffix for "adjacency list"):

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ls -l graphs/
total 67052
-rw-r--r-- 1 pi pi 43350443 Apr 29 19:47 1000000.a
-rw-r--r-- 1 pi pi  3736288 Apr 29 19:47 100000.a
-rw-r--r-- 1 pi pi   314213 Apr 29 19:47 10000.a
-rw-r--r-- 1 pi pi    25532 Apr 29 19:47 1000.a
-rw-r--r-- 1 pi pi     1957 Apr 29 19:47 100.a
-rw-r--r-- 1 pi pi      129 Apr 29 19:46 10.a
-rw-r--r-- 1 pi pi 21189957 Apr 29 20:30 500000.a
-rw-r--r-- 1 pi pi      196 Apr 29 20:40 C20.a
-rw-r--r-- 1 pi pi      306 Apr 29 20:40 C30.a
-rw-r--r-- 1 pi pi      416 Apr 29 20:41 C40.a
-rw-r--r-- 1 pi pi      526 Apr 29 20:41 C50.a
-rw-r--r-- 1 pi pi      636 Apr 29 20:41 C60.a
-rw-r--r-- 1 pi pi      746 Apr 29 20:42 C70.a
pi@pi400-64:~/planar_graph_playground $

The maximal planar graphs were created with 28yo code from the technical report, that code will be ported to playground later as well. I created all random maximal planar graphs with same random seed 12345:

Code: Select all

pi@pi400-64:~/maxplanar/work $ ./randomgraph 500000 -s 12345 -a -o 500000.a

-------------------------------------
malloc: 17   malloc-free: 0
pi@pi400-64:~/maxplanar/work $

Smallest example "graphs/10.a" is just a JSON array::

Code: Select all

[
[1,9,5,3,6,4,2]
,[0,2,4,6,7,9]
,[0,4,1]
,[0,5,8,6]
,[2,0,6,1]
,[3,0,9,7,8]
,[1,4,0,3,8,7]
,[1,6,8,5,9]
,[7,6,3,5]
,[0,1,7,5]
]

New demo "node_compact5.js" is used to test compaction code, as well as to demonstrate that Pi400 can easily deal with planar graphs of half a million vertices ("top" shows that 1.4GB resident and 1.9GB virtual memory get used). Variable "sel" stores the filename passed:

Code: Select all

#include "assert.js"
#include "fullerenes.js"
#include "undirected_graph.js"
#include "gauss-jordan.js"

var sel = (
    process.argv.length > 2
    ? process.argv[2]
    : "graphs/10.a"
);

var L;

Synchronous file read is used, to read selected file, parse as JSON and call new "from_adjacency_list()" with:

Code: Select all

var G;
const fs = require('fs');

try {
  const data = fs.readFileSync(sel, 'utf8');
  L = JSON.parse(data);
} catch (err) {
  console.error(err);
}

G = from_adjacency_list(L);

Finally it is verified that adjacency list vertex order is identical to created graph vertex oder.
And it is verified that the read graph is really an embedding:

Code: Select all

L.forEach(function (l, v) {
    l.forEach(function (w, j) {
        assert.assert(w === opposite(G, v, G.V[v][j]));
    });
});

console.log("identical vertex ordering in adjacency list and graph verified");

assert.assert(is_embedding(G));
console.log("is_embedding(" + sel + ") verified, has " + n_faces_planar(G) + " faces");

Processing 100,000 vertex graph takes 5.7 seconds:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ time rjs node_compact5.js graphs/100000.a 
identical vertex ordering in adjacency list and graph verified
is_embedding(graphs/100000.a) verified, has 199996 faces

real	0m5.729s
user	0m8.353s
sys	0m0.833s
pi@pi400-64:~/planar_graph_playground $ 

Half a million vertices take less than 28 seconds:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ time rjs node_compact5.js graphs/500000.a 
identical vertex ordering in adjacency list and graph verified
is_embedding(graphs/500000.a) verified, has 999996 faces

real	0m27.877s
user	0m38.887s
sys	0m3.525s
pi@pi400-64:~/planar_graph_playground $ 

Finally new "node.convex_face_straight_line_drawing.2.js" demo has argument processing and graph file reading. Instead of labeling the edges, here colored vectors are created in Postscript file:
https://github.com/Hermann-SW/planar_gr ... awing.2.js

Code: Select all

rjs node.convex_face_straight_line_drawing.2.js graphs/C20.a | gv -

C20_with_vectors.png

C20_with_vectors.png (36.54 KiB) Viewed 4560 times

P.S:
A bit long:

Code: Select all

const fs = require('fs');

try {
  const data = fs.readFileSync(sel, 'utf8');
  L = JSON.parse(data);
} catch (err) {
  console.error(err);
}

Just changed it to:

L = JSON.parse(require('fs').readFileSync(sel, 'utf8'));

[HermannSW]

I wanted to simplify visitor function calls, especially make them 1-line instead of 3-line because of the if and JSLint.
So I did replace all calls of this form:

Code: Select all

        if (pftv.next_vertex_edge) {
            pftv.next_vertex_edge(v, e);
        }

With just this form:

Code: Select all

        _f(pftv.next_vertex_edge)(v, e);

The tricky part was the definition of function "_f".
It was a hard fight to avoid JSLint "empty block" message by dummy assignment.
It was necessary to get rid of that warning, because it just stopped all other reporting:

Code: Select all

function _f(g) {
    return g || function (_i) {
        _i = _i;
    };
}

Function "compact5()" from yesterday got renamed "compact5_traversal()", and "compact5_traversal_visitor" can be passed when calling it, similar to "planar_face_traversal()". Here is central loop with some of the different visitor function calls:

compact5_traversal.visitor_functions.png

compact5_traversal.visitor_functions.png (26.65 KiB) Viewed 4480 times

Every planar graph has a 4-coloring, that is each vertex can get one of of 4 colors, with neighboring vertices never having same color. Since dual graph of a planar graph is planar as well, faces of a planar embedding can be colored with 4 colors, so that neighboring faces always have different colors. The proof of 4-color theorem took more than 100 years, and was finally done as a computer proof in the 1980s:
https://en.wikipedia.org/wiki/Four_colo ... em#History
I am not aware of any 4-coloing algorihm to determine a 4-coloring, the algorithms mentioned were used for the proof.

There is a linear time algorithm to determine a 5-coloring of a planar graph, which will be implemented later:
https://en.wikipedia.org/wiki/Five_colo ... _algorithm

I added the visitor concept, because now function "six-coloring(G)" determining a 6-coloring of planar embedding G is so small and beautiful:

six_coloring.pnghttps://github.com/Hermann-SW/planar_graph_playground/raw/main/res/max_planar_50_dual.6col.png

six_coloring.png (40.73 KiB) Viewed 4480 times

The vertices visited get just pushed on a stack in "begin_vertex".

After 5-bounded compaction has been determined, "end_traversal" gets invoked.
Vertices are "pop"ed from stack, and they have at most 5 neighbors in the 5-bounded compaction.
The forall_incident_edges loop collects all colors of v's neighbors in bitvector bs.
There are 2^6-1 possible 0/1 strings of length 6, and 111111 is not possible since v has at most 5 neighbors.
For the 62 other possible values, mc[] has the minimal free color to use.
Finally the coloring array "col" gets returned.


New demo "node.convex_face_straight_line_drawing.6coloring.js" shows how to fill faces with colors, and how to print face numbers (vertex numbers of dual graph) in centroid of faces vertices:
https://github.com/Hermann-SW/planar_gr ... oloring.js

C20 has vertex distances allowing to show vertex numbers:

Code: Select all

$ rjs node.convex_face_straight_line_drawing.6coloring.js graphs/C20.a | gv -

C60 has vertices too close together to show vertex numbers:

Code: Select all

rjs node.convex_face_straight_line_drawing.6coloring.js graphs/C60.a | gv -

New random maximal planar graph has too small faces (angles of less than 10° in convex face straight line drawing). Option "-dual" just computes dual graph of passed graph, and colors it:

Code: Select all

$ rjs node.convex_face_straight_line_drawing.6coloring.js graphs/50.a -dual | gv -

Nice PostScript files, and the 6-coloring is determined by a 23-line only function ...

[HermannSW]

Since last night I have functional and demo parity between JavaScript and Python planar graph playground.
Today I did need to change undirected_graph.js as well as undirected_graph.py quite often though.
Reason is, that for having same order of functions in those files, some functions had to be moved forward because of undirected_graph.hpp (C++ does not like function definitions after first use).

The 10 demos are listed in this posting:
viewtopic.php?p=2001531#p2001531
At end you can see screenshot of implementations of 6coloring demo code side-by-side for JavaScript|C++|Python.

[HermannSW]

I would not have thought that I would see dodecahedron in analog 3D first

dodecahedron.50%.jpg

dodecahedron.50%.jpg (23.81 KiB) Viewed 4071 times

I did buy 197mm long paper drinking straws, and created bigger dodecahedron with newly 3Dprinted connector first:
https://forum.prusa3d.com/forum/english ... ost-606710

Then I constructed the 5-6-6 connector needed for C60 fullerene (truncated icosahedron), and 3Dprinted it 60×.
Again analog first 3D view of C60, which is 92cm(!) high.
https://forum.prusa3d.com/forum/english ... ost-606910
Just added the math for determining fold angle of pentagon, which is planned to be part of auto folder for fullerenes that allow for in order to determine all vertices 3D coordinates:

20220514_190159.tw.part.25%.jpg

20220514_190159.tw.part.25%.jpg (111.98 KiB) Viewed 4071 times

[HermannSW]

I created "_" #define for c++_compact5.cpp demo that does timestamping:
viewtopic.php?t=332496&p=2003316#p2003316



Since I use C preprocessor for dealing with #include in "rjs" tool, I tried and got this working with nodejs as well as Python!
This is output for 100K vertex maximal planar graph:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ time rjs node_compact5.js graphs/100000.a 
identical vertex ordering in adjacency list and graph verified
is_embedding(graphs/100000.a) verified, has 199996 faces
compat5_traversal(G, {}) done
maxdegree(G) <=5 verified
               init: 0.001s
         parse2file: 0.177s
from_adjacency_list: 5.820s
  graph list verify: 0.354s
       is_embedding: 1.212s
 compact5_traversal: 0.666s
         max_degree: 0.007s
               exit: 0.009s
                sum: 8.246s

real	0m8.645s
user	0m12.223s
sys	0m1.059s
pi@pi400-64:~/planar_graph_playground $ 

And nodejs code looks very similar to C++ code wrt timestamping:
https://github.com/Hermann-SW/planar_gr ... ompact5.js

node_compact5.js.png

node_compact5.js.png (57.99 KiB) Viewed 3964 times

Like C++ code, the duration output goes to stderr and can be redirected:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ time rjs node_compact5.js graphs/100000.a 2>err
identical vertex ordering in adjacency list and graph verified
is_embedding(graphs/100000.a) verified, has 199996 faces
compat5_traversal(G, {}) done
maxdegree(G) <=5 verified

real	0m6.315s
user	0m9.034s
sys	0m0.836s
pi@pi400-64:~/planar_graph_playground $ 

In C++ demo "someDemo.cpp" includes the needed stuff from "someDemo.hpp".
".hpp" does not make sense for nodejs, so I chose ".sj" as suffix to include.
Does perhaps not look that nice, but does the job:
https://github.com/Hermann-SW/planar_gr ... ompact5.sj


P.S:
I used the timestamping duration reporting to improve C++ implementation by 33% today:
viewtopic.php?t=332496&p=2003316#p2003316
For now only node_compact5.js demo will use that, but that runs a lot of different graph code and allows to measure.


P.P.S:
Inter language time complexity comparisons are now possible (C++ | nodejs | Python):

[HermannSW]

Planar graphs are 4-colorable (algorithm unknown, only proof), and there is a linear time algorithm for 5-coloring a planar graph.
In previous posting simple linear time six_coloring algorithm implementation based on compact5_traversal was described:
viewtopic.php?t=333342&p=1998664#p1998664

three_6colorings.png.30%.jpg

three_6colorings.png.30%.jpg (31.03 KiB) Viewed 3848 times

The fullerenes I used as samples are cubic graphs (also 3-regular graphs, all vertices of degree 3).

According to Brooks' theorem every connected cubic graph other than the complete graph K4 can be colored with at most three colors.

https://en.wikipedia.org/wiki/Cubic_gra ... ndent_sets
Since maximal planar graphs are dual of cubic graphs, that means their faces can be 3-colored.
There is a linear time algorithm for computing such a 3-coloring:
https://en.wikipedia.org/wiki/Brooks%27 ... Algorithms

[HermannSW]

Just developing "node_fold_cubic.js", which should fold cubic (all vertices with degree 3) planar graphs (like fullerenes) with regular faces (all angles/lengths identical) if possible.
Implemented a small set of 3D vector functions, which will go into separate file later.
I have implemented loop that traverses a face, when started with vertices(edges) x-(s)-y-(t)-z moves around face and determines coordinates not yet computed vertices.
Fine for the initial hexagons, with computed angle needed to fit pentagon as third face.
No problem with single pentagon, only here together joining two hexagons — I will have to reevaluate the fold angle between both hexagons.
Nodejs code computes stuff, and finally writes OpenSCAD file with "console.log()":

fold_cubic_debug.OpenSCAD.png

fold_cubic_debug.OpenSCAD.png (53.54 KiB) Viewed 3750 times

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:

fold_cubic_debug.png

fold_cubic_debug.png (146.63 KiB) Viewed 3750 times

[HermannSW]

C++ directory had its Makefile, now NodeJS and Python directories got Makefile as well, with "clean", "clean_all", "verify" and "verify_all" targets. Details in this posting:
viewtopic.php?p=2007518#p2007518

pi@pi400-64:~/planar_graph_playground $ make verify_all
./rjs node_test.js > out
./rjs node_dual.js >> out
./rjs node.convex_face_straight_line_drawing.js >> out
./rjs embedding_demo.js >> out
./rjs embedding_demo.2.js >> out
./rjs embedding_demo.3.js >> out
./rjs node_compact5.js 2>err >> out
./rjs node.convex_face_straight_line_drawing.2.js >> out
./rjs node.convex_face_straight_line_drawing.6coloring.js >> out
./rjs node_6coloring.js graphs/10000.a 2>err >> out
diff out good
cd c++; make verify
make[1]: Entering directory '/home/pi/planar_graph_playground/c++'
./c++_test > out
./c++_dual >> out
./c++_compact5 2>err >> out
./c++_6coloring ../graphs/10000.a 2>err >> out
diff out good
make[1]: Leaving directory '/home/pi/planar_graph_playground/c++'
cd python; make verify
make[1]: Entering directory '/home/pi/planar_graph_playground/python'
./rpy python_test.py > out
./rpy python_dual.py >> out
./rpy python.convex_face_straight_line_drawing.py >> out
./rpy embedding_demo.py >> out
./rpy embedding_demo.2.py >> out
./rpy embedding_demo.3.py >> out
./rpy python_compact5.py 2>err >> out
./rpy python.convex_face_straight_line_drawing.2.py >> out
./rpy python.convex_face_straight_line_drawing.6coloring.py >> out
./rpy python_6coloring.py ../graphs/10000.a 2>err >> out
diff out good
make[1]: Leaving directory '/home/pi/planar_graph_playground/python'
echo

diff out good
diff python/out python/good
diff c++/out c++/good
python/norm python/good | diff - good
wc good
1800 6382 56588 good
pi@pi400-64:~/planar_graph_playground $

[HermannSW]

I have commited and submitted "anti_embedding.js" tool for finding the most non-planar edge ordering of incidence lists for a given planar graph:
https://github.com/Hermann-SW/planar_gr ... bedding.js

It contains some functions that will be moved into undirected_graph lib after C++ function+demo parity has reached.
There was function n_faces(G) before that computing the umber of faces f for a given number of edges e and vertices v from the Euler characteristic:

Code: Select all

f = e - v + 2

New function "chi(G)" computes the value chi for a given graph representation:
https://github.com/Hermann-SW/planar_gr ... .js#L8-L16

Code: Select all

function chi(G) {
    var nfaces = 0;

    planar_face_traversal(G, {begin_face: function () {
        nfaces += 1;
    }});

    return n_vertices(G) - n_edges(G) + nfaces;
}

Only for the graph being an embedding, Euler characteristic +2 will be returned.
https://en.wikipedia.org/wiki/Euler_characteristic

If I remove an edge from a given graph, there are two possibilities of how chi will change:

1. +1 if both "sides" of e belong to same face
2. -1 if both "sides" of e belong to different faces

If adding edge e back to G, these two things can happen.

If the positions in the incidence lists the edge will be reinserted to are

1. on same face, number of faces will increase by 1
2. otherwise number of faces will decrease by 1

So after removing and inserting an edge into its two vertices incidence lists, number of faces can only differ by -2, 0 or +2.

A maximal planar graph embedding has e = 3*v-6, and number of faces f = e - v + 2 = 2*v - 4.
Minimal number of faces for a worst adjacency lists is 2, that is (v-3) reductions (by -2).
This will result in chi value of 2 + (v-3)*(-2) = 8 - 2*v.

Here is maximal planar graph K5-e with worst edge ordering and chi = 8 - 2*5 = -2 (created with modified embedding_demo.3.js):

embedding_demo.K5me.worst.png

embedding_demo.K5me.worst.png (24.12 KiB) Viewed 3516 times

"anti_embedding.js" is just a random walk of simple edge remove and reinsert:
https://github.com/Hermann-SW/planar_gr ... js#L71-L83
"greedy" search would most times end in local minimum and not global minimum.
But using eg. Threshold Accepting (TA) or "Ruin&Recreate" are likely to find global minimum quicker and more reliably.
https://www.researchgate.net/publicatio ... _Principle
https://patents.google.com/patent/US641 ... d+recreate (public, expired patent with "same" text)

An edge is removed and inserted in incidence list of one of its vertices only.
And in that incidence list edge e and its next_incident_edge are just swapped by function "swap_edge(G, v, e)":
https://github.com/Hermann-SW/planar_gr ... js#L18-L28

I made use of PRNG (pseudo random number generator) MT19973, which guarantees same sequence of random 32bit values and ability to seed (no default JavaScript PRNG allows to seed):
viewtopic.php?t=335507

For maximal planar graphs the simple random search of 10000 "swap_edge()" calls reached 8-2*v easily for number of vertices 10, 50 and 100. I did store the adjacency lists representations in graphs directory:
https://github.com/Hermann-SW/planar_gr ... hs/10-12.a
https://github.com/Hermann-SW/planar_gr ... hs/50-92.a
https://github.com/Hermann-SW/planar_gr ... /100-192.a

Even with 800000 swap edge calls with many many different seeds the worst chi I was able to achieve was -390, so 8-2*200=-392 was not achieved yet.

Why did I create "anti_embedding.js"?
As first example of applying multi language+platform randomness to graph algorithms:
https://github.com/Hermann-SW/planar_gr ... js#L56-L62

Code: Select all

function rand_uint32() {
    return mt19937.genrand_int32();
}

function random_edge(G) {
    return rand_uint32() % n_edges(G);
}

And perhaps later for a new (simpler) graph planarity test (and embedding) algorithm, based on planar_face_traversal for determining chi, and then do "the right" edge remove and reinsert operations to reach embedding of the input graph with chi=2.


P.S:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./rjs anti_embedding.js graphs/100.a 10000 123456 
N= 10000 seed= 123456
2
0 [[1,42,43,96,9,63,68,46,64,84,71,23,3,99,77,6,4,2,67,93],[0,93,73,2,78,17,37,15,14,28,94,57,42],[0,4,78,1,73,67],[0,23,86,97,8,10,11,36,99],[2,0,6,72,60,15,37,78],[29,9,62,7,56,74,86],[4,0,77,99,36,81,66,21,22,82,49,7,20,15,72],[6,49,8,56,5,27,62,31,20],[7,49,19,13,11,10,3,97,69,56],[0,96,35,94,28,27,39,62,5,29,70,38,63],[3,8,11],[10,8,13,19,21,81,36,3],[16,50,59,53,89,25,88,64],[11,8,19],[1,15,20,27,28],[6,20,14,1,37,4,60,72],[12,64,46,79,80,41,38,45,32,52,29,48,18,91,61,40,24,50],[1,78,37],[23,26,40,91,16,48,29],[13,8,49,82,22,21,11],[7,31,55,27,14,15,6],[19,22,6,66,81,11],[6,21,19,82],[24,26,18,29,86,3,0,71,51,44,30],[50,16,40,26,23,30,92,75,54,51,25,83,59],[64,88,12,89,53,83,24,51,71,84],[24,40,18,23],[7,62,39,9,28,14,20,55,31],[27,9,94,1,14],[9,5,86,23,18,48,16,52,32,98,58,70],[24,23,44,92],[20,7,27,55],[29,52,16,45,33,58,98],[32,45,38,87,58],[47,44,51,54,75],[9,96,76,57,94],[3,11,81,6,99],[15,1,17,78,4],[16,41,63,9,70,58,87,33,45],[27,62,9],[18,26,24,16,61,91],[38,16,80,65,63],[43,0,1,57,76],[0,42,76,96],[30,23,51,34,47,85,92],[38,33,32,16],[16,64,0,68,79],[44,34,75,85],[18,16,29],[19,8,7,6,82],[16,24,59,12],[23,71,25,24,54,34,44],[29,16,32],[25,89,12,59,83],[34,51,24,75],[27,20,31],[5,7,8,69,90,74],[42,1,94,35,76],[29,98,32,33,87,38,70],[50,24,83,53,12],[4,72,15],[40,16,91],[9,39,27,7,5],[9,38,41,65,68,0],[25,84,0,46,16,12,88],[41,80,68,63],[21,6,81],[0,2,73,95,93],[46,0,63,65,80,79],[8,97,90,56],[9,29,58,38],[23,0,84,25,51],[6,15,60,4],[67,2,1,93,95],[86,5,56,90],[34,54,24,92,85,47],[42,57,35,96,43],[0,99,6],[17,1,2,4,37],[16,46,68,80],[79,68,65,41,16],[36,11,21,66,6],[22,19,49,6],[24,25,53,59],[0,64,25,71],[47,75,92,44],[3,23,29,5,74,90,97],[33,38,58],[25,64,12],[25,12,53],[69,97,86,74,56],[18,40,61,16],[24,30,44,85,75],[0,67,95,73,1],[35,57,1,28,9],[73,93,67],[43,76,35,9,0],[90,69,8,3,86],[32,58,29],[77,0,3,36,6]]
...
...
-192 [[64,67,1,43,46,96,68,23,9,84,71,3,6,42,4,99,2,93,77,63],[94,78,28,73,2,42,17,15,14,37,57,93,0],[67,78,1,0,73,4],[11,86,36,99,0,8,10,97,23],[72,2,0,15,6,37,60,78],[62,56,86,29,9,7,74],[4,7,77,72,82,99,81,36,22,49,21,20,15,0,66],[5,8,56,31,62,6,49,27,20],[97,19,7,3,56,10,11,69,49,13],[0,62,63,38,35,29,39,27,70,5,96,28,94],[8,11,3],[8,36,13,10,3,21,19,81],[53,89,25,50,64,16,88,59],[8,11,19],[28,27,1,15,20],[6,1,20,4,72,37,14,60],[80,29,41,79,32,38,61,24,64,45,50,40,52,91,18,48,12,46],[1,78,37],[29,23,48,16,40,91,26],[49,22,82,21,11,8,13],[6,7,15,55,31,27,14],[66,81,22,6,19,11],[82,21,6,19],[30,18,3,0,44,29,26,86,51,71,24],[51,59,75,26,16,40,92,54,50,30,83,23,25],[24,71,53,84,88,83,64,12,89,51],[40,23,24,18],[55,7,62,20,14,28,31,39,9],[9,27,1,94,14],[32,52,16,18,98,70,9,23,48,58,5,86],[23,44,24,92],[55,27,7,20],[52,16,98,33,58,29,45],[38,58,32,45,87],[54,44,75,47,51],[57,96,9,76,94],[81,99,11,3,6],[15,78,17,1,4],[45,9,58,63,16,87,41,33,70],[9,27,62],[24,61,91,26,18,16],[16,80,65,63,38],[76,57,43,1,0],[76,96,42,0],[51,23,85,34,47,92,30],[38,33,16,32],[16,79,64,0,68],[85,34,75,44],[29,18,16],[6,7,19,82,8],[12,16,59,24],[54,71,44,34,24,23,25],[32,16,29],[59,25,12,89,83],[75,24,34,51],[27,20,31],[74,5,69,7,90,8],[1,94,42,76,35],[29,38,98,87,33,70,32],[50,24,83,53,12],[15,4,72],[91,16,40],[5,39,9,27,7],[38,65,41,9,68,0],[88,25,16,12,84,0,46],[41,80,63,68],[81,6,21],[2,73,93,95,0],[63,65,46,79,0,80],[56,97,8,90],[38,29,58,9],[0,23,25,51,84],[6,15,4,60],[95,67,93,2,1],[86,90,56,5],[92,85,24,47,54,34],[96,42,43,57,35],[6,99,0],[37,1,17,4,2],[80,46,16,68],[16,79,68,41,65],[21,11,6,36,66],[22,6,49,19],[25,24,53,59],[25,71,64,0],[92,75,47,44],[29,74,5,90,97,3,23],[38,33,58],[64,12,25],[12,25,53],[86,69,74,56,97],[61,18,40,16],[75,85,24,44,30],[1,67,95,73,0],[28,9,35,1,57],[73,93,67],[76,9,43,0,35],[90,8,69,3,86],[58,29,32],[36,3,6,77,0]]
pi@pi400-64:~/planar_graph_playground $ 

P.P.S:
So the idea is, that applying "planar_face_traversal()" to non-embeddings can make sense as well (other than just checking whether a given graph is an embedding):
https://github.com/Hermann-SW/planar_gr ... #L371-L379

[HermannSW]

Interesting, embedding_demo.2.js did embed complete graph on 4 vertices, with f = 6 - 4 + 2 = 4 faces.
Now removing edge between vertices 0 and 3, we get an embedding with 3 faces.
Now further modifying the incidence list of one of the two vertices of degree 3 we get a single face non-embedding!
(similar to "single side" Möbius strip)

K4-e.single_face.png

K4-e.single_face.png (22.38 KiB) Viewed 3257 times

Starting with edge from 0 to 1 (0_a) you can follow 0_b, 0_c, ... 0_j and then 0_a again when traversing the single face.