C/C++(JavaScript) | planar graphs | draw fullerene in 2D/3D

[HermannSW]

In the 90s as researcher at University of Bonn/Germany computer science department I developed, implemented and published quite some planar graph algorithms, in C at that time with my own libraries, with PostScript and X11 as output:
https://stamm-wilbrandt.de/en/twitter/maxplana.pdf

Here is embedding and (straight line) drawing diagram from page 12:

embed_and_draw_maxplanar_graph.png

embed_and_draw_maxplanar_graph.png (70.91 KiB) Viewed 4362 times

Every planar graph has a straight line drawing like the one shown (graph edges are straight lines between the vertices).

I installed boost graph library:

Code: Select all

sudo apt install libboost-graph-dev libboost-doc

Its function "chrobak_payne_straight_line_drawing()" embeds a planar graph with n vertices into the plane as straight line drawing, with integer coordinates (2n-4)×(n-2):
https://www.boost.org/doc/libs/1_74_0/l ... ersFormula

I did copy examples directory under $HOME:

Code: Select all

mkdir ~/boost
cp -r /usr/share/doc/libboost1.74-doc/examples/libs/graph/example ~/boost

Straight line drawing example does what I am interested in:

Code: Select all

pi@pi400-64:~/boost/example $ rm a.out 
pi@pi400-64:~/boost/example $ g++ straight_line_drawing.cpp 
pi@pi400-64:~/boost/example $ ./a.out 
The straight line drawing is: 
0 -> (0, 0)
1 -> (10, 0)
2 -> (5, 4)
3 -> (5, 5)
4 -> (2, 1)
5 -> (3, 2)
6 -> (4, 3)
Is a plane drawing.
pi@pi400-64:~/boost/example $ 

straight_line_freecad.png

straight_line_freecad.png (11.16 KiB) Viewed 4362 times

Graph was hard coded in sample code:

Code: Select all

    // Create the graph - a maximal planar graph on 7 vertices. The functions
    // planar_canonical_ordering and chrobak_payne_straight_line_drawing both
    // require a maximal planar graph. If you start with a graph that isn't
    // maximal planar (or you're not sure), you can use the functions
    // make_connected, make_biconnected_planar, and make_maximal planar in
    // sequence to add a set of edges to any undirected planar graph to make it maximal planar.
    graph g(7);
    add_edge(0, 1, g);
    add_edge(1, 2, g);
    add_edge(2, 3, g);
    add_edge(3, 0, g);

Code: Select all

    add_edge(3, 4, g);
    add_edge(4, 5, g);
    add_edge(5, 6, g);
    add_edge(6, 3, g);
    add_edge(0, 4, g);
    add_edge(1, 3, g);
    add_edge(3, 5, g);
    add_edge(2, 6, g);
    add_edge(1, 4, g);
    add_edge(1, 5, g);
    add_edge(1, 6, g);

OK, that was planar graphs and boost library.

Combinatorial object server allows to generate fullerenes:
http://www.combos.org/fullgen

Generate different types of fullerenes. A fullerene is a plane graph whose faces are all pentagons and hexagons. This is a website interface to the program fullgen, written by Gunnar Brinkmann. The default graph format are adjacency lists, where the neighbors of each vertex are listed in clockwise (cw) order around the vertex in the embedding of the graph.

fulgen.c can be downloaded and build with just "make":
http://users.cecs.anu.edu.au/~bdm/plantri/

Code: Select all

pi@pi400-64:~/plantri52 $ ./fullgen 60 ipr code 6 stdout
Time for generating the patches: 0.0 seconds 
>>writegraph3d planar <<
 1  0 0 0   18 19  2
 2  0 0 0    1  3 40
 3  0 0 0    2 32  4
 4  0 0 0    3  5 41
 5  0 0 0    4 30  6
 6  0 0 0    5  7 43
 7  0 0 0    6 29  8
 8  0 0 0    7  9 45
 9  0 0 0    8 27 10
10  0 0 0    9 11 46
11  0 0 0   10 25 12
12  0 0 0   11 13 48
13  0 0 0   12 24 14
14  0 0 0   13 15 50
15  0 0 0   14 22 16
16  0 0 0   15 17 51
17  0 0 0   16 20 18
18  0 0 0   17  1 53
19  0 0 0    1 20 33
20  0 0 0   19 17 21
21  0 0 0   20 22 35
22  0 0 0   21 15 23
23  0 0 0   22 24 36
24  0 0 0   23 13 25
25  0 0 0   24 11 26
26  0 0 0   25 27 37
27  0 0 0   26  9 28
28  0 0 0   27 29 38
29  0 0 0   28  7 30
30  0 0 0   29  5 31
31  0 0 0   30 32 39
32  0 0 0   31  3 33
33  0 0 0   32 19 34
34  0 0 0   33 35 39
35  0 0 0   34 21 36
36  0 0 0   35 23 37
37  0 0 0   36 26 38
38  0 0 0   37 28 39
39  0 0 0   38 31 34
40  0 0 0    2 41 54
41  0 0 0   40  4 42
42  0 0 0   41 43 56
43  0 0 0   42  6 44
44  0 0 0   43 45 57
45  0 0 0   44  8 46
46  0 0 0   45 10 47
47  0 0 0   46 48 58
48  0 0 0   47 12 49
49  0 0 0   48 50 59
50  0 0 0   49 14 51
51  0 0 0   50 16 52
52  0 0 0   51 53 60
53  0 0 0   52 18 54
54  0 0 0   53 40 55
55  0 0 0   54 56 60
56  0 0 0   55 42 57
57  0 0 0   56 44 58
58  0 0 0   57 47 59
59  0 0 0   58 49 60
60  0 0 0   59 52 55
0
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: 1783
BBLIST: number of items in list: 105  number of patches: 1122

Generated 1 maps on 60 vertices -- reduced to 1 non-isomorphic maps. 

Total generation time: 0.0 seconds 
end of program
pi@pi400-64:~/plantri52 $

This is drawing with corresponding clockwise planar embedding from website:

c20.png

c20.png (73.32 KiB) Viewed 4362 times

fulgen.c creates embeddings of fullerenes, so only "chrobak_payne_straight_line_drawing()" is needed to determine integer coordinates.

Todos:

1. glue code for "chrobak_payne_straight_line_drawing()" and fulgen.c
2. 2D graphic output (PostScript, X11, HTML, ...)
3. determine 3D coordinates on unit sphere by eg. polar projection from planar drawing
4. transform 3D coordinates to equal length edges
5. display 3D somehow, ideally with 3D rotation capability

[HermannSW]

I never had looked into code with that dense use of C++ templates like boost library.
The graph examples are good, but there is a steep learning curve for me.

I replaced planar_face_traversal.cpp hardcoded example graph by code to read fulgen.c output, only small diff. fulgen.cpp has lowest vertex number 1, whereas boost graph library has 0. The new code decreases each vertex number by 1 while creating boost graph g:
https://gist.github.com/Hermann-SW/1131 ... /revisions

Below you can see planar face traversal of the 12 pentagons and 60/2-10=20 hexagons of C60 Buckminsterfullerene:
https://en.wikipedia.org/wiki/Buckminsterfullerene

pi@pi400-64:~/boost/example $ ~/plantri52/fullgen 60 ipr code 6 stdout 2>/dev/null | ./planar_face_traversal
Input graph is planar

Vertices on the faces:
New face: 0 17 16 19 18
New face: 17 0 1 39 53 52
New face: 0 18 32 31 2 1
New face: 1 2 3 40 39
New face: 2 31 30 29 4 3
New face: 3 4 5 42 41 40
New face: 4 29 28 6 5
New face: 5 6 7 44 43 42
New face: 6 28 27 26 8 7
New face: 7 8 9 45 44
New face: 8 26 25 24 10 9
New face: 9 10 11 47 46 45
New face: 10 24 23 12 11
New face: 11 12 13 49 48 47
New face: 12 23 22 21 14 13
New face: 13 14 15 50 49
New face: 14 21 20 19 16 15
New face: 15 16 17 52 51 50
New face: 18 19 20 34 33 32
New face: 20 21 22 35 34
New face: 22 23 24 25 36 35
New face: 25 26 27 37 36
New face: 27 28 29 30 38 37
New face: 30 31 32 33 38
New face: 33 34 35 36 37 38
New face: 39 40 41 55 54 53
New face: 41 42 43 56 55
New face: 43 44 45 46 57 56
New face: 46 47 48 58 57
New face: 48 49 50 51 59 58
New face: 51 52 53 54 59
New face: 54 55 56 57 58 59

Edges on the faces:
New face: (0,17) (17,16) (16,19) (19,18) (0,18)
New face: (0,17) (0,1) (1,39) (39,53) (52,53) (17,52)
New face: (0,18) (18,32) (31,32) (2,31) (2,1) (0,1)
New face: (1,2) (3,2) (3,40) (39,40) (1,39)
New face: (2,31) (31,30) (30,29) (4,29) (4,3) (3,2)
New face: (3,4) (5,4) (5,42) (41,42) (40,41) (3,40)
New face: (4,29) (29,28) (6,28) (6,5) (5,4)
New face: (5,6) (7,6) (7,44) (43,44) (42,43) (5,42)
New face: (6,28) (28,27) (27,26) (8,26) (8,7) (7,6)
New face: (7,8) (9,8) (9,45) (44,45) (7,44)
New face: (8,26) (26,25) (25,24) (10,24) (10,9) (9,8)
New face: (9,10) (11,10) (11,47) (46,47) (45,46) (9,45)
New face: (10,24) (24,23) (12,23) (12,11) (11,10)
New face: (11,12) (13,12) (13,49) (48,49) (47,48) (11,47)
New face: (12,23) (23,22) (22,21) (14,21) (14,13) (13,12)
New face: (13,14) (15,14) (15,50) (49,50) (13,49)
New face: (14,21) (21,20) (20,19) (16,19) (16,15) (15,14)
New face: (15,16) (17,16) (17,52) (51,52) (50,51) (15,50)
New face: (18,19) (20,19) (20,34) (33,34) (32,33) (18,32)
New face: (20,21) (22,21) (22,35) (34,35) (20,34)
New face: (22,23) (24,23) (25,24) (25,36) (35,36) (22,35)
New face: (25,26) (27,26) (27,37) (36,37) (25,36)
New face: (27,28) (29,28) (30,29) (30,38) (37,38) (27,37)
New face: (30,31) (31,32) (32,33) (33,38) (30,38)
New face: (33,34) (34,35) (35,36) (36,37) (37,38) (33,38)
New face: (39,40) (40,41) (41,55) (54,55) (53,54) (39,53)
New face: (41,42) (42,43) (43,56) (55,56) (41,55)
New face: (43,44) (44,45) (45,46) (46,57) (56,57) (43,56)
New face: (46,47) (47,48) (48,58) (57,58) (46,57)
New face: (48,49) (49,50) (50,51) (51,59) (58,59) (48,58)
New face: (51,52) (52,53) (53,54) (54,59) (51,59)
New face: (54,55) (55,56) (56,57) (57,58) (58,59) (54,59)
pi@pi400-64:~/boost/example $

Next for this example is to learn about 3D coordinates in boost and compute coordinates on unit sphere. I will start with one face, calculate coordinates on unit sphere at same minimal y-coordinate for the face, and then do a face wise breadth first search and determine successively all the other vertex coordinate.

Finally the computed 3D coordinates will be used to display the unit sphere embedding in web browser. The 2D coordinates C20 fullerene diagram from last posting is SVG on this page, do "View page source" for details:
http://www.combos.org/fullgen


P.S:
Forgot to mention that I found nice browser 3D rotation I know from freecad:
https://www.mattkeeter.com/projects/rotation/#turntable

Peek_2022-04-05_23-17.gif

Peek_2022-04-05_23-17.gif (207.35 KiB) Viewed 4269 times

[HermannSW]

I wanted to see browser interaction and switched programming language to JavaScript for that.

In the early 90s I met Goos Kant on a conference, and he did snail mail me his Phd thesis "Algorithms for Drawing Planar Graphs". Yesterday I found the thesis in basement, and I was interested in chapter "9.2 Convex Drawings" on page 117

20220406_172558.20%.jpg

20220406_172558.20%.jpg (58.74 KiB) Viewed 4198 times

because drawing each face convex in 2D looks nicer than the graphs I had shown.
The graph of C20 can be made convex face drawing by moving vertices 16, 10 and 12 slightly:



I was interested to get things working, and while Tutte's algorithm by solving system of linear equations can be done in O(n*log(n)) for planar graph sparse matrices, I used simple nodejs Gauss-Jordan elimination solver working in O(n³) I found here (modified it slightly to be usable in browser):
https://github.com/lovasoa/linear-solve ... -jordan.js

I used adjacency list representation as array of arrays, and created simple JavaScript graph library.
Function nextAdjacentEdge() is running in O(deg(w)) and not in constant time as possible with C pointer structures:

Code: Select all

function nextAdjacentEdge(G, v, w){
  j=G[w].indexOf(v);
  assert(j!=-1);
  return G[w][(j+1)%3];
}

Not a big problem here, since fullerenes have degree 3 for all vertices, so runtime is O(1) for all graphs with constant maximal vertex degree (general planar graphs can have vertex degree n-1 for n vertices).

In the 90s I created a C graph library based on "#define"s.
JavaScript is much cleaner than this, in passing anonymous functions.
This is nice implementation of iteration over all edges of a graph G, executing function f() for each:

Code: Select all

function forall_edges(G, f){
  for(v=0; v<G.length; ++v){
    G[v].forEach(function(w){
      if (v<w)
        f(v,w);
    });
  }
}

I used this to draw all SVG lines with this code snippet:

Code: Select all

  forall_edges(G, function(v, w){
    cx=l/2+(l/2-r)*sx[v];
    cy=l/2+(l/2-r)*sy[v];
    dx=l/2+(l/2-r)*sx[w];
    dy=l/2+(l/2-r)*sy[w];
    document.write('<line class="l" x1="'+cx+'" y1="'+cy+'" x2="'+dx+'" y2="'+dy+'"></line>');
  })

I will publish repo when I have done more cleanup of code, here is complete Tutte's algorithm to determine x- and y-coordinates for graph "G" with outer face vertices in array "f":

Code: Select all

function tutte(G, f){
  n=G.length;
  X=zero(n, n);
  Y=zero(n, n);
  x=zero(n, 1);
  y=zero(n, 1);
  a=0;
  slider = document.getElementById("myRange").value/100.0;
  d=slider*2*Math.PI/f.length;

Code: Select all

  f.forEach(function(v){
    x[v]=Math.sin(a);
    y[v]=-Math.cos(a);
    a+=d;
  });
  for(v=0; v<n; ++v) {
    if (f.includes(v)) {
      X[v][v]=1;
      Y[v][v]=1;
    } else {

Code: Select all

      X[v][v]=-1;
      Y[v][v]=-1;
      G[v].forEach(function(w){
        X[v][w]=1.0/G[v].length;
        Y[v][w]=1.0/G[v].length;
      });
    }
  }
  return [solve(X,x),solve(Y,y)];
}

Just as sneak preview, here a "peek" screenrecorder animated .gif showing selecting different fullerenes created with fullgen.c, changing size of SVG, clicking on two adjacent vertices and redraw with that edge being top right in drawing, and finally modifying scale value for seeing Tutte's algorithm works as well when vertices on outer face are not distributed evenly!
(animated .gif size is 512KB, too big for 250KB forum attachment limit)

[HermannSW]

Wow, this was a ride.

I found a cute way of making linear-solve Node.JS module usable in browser with minimal changes (change 1 line, delete 5):

module2browser.png

module2browser.png (46.17 KiB) Viewed 4115 times

Then I added n×m zero matrix creation function to modified gauss-jordan.js.

I did copy out "assert()" function into assert.js, worked a lot on undirected_graph.js and tutte.js.
Finally I JSlinted the last three files.
I created planar_graph_playground repo and uploaded the files.
Prior t.html now became index.html and was commited as well.
Finally README.md was commited:
https://github.com/Hermann-SW/planar_gr ... playground

Then I learned that rawgit.io is closed for new repos, and that I can create my Github Page for hosting repos as submodules:

github_pages.submodule.png

github_pages.submodule.png (67.18 KiB) Viewed 4115 times

Now demo application is public, and you can play with it in your browser of choice:
https://hermann-sw.github.io/planar_graph_playground/


This is initial work, so much changes to be made I know of, and even more I don't know of yet
"traverse_face(Emb, v, w)" that determines vertices of outer face in embedding "Emb" with edge v--w top right edge now looks like this (JSlint forced me to many changes, move all variables to top, prefix with var, so many spaces had to be inserted, indentation by 4 spaces, ...):

Code: Select all

function traverse_face(Emb, v, w) {
    var a;
    var o = v;
    var face = [o];
    while (w !== o) {
        face.push(w);
        a = nextAdjacentEdge(Emb, v, w);
        v = w;
        w = a;
    }
    return face;
}

I will implement "traverse_all_faces(G)", and compute number of faces F from the traversal. V = n_vertices(G) and E = n_edges(G) allow to check whether G is a planar embedding or not then! For planar graphs always "V-F+E==2", and if something different is computed by "V-F+E", that is proof that G is not a planar embedding. For that I need a boolean edge array, with two entries for each edge (for traversal from both sides). It will be created easily with "linear.fill(n_edges(G), 2, false)".


In case you find any bugs/problems please create an issue on github repo, or reply here.


P.S:
In case you know "Graphviz", you might find my "GraphvizFiddle" tool that works in browser interesting as well (Graphviz C code was cross compiled with Emscripten, and used from GraphvizFiddle JavaScript and HTML):
https://stamm-wilbrandt.de/GraphvizFiddle/

[HermannSW]

So many changes and new code, many commits.

I modified assert.js module like, and made it alert the assertion text before throwing it which will make it end up in console log and terminate script execution. The message contains file and line number of the assertion failure like C/C++ assert does:
https://github.com/Hermann-SW/planar_gr ... /assert.js


I implemented face traversal function "pentagons()" which returns the 12 pentagons of a fullerene. Code to determine the pentagon that corresponds to the outer face and remove it was not that nice, but does the job ("equality" of arrays having same 5 elements):
https://github.com/Hermann-SW/planar_gr ... ml#L55-L76
The 11 pentagons get now filled with cyan for easy spotting

In case vertex circles are too close together, I did set radius to third of minimal edge length and skipped drawing text:
https://github.com/Hermann-SW/planar_gr ... ml#L61-L77

Before discussing new function "is_embedding(G)" that gets asserted in "tutte.convex_face_coordinates()" because that algorithm requires an embedding to be passed, here short 287KB animated .gif showing new pentagon coloring and text draw and radius determine features. Of course you can play with published tool as well:
https://hermann-sw.github.io/planar_gra ... index.html



Now discussion of "is_embedding()":
https://github.com/Hermann-SW/planar_gr ... js#L59-L89


Just representing graph as adjacency list only as done until now makes it difficult to work with edge_arrays, since there are no edges like in a pointer graph representation. Since planar_graph_playground tool uses O(n³) time algorithm for determining n vertex embedding coordinates, I have no problems to spend O(n²) time and space for creating the needed mapping of edge(u,v) to representation e as number with n×n matrix vw2e:

is_embedding.1.png

is_embedding.1.png (19.11 KiB) Viewed 4030 times

The bottom part does initialize the matrix as needed.

Here the top part traverses all edges in both directions, and if encountering an edge that was not visited before, it marks all edges of the corresponding face as visited and increases number of faces by 1:

is_embedding.2.png

is_embedding.2.png (23.46 KiB) Viewed 4030 times

Finally the last statement makes use of the Euler characteristic of planar graphs (2) in order to return true/false:
https://en.wikipedia.org/wiki/Euler_cha ... #Polyhedra

[HermannSW]

I want to go to drawing fullerenes on sphere (3D) with stereographic projection:
https://en.wikipedia.org/wiki/Stereographic_projection

There is a bijection for all points on the (infinite) plane and sphere points without north pole:



So I searched for drawing sphere (still JavaScript) code and found @fpfaffendorf's "javascript-sphere" repo.
I forked it, reduced number of points drawn, and horizontal/vertical number of segments.
Finally I added mousemove event handling:
https://github.com/Hermann-SW/javascript-sphere

I published tool on github.io for direct rotating sphere with mouse (full 360° rotation horizontally and vertically):
https://hermann-sw.github.io/javascript-sphere/

javascript-sphere.png

javascript-sphere.png (12.13 KiB) Viewed 3972 times

The demo has "solid = true", so no points on invisible half sphere will be shown.
Just try to draw straight line between two points on sphere in white in addition.
When that will work, I will extend to 6 straight lines and draw regular tetrahedron (with "solid=false") in order to evaluate how this looks when rotating sphere in 3D. I found the x/y/z coordinates of 4 tetrahedron points on unit sphere here:
https://en.wikipedia.org/wiki/Tetrahedr ... etrahedron

[HermannSW]

I completed what I described, but had difficulties to understand what was drawn on display. So I switched default mode to "solid = true", where points not visible in case of a solid sphere are drawn in dark grey:
https://github.com/Hermann-SW/javascript-sphere

For me moving mouse and longitude and latitude lines allows to better see the 3D structure of tetrahedron.
You can just play with:
https://hermann-sw.github.io/javascript-sphere/

sphere_tetrahedron.up.png

sphere_tetrahedron.up.png (23.49 KiB) Viewed 3920 times

When mouse button is down, all longitude and latitude points with "z < 0" are not drawn anymore.
The tetrahedron is always drawn completely, with white straight lines.

sphere_tetrahedron.down.png

sphere_tetrahedron.down.png (25.2 KiB) Viewed 3920 times

So now I have good simple basis for 3D positioning input and with Orthographic Projection Matrix technique a good way to draw on the sphere. When filling all fullerene faces that are visible from front with a solid color, this would give a "solid" fullerene view.

[HermannSW]

Integrating 3D sphere view to planar_graph_playground got sidetracked.

First by using graph library for solving "cuboid surface shortest path problem", after I constructed a cube sample with start and target on opposite faces, where the shortest path passes through two more faces:
https://twitter.com/HermannSW/status/15 ... 5390921729

I will create a new thread under "General Programming Discussion" on that, and comment on the huge number of changes to the JavaScript graph representation (eg. the added edge representation for more efficiency, and mimic boost graph library "planar face traversal visitor") which is a bit off topic for this sub forum. Has been published already, but does not do much yet besides display of shortest path passing 4 faces:
https://hermann-sw.github.io/planar_gra ... rtest_path

cuboid_surface_shortest_path.1.png

cuboid_surface_shortest_path.1.png (26.45 KiB) Viewed 3833 times

New "convex face planar straight line drawing" tool has SVG area surrounded by blue square, is published for playing with:
https://hermann-sw.github.io/planar_graph_playground/

convex_face_straight_line_drawing.1.png

convex_face_straight_line_drawing.1.png (84.18 KiB) Viewed 3833 times

I mentioned the added "edge" representation already, which made selection of the edge for drawing top right edge much easier, just one click on the edge. As the new message displayed (in previous screenshot) tells, the edge vertex closer to mouse position becomes top vertex (I had to use event.layerX/Y instead event.x/y):



There is another reason why I showed the SVG boundary with blue square, now the outer face gets filled as well in case it is a pentagon.
So now always 12 pentagon faces get filled for fullerenes:

convex_face_straight_line_drawing.2.png

convex_face_straight_line_drawing.2.png (65.14 KiB) Viewed 3833 times

[HermannSW]

I mentioned drawing planar graph on a sphere surface in 3D before.

Yesterday I wanted to create a tetrahedron model in FreeCAD with cylinder edges.
I failed, but was successful with OpenSCAD.
Today I learned from @Torsten_Paul on twitter about the (magic for me) hull() function.
I published new script that reduced to 8 lines only with Torsten's trick (and the nice for() function):
https://gist.github.com/Hermann-SW/3939 ... 21e4624467

Below is the result of this small script:

Code: Select all

v=[[sqrt(8/9),0,-1/3],[-sqrt(2/9),sqrt(2/3),-1/3],[-sqrt(2/9),-sqrt(2/3),-1/3],[0,0,1]];
R=40;
r=1;
$fn=25;
for (a = [0:2], b = [a + 1:3]) hull() {
  translate(R*v[a]) sphere(r);
  translate(R*v[b]) sphere(r);
}

So why do I post about this here?
Line 1 of script 3D coordinates are on unit sphere (with radius 1 around [0,0,0]) from Wikipedia:
https://en.wikipedia.org/wiki/Tetrahedr ... etrahedron

Code: Select all

translate(R*v[...

in lines 6 and 7 moves the vertices to surface of sphere with radius R.

The hull() { ... } call just "draws" one edge in 3D.
So I will use this to output OpenSCAD file for a planar graph with unit sphere coordinates by iterating over all (at most 3n-6 for planar graph with n vertices) edges with "forall_edges(G, function(e) { ... })" for outputting edge e with "hull()" between vertices "source(G, e)" and "target(G, e)".

Overlaying the sphere with radius r used in hull() with another sphere with bigger radius will make vertices more visible if needed, eg. by appending these lines to above script:

Code: Select all

for(a = [0:3]) {
  translate(R*v[a]) sphere(2.5*r);  
}

tetrahedron_with_cylinder_edges.scad.thick_vertices.png

tetrahedron_with_cylinder_edges.scad.thick_vertices.png (26.97 KiB) Viewed 3758 times

After writing that file, running "openscad filename" will allow for rotating, moving and zooming without writing any code!

[HermannSW]

Todos:

1. glue code for "chrobak_payne_straight_line_drawing()" and fulgen.c
2. 2D graphic output (PostScript, X11, HTML, ...)
3. determine 3D coordinates on unit sphere by eg. polar projection from planar drawing
4. transform 3D coordinates to equal length edges
5. display 3D somehow, ideally with 3D rotation capability

Time to revisit 1st posting todo list.

1) is done by not directly executing fulgen.c each time, but by adding C20, C30, ..., C70 fullerene exammple adjacency lists generated with fulgen.c into fullerenes.js

2) done with SVG output into browser:
https://hermann-sw.github.io/planar_graph_playground/

5) described yesterday, creating OpenSCAD file and viewing/rotating/zooming/... in OpenSCAD:

tetrahedron_with_cylinder_edges.scad.thick_vertices.33%.png

tetrahedron_with_cylinder_edges.scad.thick_vertices.33%.png (21.09 KiB) Viewed 3710 times

3+4) I had the fallacy that fullerene equal edge length embedding into 3D would always lead to vertex coordinates on unit sphere. This is true for C20 (dodecahedron) and likely C60 ("football" Buckminster fullerene). But it is definitely false for eg. C40:

C40_fallacy.png

C40_fallacy.png (52.24 KiB) Viewed 3710 times

Reason is that for regular pentagon and regular hexagon the inside angles are (5-2)*180°/5=108° and (6-2)*180°/6=120°. Now look at leftmost inner vertex of C40. It is surrounded by 3 hexagons (white). And 3*120°=360° is full rotation, so the three hexagons are on same plane in folding of C40 into 3D. So that vertex will definitely be "inside" unit sphere, with its distance to origin being less than 1.

Next todo will be to take a fullerene graph embedding, determine its dual graph (vertex for each face, edges 1:1 mapping between both graphs, vertices connected if and only if corresponding faces are neighbors), and then do a traversal of not yet visited vertices of dual graph (faces of original graph) by Depth first search, breadth first search or somehow else, start with initial plane embedding of face corresponding to start vertex of dual graph in 3D, and then fold regular faces determining of not yet determined 3D vertex coordinates of the folded faces. Finally each vertex should have received a 3D coordinate, such that each face's vertices lie in a 2D plane (like here for regular dodecahedron from Wikipedia):

[HermannSW]

I created new thread "JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface" under "Other programming languages" forum. Lots of information on creating dual graph, and how "dual_graph()" started as 25 line function, and finally ended as only 12 line function doing the job. What is relevant here is, that since doday PostScript graph drawing output can be created as well with "JavaScript plus C includes" nodejs tool "rjs" executing "node.convex_face_straight_line_drawing.js":
viewtopic.php?p=1995804#p1995804

Here is C30.ps:
https://github.com/Hermann-SW/planar_gr ... ain/C30.ps

In C30.ps top there are quite tricky /vertex and /poly defines, discussed here:
viewtopic.php?p=1995804#p1995658
:

20220421_155813.part.16pc.jpg

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

[HermannSW]

After I ported JavaScript graph library to Python, and developed more and more functionality, the idea came up in my mind to port to C++ as well. The first reason was to use std::vector resizable arrays. But now I learned that compiling with "-std=c++11" gives me C++ lambdas!

Python lambdas are a bit less powerful than JavaScript anonymous functions.
But C++ lambdas are powerful.

First I had to get the basics right in C++ for design goal "graph library code should look nearly identical for all languages":

Code: Select all

typedef int num;
typedef num vertex;
typedef num edge;

typedef std::vector<edge> Vertex;
typedef std::vector<std::vector<num>> Edge;

After getting it right, I am really excited of C++ lambdas.

In JavaScript I was just able to pass anonymous function to forall_vertices() as 2nd argument and code worked:

Code: Select all

function forall_vertices(G, f) {
    var v;
    for (v = 0; v < n_vertices(G); v += 1) {
        f(v);
    }
}

Code: Select all

function max_degree(G) {
    var mdeg = -1;

    forall_vertices(G, function (v) {
        if (degree(G, v) > mdeg) {
            mdeg = degree(G, v);
        }
    });

    return mdeg;
}

Now implementation of "max_deg()" with C++ lambda works.
First, "forall_vertices()" needs to be a template function in order to accept all possible function signatures as 2nd argument:

Code: Select all

template <typename F>
void forall_vertices(graph& G, const F& f) {
    for (vertex v = 0; v < n_vertices(G); v += 1) {
        f(v);
    }
}

The syntax for C++ lambdas was new to me, and passing mdeg by "reference" in lambda's capture clause did the trick:
https://www.learncpp.com/cpp-tutorial/lambda-captures/

Code: Select all

num max_degree(graph& G) {
    num mdeg = -1;

    forall_vertices(G, [G, &mdeg](vertex v) {
        if (degree(G, v) > mdeg) {
            mdeg = degree(G, v);
        }
    });

    return mdeg;
}

I am pretty sure that now after the basic design decisions are done, undirected graph library and some demos will be committed soon.


Yesterday I did implement 6-coloring of planar graphs (every planar graph has a 4-coloring of its vertices, each vertex gets one of 4 colors, and for all edges its vertices are colored differently), and by running the algorithm after "dual_graph()" call that gives a 6-coloring of the embeddings faces. Colored Postscript output below, "six_coloring()" functions is only 23 lines long (in JavaScript):
viewtopic.php?p=1998664#p1998664



C20 fullerene, with face coloring, vertex labels and face labels (the vertex number in dual graph) at centroid of faces vertex coordinates:

C20_6col.png

C20_6col.png (29.26 KiB) Viewed 3517 times

P.S:
Just testing, this works already and does what "print_graph()" does — here with nested lambdas:

Code: Select all

    graph G = from_adjacency_list_lookup(K4);

    forall_vertices(G, [&G](vertex v) {
        std::cout << v << " ";
        forall_incident_edges(G, v, [&G, v](edge e) {
            std::cout << e  << "(" << opposite(G, v, e) << ") ";
        });
        std::cout << std::endl;
    });

Output:

Code: Select all

0 0(1) 1(3) 2(2) 
1 3(2) 4(3) 0(0) 
2 2(0) 5(3) 3(1) 
3 1(0) 4(1) 5(2) 

[HermannSW]

My design goal was to have C++ graph library look as similar as possible to same code in JavaScript and Python libraries.

Passing partial struct with lambdas with captures was a real challenge, but I got as close as was possible.
While C++ lambdas became available with c++11, for passing lambdas c++14 is needed.
Passing named struct members is possible with c++2a, but that requires all members to be passed named or none, enforced with compile error.
So that was no option and since today my Makefile uses "-std=c++14".

I created a standalone demo for playing just with the mentioned passing lambdas "lmbda.cpp":
https://gist.github.com/Hermann-SW/4c36 ... 6f39c52191

Code: Select all

pi@pi400-64:~ $ head -4 lmbda.cpp 
// Copyright: https://mit-license.org/
//
// cpplint lmbda.cpp 2>&1 | grep -v "Is this a non-const reference?"
// g++ -Wall -Wextra -pedantic -std=c++14 -g lmbda.cpp -o lmbda
pi@pi400-64:~ $ 

This is the struct I am talking about:

Code: Select all

struct compact5_traversal_visitor {
    void (*begin_traversal)() = 0;
    std::vector<int> (*end_traversal)() = 0;
    void (*begin_vertex)(vertex) = 0;
    void (*end_vertex)(vertex)= 0;
    void (*next_edge)(edge)= 0;
    void (*next_vertex_edge)(vertex, edge)= 0;
};

Finally I was able to call function with partially initialized struct:

Code: Select all

    compact5_traversal(G, {
        []() { std::cout << "begin_traversal " << G.V.size() << std::endl; },
        []() { std::cout << "end_traversal " << G.V.size() << std::endl;
               return std::vector<int>(0); },
        [&G](vertex v) { std::cout << v << std::endl;
                         G.V.push_back(std::vector<edge>(0)); }
    });

This really works:

Code: Select all

pi@pi400-64:~ $ ./lmbda 
begin_traversal 3
2
end_traversal 4
pi@pi400-64:~ $ 

But as said before, the member functions have to be passed in the correct order.
As can be seen above, the first function is "begin_traversal", and if that is not needed, one can pass either "0" or NULL (works, but maybe looks surprising), or better "[](){}" in case no argument gets passed like in "begin_traversal" (it would be "[](edge){}" for a function with one argument of type edge).


From starting to port to C++ I linted my C++ code. I use cpplint installed with "pip install cpplint". There is one warning I will not change my code for:

Code: Select all

pi@pi400-64:~ $ cpplint lmbda.cpp
lmbda.cpp:44:  Is this a non-const reference? If so, make const or use a pointer: graph& G  [runtime/references] [2]
Done processing lmbda.cpp
Total errors found: 1
pi@pi400-64:~ $ 

ccplint is from Google, and from many threads I learned that Google requires to pass input only arguments as const ref to a function, and pointers have to be used for output arguments. I will not do "forall_vertices(&G, ..." only to get rid of that warning. I mostly silenced the warning in cpplint target of my Makefile:

Code: Select all

cpplint:
	cpplint util.cpp 
	cpplint tst.cpp
	cpplint undirected_graph.hpp 2>&1 | grep -v "Is this a non-const reference?"

This is the result, 20 ignored warnings in my current dev environment:

Code: Select all

pi@pi400-64:~/planar_graph_playground/c++ $ make cpplint
cpplint util.cpp 
Done processing util.cpp
cpplint tst.cpp
Done processing tst.cpp
cpplint undirected_graph.hpp 2>&1 | grep -v "Is this a non-const reference?"
Done processing undirected_graph.hpp
Total errors found: 20
pi@pi400-64:~/planar_graph_playground/c++ $ 

There is one more warning I will have to accept, when compiling code with passing lambdas with captures:

Code: Select all

pi@pi400-64:~ $ g++ -Wall -Wextra -pedantic -std=c++14 -g lmbda.cpp -o lmbda
lmbda.cpp: In function ‘int main()’:
lmbda.cpp:63:11: warning: capture of variable ‘G’ with non-automatic storage duration
   63 |         [&G](vertex v) { std::cout << v << std::endl;
      |           ^
lmbda.cpp:56:7: note: ‘graph G’ declared here
   56 | graph G(3);
      |       ^
pi@pi400-64:~ $ 

At least I can now do in C++ what looks very similar to JavaScript and Python graph library, here forall vertices loop part of implementation of "print_graph()":

Code: Select all

JavaScript
    forall_vertices(G, function (v) {
        print_vertex(G, v);
    });

Code: Select all

Python
    forall_vertices(G, lambda v: print_vertex(G, v))

Code: Select all

C++ with the warning shown
    forall_vertices(G, [&G](vertex v) {
        print_vertex(G, v);
    });

Two more comments:
1)
I don't know why "compact5_traversal()" code shown above works, I thought that I would have to mention "G" either as capture in [] or as argument in () of lambda. This code works with g++ and "-std=c++14" under 64bit Raspberry Pi OS as well as 64bit Intel Linux, as long as that is the case I will accept that it works.

2)
If you look into lmbda.cpp gist you will notice that I defined "graph g;" globally, outside of "main()".
Only that way I got all working, I have no idea how to deal with the compiler errors when moving "graph G;" into "main()".
If you know or can find out, please respond here!
In general playing with C++ lambdas since yesterday "to look similar to JavaScript anonymous function / Python lambda" was a really big riddle for me until now, and I am happy that things went well until now.

[HermannSW]

I had a longer phone call with my older son, and he solved both open questions:

1)
lambdas have access to all globals, no need to pass them in [] or () to the lambda.

2)
He proposed to use std::function instead the function prototypes I used,
(I updated the gist, these are the diffs: https://gist.github.com/Hermann-SW/4c36 ... 6f39c52191)

std_function.png

std_function.png (60.18 KiB) Viewed 3376 times

and that allowed to move graph declaration into main, get rid of the compile error and just work correctly!

Code: Select all

pi@pi400-64:~ $ g++ -Wall -Wextra -pedantic -std=c++14 -g lmbda.cpp -o lmbda
pi@pi400-64:~ $ ./lmbda 
begin_traversal 3
2
end_traversal 4
pi@pi400-64:~ $ 

Moving graph definition into main complained on missing captures of G, after adding the captures all was fine:

graph_local.then_missing_captures.png

graph_local.then_missing_captures.png (39.42 KiB) Viewed 3376 times

[HermannSW]

On the right path, this is "six_coloring()" using std::function approach from previous posting.
Unlike named struct members, inserting name in comment is easier:

six_coloring.cpp.png

six_coloring.cpp.png (65.63 KiB) Viewed 3341 times

With this little demo:

tst.cpp.png

tst.cpp.png (59.01 KiB) Viewed 3344 times

Outputs 6-coloring from planar embedding read, here for maximal planar graph on 10 vertices:

Code: Select all

pi@pi400-64:~/planar_graph_playground/c++ $ ./tst ../graphs/10.a
0: 2
1: 4
2: 0
3: 0
4: 1
5: 1
6: 3
7: 0
8: 2
9: 3
pi@pi400-64:~/planar_graph_playground/c++ $ 

The 100 vertex maximal planar graph does really take 6 colors, color "5" exactly once:

Code: Select all

pi@pi400-64:~/planar_graph_playground/c++ $ ./tst ../graphs/100.a | cut -f2 -d\  | sort -n | uniq -c
     33 0
     21 1
     18 2
     16 3
     11 4
      1 5
pi@pi400-64:~/planar_graph_playground/c++ $ 

Finally speed for 500,000 vertex maximal planar graph, 20 seconds for reading embedding from SSD, computing six-colorig and writing to Pi400 SSD::

Code: Select all

pi@pi400-64:~/planar_graph_playground/c++ $ time ( ./tst ../graphs/500000.a > 500000.col )

real	0m20.977s
user	0m16.780s
sys	0m4.056s
pi@pi400-64:~/planar_graph_playground/c++ $ 

And the color count over all vertices of the graph, 8995 vertices with color 5, from colors 0..5:

Code: Select all

pi@pi400-64:~/planar_graph_playground/c++ $ cat 500000.col | cut -f2 -d\  | sort -n | uniq -c
 170718 0
 111821 1
  84250 2
  74295 3
  49931 4
   8985 5
pi@pi400-64:~/planar_graph_playground/c++ $ 

[HermannSW]

I am done with porting undirected_graph lib to C++, just need to port the demo applications sofar.

During dev I used new tst.cpp:

Code: Select all

// Copyright: https://mit-license.org/

#include "c++/util.hpp"
#include "c++/undirected_graph.hpp"

int main(int argc, char *argv[]) {
    assert(argc > 1);

    graph G;

    char *buf = readFile(argv[1]);
    std::vector<std::vector<int>> adj = parse2(&buf);

    G = from_adjacency_list(adj);

    assert(is_embedding(G));

    std::vector<std::vector<vertex>> pent = pentagons(G);
    std::cout << pent.size() << " pentagons" << std::endl;

    graph D = dual_graph(G);
    print_graph(D);
    std::cout << pentagons(D).size() << " pentagons" << std::endl;

    std::cout << is_identical_graph(G, G)
              << is_identical_graph(D, G) << std::endl;

    std::vector<int> col = six_coloring(G);

    forall_vertices(G, [col](vertex v) {
        std::cout << col[v];
    });
    std::cout << std::endl;
}

And it works:

Code: Select all

pi@pi400-64:~/planar_graph_playground/c++ $ ./tst ../graphs/10.a 
0 pentagons
16 vertices, 24 edges
0: (0)1 (7)7 (6)6
1: (0)0 (1)2 (11)10
2: (1)1 (2)3 (17)13
3: (2)2 (3)4 (13)11
4: (3)3 (4)5 (15)12
5: (4)4 (5)6 (16)8
6: (5)5 (6)0 (12)7
7: (7)0 (8)8 (12)6
8: (8)7 (9)9 (16)5
9: (9)8 (10)10 (21)15
10: (10)9 (11)1 (23)13
11: (13)3 (14)12 (19)14
12: (14)11 (15)4 (20)15
13: (17)2 (18)14 (23)10
14: (18)13 (19)11 (22)15
15: (20)12 (21)9 (22)14
2 pentagons
10
2400113023
pi@pi400-64:~/planar_graph_playground/c++ $ 

I found DFS (Depth First Search) demo among my 90s C code, ported to C++ and new undirected_graph.hpp use, and after dealing with 100 cpplint warnings (whitespace at end, missing whitespace around "=", ...) now it is cpplint warn free. For last warning to go away I had to put the "while()" of a do-while loop onto the same line as closing angle bracket:

Code: Select all

// Copyright: https://mit-license.org/
#include "c++/undirected_graph.hpp"

void DFS(const graph& G, vertex v1, edge e1) {
    std::vector<edge>    vpred(n_vertices(G), -1);
    std::vector<vertex>  epred(n_edges(G), -1);
    vertex v, w; edge g;

    v = v1; g = e1; vpred[v1] = e1;

    do {
        w = opposite(G, v, g);

        if   (vpred[w] == -1) {
            std::cout << "tree-edge " << g << " from vertex " << v;
            std::cout << " into (new) vertex " << w << std::endl;

            vpred[w] = g; v = w;
        } else if (epred[g] == -1) {
            std::cout << "back-edge " << g << " from vertex " << v;
            std::cout << " into (old) vertex " << w;
            std::cout << " visited the first time." << std::endl;

            epred[g] = v;
        } else {
            std::cout << "back-edge " << g << " from vertex " << w;
            std::cout << " into (this) vertex " << v;
            std::cout << " visited the second time." << std::endl;
        }

        g = next_incident_edge(G, v, g);

        while ((vpred[v] == g) && ((g != e1) || (v != v1))) {
            printf("backtracking over tree-edge %d", g);
            printf(" from (this) vertex %d", v);
            printf(".\n");

            v = opposite(G, v, g);
            g = next_incident_edge(G, v, g);
        }
    } while (g != e1);
}


int main() {
    vertex a, b, c, d;
    edge e;

    graph G;

    a = new_vertex(G);
    b = new_vertex(G);
    c = new_vertex(G);
    d = new_vertex(G);

    e = new_edge(G, a, b);
    new_edge(G, a, c);
    new_edge(G, a, d);
    new_edge(G, b, c);
    new_edge(G, b, d);

    DFS(G, a, e);

    return 0;
}

Its output can be seen below.
Running it on a planar embedding allows to compute an st-numbering, which can be used for a "horvert" representation of a planar graph:
Vertices are horizontal segments, edges are vertically. In case two horizontal segments are vertically visible, they have to be connected.
Below screenshot shows example ASCII display of K4, the complete graph on 4 vertices.
Algorithm for computing horvert representation takes O(n) time (better than O(n^3) for solving system of linear equations for convex face straight line drawing).
Horvert segments start and end at integer coordinates, on (2n-5)x(n-1) grid.
Algorithm needs to computes dual graph, which is available already by "dual_graph()" function.

dfsdemo_output.png

dfsdemo_output.png (176.4 KiB) Viewed 3243 times

[HermannSW]

Just completed parity in features and demos between Python and JavaScript for planar graph playground. The code is "the same" besides the changes needed for the specific programming language.

Just checked whether undirected_graph.hpp implements same functions in same order as undirected_graph.js, and found "forall_incident2_edges(G, a, ...)" missing in C++. So I implemented it: "forall_incident_edges(G, v, ...)" iterates over all edges incident to vertex v, and "a" is just a "std::vector<vertex>". In order to know which vertex of a has the selected edge, that vertex is passed as 1st argument as well. A mixture of template and lambdas:

Code: Select all

template <typename F>
void forall_incident2_edges(const graph& G, std::vector<vertex>& a, const F& f) {
    std::for_each(a.cbegin(), a.cend(), [G,f](vertex v) {
        std::for_each(G.V[v].cbegin(), G.V[v].cend(), [v,f](edge e) {
            f(v, e);
        });
    });
}

This simple code tests new function:

Code: Select all

#include "c++/undirected_graph.hpp"

int main(int argc, char *argv[]) {
    graph G = from_adjacency_list(parse2file(argv[argc-1]));
    print_graph(G);

    std::vector<vertex> a = {1, 2};
    forall_incident2_edges(G, a, [](vertex v, edge e) {
        std::cout << v << " " << e << std::endl;
    });
}

And it works:

forall_incident2_edges.png

forall_incident2_edges.png (23.2 KiB) Viewed 3170 times

After completing feature parity, all demo code for JavaScript and Python will be implemented for C++ as well:

Code: Select all

c++_test.cpp
c++_dual.cpp
c++.convex_face_straight_line_drawing.cpp
embedding_demo.cpp
embedding_demo.2.cpp
embedding_demo.3.cpp
c++_compact5.cpp
c++.convex_face_straight_line_drawing.2.cpp
c++.convex_face_straight_line_drawing.6coloring.cpp
c++_6coloring.cpp

"c++_6coloring.cpp" is done already:

pi@pi400-64:~/planar_graph_playground/c++ $ ./c++_6coloring ../graphs/C20.a -dual
12 pentagons for graph
0 pentagons for dual graph
dual graph: 12 vertices, 30 edges
0: (0)1 (19)9 (26)11 (4)3 (2)2
1: (0)0 (1)2 (20)10 (17)8 (18)9
2: (1)1 (2)0 (3)3 (5)4 (21)10
3: (3)2 (4)0 (25)11 (8)5 (6)4
4: (5)2 (6)3 (7)5 (9)6 (24)10
5: (7)4 (8)3 (27)11 (12)7 (10)6
6: (9)4 (10)5 (11)7 (13)8 (23)10
7: (11)6 (12)5 (28)11 (16)9 (14)8
8: (13)6 (14)7 (15)9 (17)1 (22)10
9: (15)8 (16)7 (29)11 (19)0 (18)1
10: (20)1 (21)2 (24)4 (23)6 (22)8
11: (25)3 (26)0 (29)9 (28)7 (27)5
6-coloring of dual graph
012102102334
pi@pi400-64:~/planar_graph_playground/c++ $

P.S:
So nice 6coloring Postscript output will be available soon for C++ planar graph playground:
viewtopic.php?t=333342&p=1998664#p1998664



P.P.S:
I displayed 6coloring demo code side-by-side, JavaScript/C++/Python and took screenshot.
33% below, 100% resolution here: https://stamm-wilbrandt.de/en/forum/6co ... es.png.jpg

6coloring.code.3_languages.png.33%.jpg

6coloring.code.3_languages.png.33%.jpg (23.38 KiB) Viewed 3157 times

[HermannSW]

From other thread posting:
viewtopic.php?t=333536&p=2001920#p2001174

A new demo just tests 6coloring without PostScript output.
Python demo can process 10000 vertex maximal planar graph in 5 seconds on Pi400.
JavaScript code does need 2.5 seconds.
For not yet identifed reason C++ needs much more time, needs debugging.

Short before submitting C++ code, more demos implemented, I followed up on the suspicious behavior that C++ code took more time than nodejs and Python for running 6coloring demo for 1000 or more vertex graphs.

I compiled with "-pg" and "-O3" and did run new c++_6coloring.cpp, which created "gmon.out".
More than 80% of CPU was shown to be used in small function "six_coloring()", when running:

Code: Select all

gprof c++_6coloring | less

Cause was, that I did list graph "G" in lambda capture list as "G", and not by reference as "&G".
So for all edges (of the complete graph!) traversed, a copy of G was made when calling lambda !
This is corrected line:

Code: Select all

        forall_incident_edges(G, v, [&G, &col, v, &bs](edge e) {

Now that C++ planar_graph_playground runs faster, it also runs with much less memory usage than nodejs or Python.
Running node_compact5.js aborts with out of memory on my Pi400 for 1 million vertex maximal planar graph with no other program running (works fine for "graphs/500000.a"). Running python_compact5.py only uses a little more than 100MB of resident memory, but runs forever.

So I generated 2 million vertex maximal planar graph and c++_compact5 did run nicely with just above one minute runtime, reading graph, validating that graph incidence lists edge order matches that of adjacency lists of read file, and finally does planar face traversal of graph for validating that the read graph is an embedding:
https://github.com/Hermann-SW/planar_gr ... /2000000.a

I tried with 3 million vertices, and it works as well (in 115 seconds real time) ...

compact5_3M_pi400.png

compact5_3M_pi400.png (49.54 KiB) Viewed 3049 times

... with 3.2GB of resident memory!

c++_3.2GB_res.png

c++_3.2GB_res.png (79.1 KiB) Viewed 3049 times

This only works if no other programs are running!
As shown 3000000.a size is 136MB, above of 100MB that can be pushed onto "normal" github.
So I submitted gzipped version to the repo:
https://github.com/Hermann-SW/planar_graph_playground/blob/main/graphs/3000000.a.gz



Btw, on weekend I 3Dprinted connectors for new paper drinking straws and created an analog C60 fullerene — 92cm high!
viewtopic.php?p=2002807#p2002807



P.S:
The red/yellow/purple/pink straws of C60 are the 12 pentagons each fullerene has.
These pentagons are the filled faces in below convex face planar straight line drawing of C60:
https://hermann-sw.github.io/planar_graph_playground/

C60.planar.png

C60.planar.png (83.89 KiB) Viewed 3019 times

[HermannSW]

I wanted "c++_compact5.cpp" demo "look as" nodejs and Python versions.
But I wanted to get detailed durations for parts of the code by high precision timestamps.
Here is the new duration output after the normal demo output:

Code: Select all

pi@pi400-64:~/planar_graph_playground/c++ $ time ./c++_compact5 ../graphs/500000.a 
identical vertex ordering in adjacency list and graph verified
is_embedding(../graphs/500000.a) verified, has 999996 faces
               init:   0.000s
         parse2file:   0.590s
from_adjacency_list:   6.050s
  graph list verify:   0.350s
       is_embedding:   2.314s
               exit:   1.111s
                sum:  10.415s

real	0m10.448s
user	0m9.967s
sys	0m0.478s
pi@pi400-64:~/planar_graph_playground/c++ $

I was able to achieve this with "_" #define placed where I wanted the (nanosecond precision) timestamps to be taken. Only other change to a "normal" program was renaming of "main()" to "_main()":

c++_compact5.cpp.png (70.99 KiB) Viewed 3001 times

For every demo timestamping stuff gets bundled under same name ".hpp" file.
"c++_compact5.hpp" might not look nice, but it does the job:

Code: Select all

#include <iomanip>

const char *_ts[7] = {"               init: ", "         parse2file: ",
                      "from_adjacency_list: ", "  graph list verify: ",
                      "       is_embedding: ", "               exit: ",
                      "                sum: "};
struct timespec _t[7];
int __t = 0;
#define _ { clock_gettime(CLOCK_REALTIME, &_t[__t++]);  }

void _tdif(int s, int i, int j) {
    std::cout << _ts[s] << std::setw(7) << (_t[j].tv_sec - _t[i].tv_sec) +
       (_t[j].tv_nsec - _t[i].tv_nsec)/1000000000.0 << "s" << std::endl;
}

int _main(int argc, char *argv[]);

int main(int argc, char *argv[]) {
  _ _main(argc, argv);

  _ std::cout << std::fixed << std::setprecision(3);
    for(int i=0; i < __t - 1; ++i) {
        _tdif(i, i, i+1);
    }
    _tdif(__t - 1, 0, __t - 1);

    return 0;
}

I did run c++_compact5 demo for maximal planar graphs with numbers of vertices in range 100K up to 2M:

c++_compact5.cpp.evaluation.png

c++_compact5.cpp.evaluation.png (37.29 KiB) Viewed 3001 times

I did compare previous implementation of "Edge" typedef with nested std::vectors with just one std::vector and one std::array<int, 2> where no vector is needed:

Code: Select all

< typedef std::vector<std::vector<int>> Edge;
---
> typedef std::vector<std::array<int, 2>> Edge;

As can be seen in above evaluation, this change reduced all runtimes by 33% (exit by 66%), so I will go with new typedef.

[HermannSW]

c++_compact5.cpp demo got two more tests:

Code: Select all

pi@pi400-64:~/planar_graph_playground/c++ $ time ./c++_compact5 ../graphs/10000.a 
identical vertex ordering in adjacency list and graph verified
is_embedding(../graphs/10000.a) verified, has 19996 faces
compat5_traversal(G, {}) done
maxdegree(G) <=5 verified
               init: 0.000s
         parse2file: 0.022s
from_adjacency_list: 0.096s
  graph list verify: 0.006s
       is_embedding: 0.035s
 compact5_traversal: 0.013s
         max_degree: 0.000s
               exit: 0.013s
                sum: 0.185s

real	0m0.191s
user	0m0.157s
sys	0m0.019s
pi@pi400-64:~/planar_graph_playground/c++ $ 

I made this "_" timestamping available for nodejs
viewtopic.php?p=2003462#p2003462

as well as for Python planar graph playground code as well:
viewtopic.php?p=2003466#p2003466


For now only c++_compact5.cpp | node_compact5.js | python_compact5.py demos will use timestamping, but that runs a lot of different graph code and allows to measure (decide which coding alternative to take, like in pevious posting implemenation change that reduces runtime overall by 33%).


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

python_compact5.cpp.js.py.png

python_compact5.cpp.js.py.png (53.36 KiB) Viewed 2960 times

[HermannSW]

The duration output uncovered a serious runtime problem for Python "parse2file()".
In order to get acceptable runtimes, I had to ignore "eval() is evil" rule:
viewtopic.php?t=333536&p=2003638#p2003638

Python planar playground is really slow compared to nodejs or C+++.

I did run c++_compact5.cpp demo for vertices in 1K..2M vertices range, with 1/2/5 schema.
Looks as if all times are as they should (no other programs were running, especially no browser)

c++_compact5.cpp.durations.png

c++_compact5.cpp.durations.png (29.11 KiB) Viewed 2915 times

[HermannSW]

I used profiling flag "-pg" in Makefile. For 1 million vertex maximal planar input graph 1000000.a "gprof ./c++_compact5 | less" showed these double digit runtime percentage contributors:

Code: Select all

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 29.59      4.29     4.29        2     2.15     2.15  compact5_traversal(graph&, compact5_traversal_visitor)
 24.55      7.85     3.56  2999994     0.00     0.00  compact5_find(graph const&, int, int)
 17.17     10.34     2.49  1999996     0.00     0.00  traverse_face(graph const&, std::vector<std::array<bool, 2ul>, std::allocator<std::array<bool, 2ul> > >&, int, int, int, planar_face_traversal_visitor&)
...

I tried some stuff, until I was successful with improving "compact5_find()".
Old implementation did check all edges incident to v and w, before it returned found edge e, because "forall_incident_edges()" uses "std::for_each()".
Now I learned that "std::find_if()" is what I want, because it aborts search as soon as edge e between vertices v and w has been found:

compact5_find.diff.png

compact5_find.diff.png (32.88 KiB) Viewed 2884 times

This gprof output with new code, "compact5_find()" is now 3rd place and not 2nd anymore (reduction from 3.56s to 1.92s by nearly 50%):

Code: Select all

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 32.60      4.29     4.29        2     2.15     2.15  compact5_traversal(graph&, compact5_traversal_visitor)
 18.47      6.72     2.43  1999996     0.00     0.00  traverse_face(graph const&, std::vector<std::array<bool, 2ul>, std::allocator<std::array<bool, 2ul> > >&, int, int, int, planar_face_traversal_visitor&)
 14.59      8.64     1.92  2999994     0.00     0.00  compact5_find(graph const&, int, int)
 11.93     10.21     1.57  5999988     0.00     0.00  new_edge_vertex(graph&, int, int)
...

[HermannSW]

Did compile under (Intel) Ubuntu 20.04 and got a single compile warning on not dealing with "fread()" response.
Just fixed it:
https://github.com/Hermann-SW/planar_gr ... 8aa450c8d9

Code: Select all

     assert(buf);
-    fread(buf, 1, l, src);
+    assert(1 == fread(buf, l, 1, src));
     fclose(src);

Not sure why g++ 9.x raised the warning, while Raspberry Pi OS g++ 10.2.1 does not.
I asked for all kinds of warnings:

Code: Select all

CCFLAGS = -Wall -Wextra -pedantic -std=c++14 -O3 -I.. -pg

[HermannSW]

I used profiling flag "-pg" in Makefile. For 1 million vertex maximal planar input graph 1000000.a "gprof ./c++_compact5 | less" showed these double digit runtime percentage contributors:

My older son pointed me to "perf" based flamegraphs.
I followed steps here:
https://www.percona.com/blog/2019/11/20 ... me-graphs/

Unfortunately on both my Pi400 bootable images (64bit and 32bit) the running kernel does not match the installed tools, so I cannot use that method on those images.

I tried Intel Ubuntu and that worked.
Captured 1 million vertex graph processing of c++_compact5 (recompiled without "-pg" for gprof):

Code: Select all

time sudo perf record -a -F 99 -g  -- ./c++_compact5 ../graphs/1000000.a

And converted to flamegraph.svg:

Code: Select all

sudo perf script | ~/src/FlameGraph/stackcollapse-perf.pl - | ~/src/FlameGraph/flamegraph.pl > flamegraph.svg

I took gimp screenshot with delay and capturing mouse pointer.
As the screenshot shows, hover help indicates information for the rectangle under mouse cursor, for which text did not fit:

screenshot_flamegraph.png

screenshot_flamegraph.png (36.7 KiB) Viewed 2778 times

[HermannSW]

For answering a question on mathoverflow:
https://mathoverflow.net/a/425181/484554

I needed fast planar graph random generator.
I had one from 1994, and want to reimplement it in my new planar_graph_playground.
In order to answer the question, I created new randomgraph repo:
https://github.com/Hermann-SW/randomgraph
My first repo I created in 2022 with most file timestamps from 1994 ...

Code: Select all

$ ls -lst
total 160
 4 -rw-rw-r-- 1 stammw stammw  1080 Jun 21 20:14 LICENSE
 4 -rw-r--r-- 1 stammw stammw   880 Jun 21 20:05 README
 4 -rw-r--r-- 1 stammw stammw  1347 Jun 21 20:00 Makefile
 4 -rw-r--r-- 1 stammw stammw   994 Nov 13  1997 array.h
 4 -rw-r--r-- 1 stammw stammw  1735 Feb 14  1996 basic.h
12 -rw-r--r-- 1 stammw stammw 10593 Feb 10  1996 randomgraph.c
 4 -rw-r--r-- 1 stammw stammw  2724 Dec 17  1994 is_embedding.c
 4 -rw-r--r-- 1 stammw stammw   264 Dec 17  1994 is_embedding.h
16 -rw-r--r-- 1 stammw stammw 12939 Dec 13  1994 list.c
 8 -rw-r--r-- 1 stammw stammw  7330 Dec 13  1994 list.h
 4 -rw-r--r-- 1 stammw stammw  2008 Dec 13  1994 set.c
12 -rw-r--r-- 1 stammw stammw  9297 Dec 13  1994 ugraph.def
40 -rw-r--r-- 1 stammw stammw 36950 Dec 13  1994 ugraph.h
 4 -rw-r--r-- 1 stammw stammw  2147 Nov 28  1994 array.c
 4 -rw-r--r-- 1 stammw stammw  2119 Nov 11  1994 randomgrapho.c
 4 -rw-r--r-- 1 stammw stammw  3807 Sep 13  1994 triangulate.c
 4 -rw-r--r-- 1 stammw stammw   171 Jun 13  1994 randomgrapho.h
 4 -rw-r--r-- 1 stammw stammw    35 Apr 15  1994 triangulate.h
 4 -rw-r--r-- 1 stammw stammw  1517 Apr 15  1994 set.h
 4 -rw-r--r-- 1 stammw stammw  1401 Mar 17  1994 basic.c
 4 -rw-r--r-- 1 stammw stammw  2669 Mar  2  1994 b_urn.h
 4 -rw-r--r-- 1 stammw stammw  1186 Mar  2  1994 b_stack.c
 4 -rw-r--r-- 1 stammw stammw   902 Mar  2  1994 b_stack.h
$ 

When I answered two days ago, I used Ubuntu.
Just before writing this posting, I tried on Raspberry Pi (64bit) OS, and got errors.
Reason is that Raspberry Pi OS gcc is more picky on multiple definitions of variables than Ubuntu gcc.
Easily fixed with this commit:
https://github.com/Hermann-SW/randomgra ... 885ef716f2


The repo allows to create planar random graphs, with type in {cubic, cubic_Halin, maximal_planar, dual_of_cubic_Halin}.

Only new feature I implemented two days ago is, that when writing output to a file ending with ".a", that file will contain the embedding adjacency list for use with planar_graph_playground. Compiling with -O3 instead of -g allows to create 1,000,000 vertex maximal planar graph embedding in 9 second on a 64bit OS Pi400:

Code: Select all

pi@pi400-64:~/randomgraph $ time ./randomgraph 1000000 -s 1234 -o t.a

-------------------------------------
malloc: 20   malloc-free: 0

real	0m8.946s
user	0m8.370s
sys	0m0.489s
pi@pi400-64:~/randomgraph $ du -sm t.a
41	t.a
pi@pi400-64:~/randomgraph $ 

Adjacency list is just JSON array of array of int file:

Code: Select all

pi@pi400-64:~/randomgraph $ ./randomgraph 7 -s 1234 -o t.a

-------------------------------------
malloc: 20   malloc-free: 0
pi@pi400-64:~/randomgraph $ cat t.a 
[[1,3,5,6,4,2],[0,2,5,3],[0,4,6,5,1],[0,1,5],[0,6,2],[2,6,0,3,1],[5,2,4,0]]
pi@pi400-64:~/randomgraph $