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

[HermannSW]

Initially this started with thread "C/C++(JavaScript) | planar graphs | draw fullerene in 2D/3D" in C++ forum, with plan to use Boost graph library:
viewtopic.php?t=332496

For quick prototyping and interaction with the graph I switched to using JavaScript and made tool work in the browser:
"JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface"
viewtopic.php?t=333342

Here is an example screen recording of embedding and drawing C30 fullerene, and its dual graph:



Later I created tool "rjs" allowing to run the JavaScript graph library on the command line using nodejs. Because the code needs to run in browser as well, nodejs "require" was no option. So "rjs" (run JavaScript) uses C preprocessor #include instead.

Few days ago I learned that Mathplotlib allows for drawing graphs together with networkx library:
https://twitter.com/HermannSW/status/15 ... 2681232386

Especially the zoom in/out feuture impressed me, and I wanted to get Mathplotlib output for my graph library as well.

That was the start of the Python port of my lib. No drawing yet, but graph embedding, is_embedding(), dual_graph() utllizing "planar_face_traversal()" with "planar_face_traversal_visitor" motivated by Boost graph library already work in Python.

I just did initial commit, one function is missing, and cleanup work (pylint) is not completed:
https://github.com/Hermann-SW/planar_gr ... ain/python
Here is initial demo run:

python_dual.py.png

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

In previous JavaScript posting I showed how to get rid of need for global variables in Python for use of lambda with "planar_face_traversal_visitor". The trick was to pass 1-element list of integer instead of integer, because that gets passed as reference. The needed increment of integer variable was not only needed in "is_embedding()" described in that posting. So this functions gets used several times now:
https://github.com/Hermann-SW/planar_gr ... py#L12-L13

Code: Select all

def incr(arr, i=0):
    arr[i] += 1

Here is example use in "dual_graph()":
https://github.com/Hermann-SW/planar_gr ... #L206-L216

Code: Select all

def dual_graph(G):
    last_face = [-1]

    D = new_graph(n_faces_planar(G), n_edges(G))

    pftv            = planar_face_traversal_visitor()
    pftv.begin_face = lambda: incr(last_face)
    pftv.next_edge  = lambda e: new_edge_vertex(D, last_face[0], e)
    planar_face_traversal(G, pftv)

    return D

The design goal of Python lib was to be as similar as possible to JavaScript lib, therefore no camelCase.
Tool rpylint allows for pylint with C includes, and turns off warnings like camelCase that are intentlionally accepted:
https://github.com/Hermann-SW/planar_gr ... on/rpylint


Next, after more cleanup and adding missing "is_same_embedding()" function will be to integrate with Mathplotlib.
networkx graph representation has no representation for edges, that was the reason I ported to "undirected_graph.py".
Initially networkx will be used just to draw graph with ".draw()", with coordinates determined by already implemented in JavaScript code "convex face planar straight line drawing". Later networkx will not be used anymore.


P.S:
Besides drawing with Mathplotlib, output to PostScript directly will be possible as well (the needed code just needs to be ported from JavaScript).

[HermannSW]

It took some time, and first I added new "edge label" feature to JavaScript graph library Postscript output yesterday:
viewtopic.php?p=1997149#p1997149



Then I ported Postscript drawing stuff from ps.js to ps.py, and created new embedding_demo.py not available for JavaScript right now, which I will discuss below.

First after initial posting a word on design decisions for JavaScript and Python undirected_graph libs. It was important to have an edge representation, being able to access both end vertices (with source(G, e) and target(G, e)), and most importantly, to be able to find next cyclic adjacanet edge of edge e for vertex v in constant time. For that I used 2-dimensional array G.V and 3-dimensional array G.E in JavaScript. I just used same square bracket representation in Python, but that are lists in Python. Lets take the print_graph() output for graph "K5-e" shown in previous posting. The complete graph on 5 vertices (that is non-planar), with one edge removed (between vertices 1 and 3, that graph is a planar graph):

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

Adding "print(K.V)" prints the vertex representation 2-dimenssional list:

Code: Select all

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

Adding "print(K.E)" prints the edge representation 3-dimensional list:

Code: Select all

[[[0, 0], [1, 1]], [[0, 1], [2, 2]], [[0, 2], [3, 1]], [[0, 3], [4, 1]], [[1, 0], [2, 3]], [[1, 2], [4, 0]], [[2, 0], [4, 3]], [[2, 1], [3, 2]], [[3, 0], [4, 2]]]

Looking eg. at edge "8" between vertices "3" and "4", edge 8 appears at 0th and 2nd position in adjacent edge lists G.V[3] and G.V[4].
G.E[8] is [[3, 0], [4, 2]], with 2-lists for vertex "3" (first entry) and "4" (2nd entry). The 2nd entries in the 2-lists are the indices where edge 8 apppears in adjacent edge lists of vertices 3 and 4.

"next_adjacent_edge(G, v, e)" function is essential for planar graph traversing, and the reason I created this library and do not use Python networkx lib.


I get the embeddings into graph form from vertex adjacent vertex list by "from_adjacency_list(L)".

"embedding_demo.py" is described here:
https://github.com/Hermann-SW/planar_gr ... ing_demopy

The adjacency list graph K4 (complete graph on 4 vertices) corresponds to the clockwise order of edges in graph drawing. The edge labels have the face number first, and letters in order of traversal of the face in at the end. Since the number of faces traversed for K4 is 2 + n_vertices(G) - n_edges(G) = 4, the graph is an embedding:

postscript_traversal_edge_labels.K4.png

postscript_traversal_edge_labels.K4.png (23.59 KiB) Viewed 2098 times

Now a slightly different edge order corresponding to this drawing for graph K4noemb is no embedding. Reason is that only 2 "faces" get traversed (always using "next_adjacent_edge()", next edge in clockwise order), where 4 faces are needed for a planar embedding:

postscript_traversal_edge_labels.K4noemb.png

postscript_traversal_edge_labels.K4noemb.png (24.42 KiB) Viewed 2098 times

All details can be found in embedding_demo.py source:
https://github.com/Hermann-SW/planar_gr ... ng_demo.py

I want to highlight the planar face traversal that computed the edge labels here.

Function "incr()" to increment an array entry by one can be found here:
https://github.com/Hermann-SW/planar_gr ... py#L10-L11

Code: Select all

def incr(arr, i=0):
    arr[i] += 1

Function "assgn()" to assign an array entry with a value can be found here:
https://github.com/Hermann-SW/planar_gr ... py#L39-L40

Code: Select all

    def assgn(G, v, e, arr, x):
        arr[e][ind(G, v, e)] = x

These simple helper functions are needed, since assignments are not possible in Python lambda expressions.

This is code for determining the edge labels. eface has two entries for each edge, initialized with -1. Later the displayed label will be stored. Determining which of the two locations to store for edge is is done with "ind(G, v, e)" function, which returns 0 if v is source of e, and 1 otherwise. That way for both directions of traversal of edge e data can be stored. Variables need to be passed by reference in the lambdas, so a 1-element list is used instead of integer variables last_face and cnt. The planar_face_traversal_visitor class is motivated by C++ Boost graph library, and is filled wih dummy functions doing nothing by default.
https://github.com/Hermann-SW/planar_gr ... py#L21-L34
Below code does increment last_face and sets cnt to 0 on entering a new face (begin_face).
And it assigns new edge label to eface[e]... and increments cnt for every edge visited on face traversal (next_vertex_edge).
Finally call "planar_face_traversal(G, pftv)" does the job:

Code: Select all

    eface = filled_array(n_edges(G), 2, -1)
    last_face = [-1]
    cnt = [-1]
    pftv                  = planar_face_traversal_visitor()
    pftv.begin_face       = lambda: (incr(last_face), aset(cnt,0))
    pftv.next_vertex_edge = lambda v, e: (assgn(G, v, e, eface,
                                                str(last_face[0])+"_"+chr(97+cnt[0])),
                                          incr(cnt))
    planar_face_traversal(G, pftv)

And this simple loop does add the labels to the edges (on correct side, with correct angle):
https://github.com/Hermann-SW/planar_gr ... py#L53-L64
First source and target of edge e get computed.
Then middle point cx/cy of drawn edge between v and w.
atan2() function determines the angle needed for drawing label parallel to edge e, on correct side.
Then both edge labels are printed in Postscript with the determined angle deg and incremented by 180° for the other side.
This is all done in helper function "def draw_edge_label(G, e, coords)", which is called in forall_edges() loop at bottom:

Code: Select all

    def draw_edge_label(G, e, coords):
        v = source(G, e)
        w = target(G, e)
        cx = (ps.scrx(coords[0][v]) + ps.scrx(coords[0][w])) / 2
        cy = (ps.scry(coords[1][v]) + ps.scry(coords[1][w])) / 2
        deg = math.atan2(coords[1][v] - coords[1][w], coords[0][w] - coords[0][v]) * 180 / math.pi
        print("12 " + str(deg) + " (" + eface[e][0] + ") " +
              str(cx) + " " + str(cy) + " txtdistdeg")
        print("12 " + str(180+deg) + " (" + eface[e][1] + ") " +
              str(cx) + " " + str(cy) + " txtdistdeg")
    forall_edges(G, lambda e: draw_edge_label(G, e, coords))

I will bring Python port to parity with JavaScript version of lib soon, and then extend both with new features.

I selected MIT license for planar_graph_playground repo so that you can maximally make use of this lib.

What definitely will come is computing of planar 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 imported 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


P.S:
I forgot to mention that I am done with pylint work:
https://github.com/Hermann-SW/planar_gr ... on/rpylint

I had to ignore warnings of passing more than 5 arguments to a function, 8 args are needed for one function in order to avoid use of global variables in it:
https://github.com/Hermann-SW/planar_gr ... /ps.py#L20

rpylint creates temporary file "/tmp/rpylint", which can show you which line the linter or assert statements when executed with "./rpy" are meant.

Down to a single warning (of those not silenced in rpylint) by having to use global variable "lookup" for implementing "from_adjacency_list()":
https://github.com/Hermann-SW/planar_gr ... y#L97-L112

Code: Select all

pi@pi400-64:~/planar_graph_playground/python $ ./rpylint embedding_demo.py 
************* Module rpylint
/tmp/rpylint:102:4: W0603: Using the global statement (global-statement)

------------------------------------------------------------------
Your code has been rated at 9.97/10 (previous run: 9.97/10, +0.00)

pi@pi400-64:~/planar_graph_playground/python $ 

[HermannSW]

Down to a single warning (of those not silenced in rpylint) by having to use global variable "lookup" for implementing "from_adjacency_list()":
https://github.com/Hermann-SW/planar_gr ... y#L97-L112

Code: Select all

pi@pi400-64:~/planar_graph_playground/python $ ./rpylint embedding_demo.py 
************* Module rpylint
/tmp/rpylint:102:4: W0603: Using the global statement (global-statement)

------------------------------------------------------------------
Your code has been rated at 9.97/10 (previous run: 9.97/10, +0.00)

pi@pi400-64:~/planar_graph_playground/python $ 

Wow, I will get rid of that warning by using my own 1993 technical report.
Each planar graph has a 5-bounded compaction (Lemma 3.2), which allows to test for existence whether edge u--w exists in G in O(1):
https://stamm-wilbrandt.de/en/TR/IAI-TR ... pdf#page=4
No need anymore for O(n²) space global "lookup" arrray, after having implemented that.


I played with embedding_demo.py, no need to store edge labels in edge array and then create Postscript output.
Instead the labels can be output on the fly during planar face traversal in embedding_demo.2.py:
https://github.com/Hermann-SW/planar_gr ... py#L39-L54

Then I created new /parrow PostScript define allowing for colored vector parallel to undirected edge, in direction of edge traversal:
https://gist.github.com/Hermann-SW/973b ... nt-4146273


New embedding_demo.3.py does now output colored vectors better demonstrating face traversal:
https://github.com/Hermann-SW/planar_gr ... ng_demo3py


Here just nice screenshot of 1st Postscript page with 4 colors for 4 faces:

postscript_traversal_edge_vectors.K4.png

postscript_traversal_edge_vectors.K4.png (21.49 KiB) Viewed 2037 times

Non-embedding screenshot with only two colors for two faces is here:
https://github.com/Hermann-SW/planar_gr ... 4noemb.png


Code is compact:
https://github.com/Hermann-SW/planar_gr ... py#L39-L54

For now only 4 colors are defined and are used cyclically.
At end of computation of cx/cy midpoint of edge and angle, just /parrow define gets used:

Code: Select all

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

Code: Select all

    rgb = [ "0 0 1", "0 1 0", "1 0 0", "0.5 0.5 1" ]

    def draw_vertex_edge_vector(G, v, e, rgb):
        w = opposite(G, v, e)
        cx = (ps.scrx(coords[0][v]) + ps.scrx(coords[0][w])) / 2
        cy = (ps.scry(coords[1][v]) + ps.scry(coords[1][w])) / 2
        deg = math.atan2(coords[1][v] - coords[1][w], coords[0][w] - coords[0][v]) * 180 / math.pi
        print("30 6 " + rgb + " " + str(deg) +
              " " + str(cx) + " " + str(cy) + " parrow")
              

"draw_vertex_edge_vector()" gets called in "next_vertex_edge" callback of planar face traversal visitor.
No need for cnt variable anymore, so removed:

Code: Select all

    last_face = [-1]
    pftv                  = planar_face_traversal_visitor()
    pftv.begin_face       = lambda: incr(last_face)
    pftv.next_vertex_edge = lambda v, e: draw_vertex_edge_vector(G, v, e,
                                                                 rgb[last_face[0] % len(rgb)])
    planar_face_traversal(G, pftv)

[HermannSW]

I have completely implemented third language undirected graph library (C++), in addition to JavaScript and Python.
Before implementing all the demo code in C++, I worked on functional and demo parity between JavaScript and Python parts of the repo.

rpylint reported "W0621: Redefining name '...' from outer scope" warning, which I will not fix.
I don't want to use cryptic (graph) names in undirected_graph.py, so I use mostly "G" as graph parameter name.
I have no problem with demo code using G as well, but that creates the warning.
So updated rpylint just filters this warning:

Code: Select all

#!/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 --const-naming-style=any --min-public-methods=0 --max-args=8 /tmp/rpylint | grep -v "W0621: Redefining name '.*' from outer scope"

Next I got 4 warnings on "lambda may not be necessary", like this remaining:

Code: Select all

pi@pi400-64:~/planar_graph_playground/python $ rpylint python_6coloring.py 
************* Module rpylint
/tmp/rpylint:403:23: W0108: Lambda may not be necessary (unnecessary-lambda)

------------------------------------------------------------------
Your code has been rated at 8.85/10 (previous run: 8.88/10, -0.03)

pi@pi400-64:~/planar_graph_playground/python $

I fixed three by replacing "....next_vertex = lambda v: f(v)" with "....next_vertex = f", because the warnings were correct.
But the last (shown) warning is not correct, at least functionality breaks if I do same modification that fixed the 3 other warnings.
The "#pragma" comment shows what should work, but does not.
Initially "pentagons(G)" function had 3 helper functions called via lambdas.
"next_vertex" was easily changed into not needing helper function.
"end_face" was changed by not conditionally only storing pentagons, but by storing all faces.
Pentagons into array 0 position, all others into 1 position.
That way inline "... if ... else ..." could be used with lambda.
This is final version of "pentagons(G)" function, which returns vector of pentagons of the embedded graph G:
https://github.com/Hermann-SW/planar_gr ... #L307-L322

pentagons.py.png

pentagons.py.png (31.24 KiB) Viewed 1892 times

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.

This is the output generated, identical for C++, JavaScript and Python. The 10,000 color values (0..5) being identical is a very good indicator that all 3 implementations compute the exact same thing:

Code: Select all

pi@pi400-64:~/planar_graph_playground/python $ time rpy python_6coloring.py ../graphs/10000.a 
0  pentagons for graph
2162  pentagons for dual graph
6-coloring of  graph
2222232323221314113112112212124423123234231222232131333245122322222221131241323221131321003311234013221351312113131112134241124251323211131324323313032022113213135223132323101143240123203325223240322121331422341203211442243355322222221111152200234113113322311334042110231344132110323332223211244321521402231224440134330202444323122041222331223241011323403332213304032322413034104311433333412111012310233421433303102233340232311513433343103103300123222430121403434212133022210233400330232211200422213323101223014021222130033344142002330134120444423300421343010442040333204033304343441112230224310402232440301304424112012434132303043003312323114130431031121013144013323232122334123320042202011210312322510230143011020302333323222233032040414440200304044321221402021133432021313334312234343210501033010211403242343042003223032400313411343103433303301030331022211012131322040041311031331324310404414011004242023101033000223443324022332401040223420040000001000231130210324423033234234203432032230332144131442432122020313304421024152012430334100202023023312100304244013430023042405041442020424342320101250303240310121323311224111031014320330004241042033330204203220020145003333023030032413023214422003221301031230024024541310454010003102020214104202121404030132112101040034404340005132413444203340403220301300142104120352131012340012202240023433303324311142423123330022023014445112032202143013334153131003002330431344324342321213000204314000422032112303144020202030423203100113433042100031014454305430014030222041310112203514031224032302111343024303442302203423002022032143121232450041200400300300432040325340224102400251004040443141023010240303130000012440403234400424114435111102022214113400403232004004030025523033141032013003112331010100343201314100403422324430044033030043002003032200320000300411031004134301004031010124333032032030100200030132410014301021334221310442023414003000002201222300323433303212140020302010141120440034203005034240031102210103322200310013010031150312002415012144410100330141034100022112130313234123403532411200104300001104230021041110004213103400002302222422301410000240120224542220000103131444040230404210220031030310300000232024404400002050022322000312201322342200420300201010000002103213034022324300440033102000010401242340102200430301132104113300304042020100315332130142411100114503310100143242043121003035213034010000213010011441000332030100022000211200200143333244201411021003000400202332132230030110154241130100402130113202402113310043410000224140020004121050310300010010132000010433330033431140011013000344210400020312002401303102024110531410502122103003040200000033401424031141020302030001300020003012131030402400001434122021304413440022411340201333420501033314320330100404143230033130034202033003420100250230203002031100112014133334030000310333101101101114400151043024200410112032310020210351103101340301540000052310200000032110143201103323101210343130003114213103200030313051331320404101511002001304100032130003010030404140300303000332301002444200423144010010204214403000101201342205330040000002203010133400011500040045002100001343141001010005013031300031253043355000034013000110032241125104200232523225013321213041422200301023100430010140300500103321005300043410112100223003220013014000110012020201010040000302100102010100013500130001013202401000003135312140331010323030001300302103040241214300140421032403404001320110000231041204204040401040200103203233300000001031100000001320200425030340220012001042441023144403410403103003021011000120023302000200003334114000020412241004211400014210010001001200210020212000101200130332422312112230131412213143241133020400040000002030312210100110100300000000000201201230003100002312000304005001000232030422030044400110043000124011430015111341200001101011000240043001113230050420000412111120310000400034012010100000230124022304021331014014110141040002120400030011024440040041314013002400121214311001010301201121001021002034101411323222101331410134443035043420111211210113030011104020312103133000330311102303041000300043003241442304230312202404303210030011400134131143030100400110210200013211443114411103101100402032010003000103112100320522202351320002030141105132411101010400024141033000004400230430042201201135032020040211010234021004300001230202000140013222003000100000212111430002003323213002101430201030133200020042201222030300001132110115100040202034400211320300030444004132300040410301014102001040101041002023333111012022113001010200001000040120004302030501410200001110121300221000000040240202015110202003004350101401511120410012102050210002221201001100022020240010313100000401300332121230010022000020421403010422000200015132041020101021321001010301121014003021544010002410010202122312010020201321010100020000000210213101141004000042221002104222321300010000430041023003140340010000044213414100100141240020100001002100333201041112113002120001113021014303131340000224320420300442301400110020515100201000211100001003120004001101300055103032000000031200010014401000340021410242210304243033100233010110111403110421000021141230130403320101301020013001304343001000000210110420000405200102100204011244103310202201103212231000101420000250012341043220203430000013000304023041031300200010102021000440203212031030033011303000020110003300004030101001123110001100110450004100200031131130102142400014500105000020000501221132312310134000041302052130000111331310010000213000000101300302100300033220400313000200320001243001001203201300000000102010120010101010330120202200002010000000101012033124301430010400000231340040401141021211423004102000103000022140101111021013202031020402300010300013000441134000000020153004201100000011320100200011210011000000530102022124034000201202010110010300401304000012304120320110012211201122001100400200311421000000003034223311044110042233012123004510300103000424004110422103310130014330302023003300010201021003300430145110020011005103100430300004330021110211003144131223320210020310141102030110020021010040110124050131011030204040021001004001111100021110021312310100110110402000111210310012310000001110100414200111001101031010000031311020301010010300012010040031102010010100000134121111130020000400002420140000000034421100010110114010011102040010500340014001110211031111102101211103022203212040400110000321010332110200011024110301000024002201022001103111011312040012024001112213031512011002142034041203023021100442020210020003030100002132340011300202312110131112003121202012104100013150021112110000403250101000111141300002201111030110001020420211140011300121010011040121020100003100030121102123113051201203300020001210044300142512000240102030300202241334111020012041100122201101321030142312000031143100032314321250200121030012400121001032300000120303000300301300300143410100110012130012300110322011120004100011341122040423121022000011110102210010011451111113020212100032110111001111211410112000022410013102143100120310000040000112430103303423233101302001110020001000030000000110010031110000023201001100304511003114301011023200040001103101320503221203024412013402013000300024012111010013140030221121101030132200003504100212024421423111110402301000010104110115311003000021341341131110140025240004022122133021403010201223202011202202110310101204003120031302001000123011110352033010014301102101012020023132120013103220200314010404041042001113001101010320232023000305422100120110102033110232000040004102301001132200211310205102411020130120112240012500303304010300000123122004001102130000042102112304242100313444201342113001202001230130115354131100110210431012012200114210210101001120101133031021000103500312254030102121202042110002420020234020103140311112212210102024330340223001101015034431230014011142003421010054120532132021000210101000400032110321114322001123120221500401001413112111241550010210112131040010101120100010010000301001003200143210441011000312011211150204202212232402200101210001101403012112024421000305100301310124140221201104121200111304120223104110000110101212022100022033011031341100131101424031030102102345212100131213012200230130401212042001020313511312413004102000340003021111200021232302330220020012412212410302120010031112000020242110130103221010130102102402130012303410030020022000100200200010200132312314110213201011111001100030401120311100001000122010111010205300214100401213001120020100450012102421413410112222040030022100000013331220220100101011210131012402001033234212301214322031011101321104200142411202210032034012040311321253030102211234102413011124414041421432504140301210314241030241301442020001011214114110404000100030330010000001011333334241120100030112104110212312213014110301211010010531101114014524004112020032121030300301102004023000042331000143210512123310101210211111212010003023032123001101020204013412145110212200210430112122122121011322043021220000100023041101230032303312223113021031204125231223134423023313034212300200033122100123003421200003303212130303005101310020001110003024343013040221000010320342140020111144132403040012022003020030304140323110340010111411241123212321401001214200331010100001333134210211423010321130013220102420010014331004103200325311540201202210201021032020451030132212430113251211441211110024521242140011020210110112110001322011022002220012300101023141500011300330013524322211211132114032045032031121004100311111132121001433101043301211300224324122030150201111211145411100140450010020113223012310241020104102513230021001332012331040203011430000132403311340130401410010024103314025113402330053140212010142324032012122321433400013135154344010010310002103030122050122230433401243410010304312013111101103302131024101002102012201003120003343103141324112233042010123303040022110313331321221213004100413032320442100011042002112111100332124401240211021000400431315043440140141404131033100043425214030140023200140400011121203040043002134332240102422134010402022021130320122233300134140023302230214231423233104403220202323222103243415103331343430011335311322330330001002401450210001201204023150002040222411532210300200031142100320224040030451334010344412202220122201202005040012401023401340000402154513122324004101023304410011400122233203032400215

real	0m5.112s
user	0m5.055s
sys	0m0.074s
pi@pi400-64:~/planar_graph_playground/python $ 

P.S:
Function "six_coloring()" does need only one helper function for "forall_incident_edges()" loop because of the assignment in "edge_bit()":
https://github.com/Hermann-SW/planar_gr ... #L211-L234

6coloring.py.png

6coloring.py.png (37.37 KiB) Viewed 1883 times

P.P.S:
Just committed and pushed "python_6coloring.py" 30 line demo for playing:
https://github.com/Hermann-SW/planar_gr ... oloring.py
In case optional argument is appended, 6coloring is computed for dual graph of the input graph:

Code: Select all

pi@pi400-64:~/planar_graph_playground/python $ rpy python_6coloring.py ../graphs/10.a -dual
0  pentagons for graph
2  pentagons for dual graph
dual graph: 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
6-coloring of dual graph
0101012101001120
pi@pi400-64:~/planar_graph_playground/python $ 

P.P.P.S:
Nice Postscript screenshots of 6colorings can be viewed at end of this posting:
viewtopic.php?t=333342&p=1998664#p1998664

three_6colorings.png.30%.jpg

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

[HermannSW]

With implementations of undirected graph library reaching functional and demo parity soon for JavaScript, Python and C++, I thought about documentation. I knew that doxygen can be used for C++ and JavaScript, and learned today that it can be used for Python as well.

I followed John Woolsey's workshop steps:
https://www.woolseyworkshop.com/2020/06 ... h-doxygen/

Code: Select all

pi@pi400-64:~/planar_graph_playground/python/dt $ diff Doxyfile.initial Doxyfile
35c35
< PROJECT_NAME           = "My Project"
---
> PROJECT_NAME           = "planar graph playground (Python)"
198c198
< JAVADOC_AUTOBRIEF      = NO
---
> JAVADOC_AUTOBRIEF      = YES
288c288
< OPTIMIZE_OUTPUT_JAVA   = NO
---
> OPTIMIZE_OUTPUT_JAVA   = YES
488c488
< EXTRACT_ALL            = NO
---
> EXTRACT_ALL            = YES
1793c1793
< GENERATE_LATEX         = YES
---
> GENERATE_LATEX         = NO
pi@pi400-64:~/planar_graph_playground/python/dt $ 

Running doxygen creates a lot of HTML, but since "undirected_graph.h" is not used via import in Python but via C includes (executed with "rpy" tool), the namespace prefixes for each and every function are disturbing. But after clicking on file list, then undirected_graph.py, clicking on "undirected_graph" under Namespaces gives the page I am interestwed in, with function names without prefixes::

doxygen.python.planar_graph_playground.png

doxygen.python.planar_graph_playground.png (44.6 KiB) Viewed 1801 times

The only function I documented sofar as test is "pentagons()", here in list of functions:

doxygen.python.functions.png

doxygen.python.functions.png (25.54 KiB) Viewed 1801 times

Clicking on "More" gives this:

doxygen.python.pentagons.png

doxygen.python.pentagons.png (29.43 KiB) Viewed 1801 times

I have not much experience with doxygen, but given that it allows to document all three languages of planar graph playgroound, and that even without documentation useful HTML overview pages are created, I think I will add doxygen comments for all three languages, at least for undirected_graph.(py|js|cpp) ...


P.S:
That was all that I added:

Code: Select all

def pentagons(Emb):
    """! Determine pentagon faces of embedding Emb

    @param Emb The undirected graph embedding

    @return pentagons(Emb), as list of list of vertex
    """
    def init_face(f):
        f[0] = []
...

[HermannSW]

Two days ago I got functional and demo parity between JavaScript and Python planar graph playground.
Yesterday 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).

I did use "eval()" to parse JSON (only adjacency list, which is a list, with each vertex having a list of adjacent vertices).
rpylint warned about use of eval().
I had self-written parse() and parse2() functions for parsing std::vector<int> and std::vector<std::vector<int>> in C++.
So I ported that to Python, and got rid of having to use eval:

Code: Select all

...
def parse(st):
    result = []
    i = 0

    while st[i] != '[':
        i += 1

    while st[i] != ']':

        i += 1
        while st[i].isspace():
            i += 1

        j = i

        while not(st[i].isspace()) and (st[i] != ']') and (st[i] != ','):
            i += 1

        result.append(int(st[j:i]))

        while st[i] != ']' and st[i] != ',':
            i += 1

    return st[i+1:],result

def parse2(st):
    result = []
    i = 0

    while st[i] != '[':
        i += 1

    while st[i] != ']':

        i += 1
        while st[i].isspace():
            i += 1

        st, p = parse(st[i:])
        result.append(p)

        i = 0
        while st[i] != ']' and st[i] != ',':
            i += 1

    return st[i+1:],result

...

I implemented "parse3()" as well, that is able to parse the list of adjacency lists from fullerenes.py (C20, C30, ..., C70).
Looks very similar to parse2(), just calls parse2() instead of parse() internally.

I realized that my up to now implementation for filled_array() in Python ...

Code: Select all

def filled_array(n, m, v=0):
    A = []
    for _ in range(n):
        if m == 1:
            A.append(v)
        else:
            a = []
            for _ in range(m):
                a.append(v)
            A.append(a)
    return A

... as well as JavaScript ...

Code: Select all

function filled_array(n, m, v) {
    var zm = new Array(n);

    if (v === undefined) {
        v = 0;
    }

    if (m==1)
        zm.fill(v);
    else
        for (var j=0; j<n; j++) {
            zm[j] = filled_array(m, 1, v);
        }
    return zm;
}

... do return either std::vector<int> in case of m=1 or std:vector<std::vector<int>> otherwise.
In C++ I used template for dealing with any value "v" type already.
But using another template type for return type did not work for me.
So I used "filled_array(n, m, v)" to return std:vector<std::vector<int>>, and filled_vector(n, v) for case m=1.
I will change JavaScript and Python to have code lock "the same" for all 3 languages, as that is the general design goal of planar graph playground.

[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 "rpy" tool, I tried and got this working with Python as well as nodejs!
This is output for 10K vertex maximal planar graph:

Code: Select all

pi@pi400-64:~/planar_graph_playground/python $ time rpy python_compact5.py ../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.719s
from_adjacency_list: 1.360s
  graph list verify: 0.159s
       is_embedding: 0.518s
 compact5_traversal: 0.256s
         max_degree: 0.009s
               exit: 0.056s
                sum: 3.076s

real	0m3.547s
user	0m3.430s
sys	0m0.094s
pi@pi400-64:~/planar_graph_playground/python $ 

Python timestamping does not look as similar to C++ as nodejs does, because of Python indenting rules, but very close. Like nodejs and C++ function "_main()" needs to be defined. Only for Python final call to "_summary()" is needed:
https://github.com/Hermann-SW/planar_gr ... ompact5.py

python_compact5.py.png

python_compact5.py.png (64.54 KiB) Viewed 1598 times

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

Code: Select all

pi@pi400-64:~/planar_graph_playground/python $ time rpy python_compact5.py ../graphs/10000.a 2>err
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

real	0m3.237s
user	0m3.118s
sys	0m0.126s
pi@pi400-64:~/planar_graph_playground/python $ 

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


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


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

[HermannSW]

The duration output is especially good for Python, as it reveals a problem in planar graph playground:

python_compact5.py.durations.png

python_compact5.py.durations.png (24.87 KiB) Viewed 1531 times

I just committed and pushed the newly generated maximal planar graph embeddings (20K/30K/40K/50K vertices) with random seed 12345:
https://github.com/Hermann-SW/planar_gr ... ain/graphs


The screenshot shows that with slight 10K increases of vertices, parse2file has a big issue.
The files are not really big, 50000.a is only 1780KB in size.
So the harmless looking function definition is not that harmless:

Code: Select all

def parse2file(name):
    return parse2(open(name).read())[1]

My bet is on the "open(...).read()", learned that reading in loop and copying into mmaped file might be a solution.
"parse2()" processes the whole input as string, I doubt that can be an issue.

[HermannSW]

That was an interesting problem.
I measured file read for 50K vertices graph, and that was single digit millisecond.

Then I replaced string (UTF-8) parsing with "bytes" parsing [read with open(..., "rb").read() ] instead of string.
That reduced the parse2file time from 21s to 20s for 40K, not promising.

Then I did remove the addition of the read integers of "parse()" to result array.
So the result returned was a length 40K array of empty arrays — and the time kept at 20s!
So it is really the parsing that takes the time, and not the creation of 2-dimensional list.

Finally I ignored the "eval() is evil" rule and replaced "parse2file()" parsing with just "eval()":

Code: Select all

...
 def parse2file(name):
-    return parse2(open(name).read())[1]
+    return eval(open(name).read())
 
...

That did resolve the time problems, now parse2file times are as they should for 10K..100K vertices:

python_compact5.py.durations.eval.png

python_compact5.py.durations.eval.png (34.37 KiB) Viewed 1495 times

At bottom I added parse2file and sum times for nodejs and C++, and both are much faster than Python.
Perhaps I will give numpy arrays as basis of undirected graph implementation a try later.

[HermannSW]

As addendum to last posting, newly committed perfcomp tool (uses paste command for horizontal join) allows to get planar_graph_playgound comparison for all three languages easily:

perfcomp.50000.png

perfcomp.50000.png (50.84 KiB) Viewed 1347 times

C++ directory of planar_graph_playground has a Makefile for obvious reasons.
I added Makefile to NodeJS as well as Python directories as well.

Target "clean" in all Makefiles removes generated files.
Target "clean_all" removes all generated files for C++ and NodeJS and Python.

Target "verify" runs all demo programs and accumulates their output in file "out".
At the end that file is compared against checked in file "good", in order to spot differences created by changes easily.

"verify_all" does "verify" for all three languages, and finally a diff between the output files for NodeJS and Python (because C++ has not all demos implemented yet). Boolean values (true/false for NodeJS) differ from Python (True/False). Directory where graphs are loaded from differ as well ("graphs" and "../graphs"). And there are some whitespace differences when printing array of array of integer. New python/norm normalizes away the differences, allowing for a final diff. Here from top level NodeJS Makefile:

Code: Select all

verify_all: verify
        cd c++; make verify
        cd python; make verify
        echo
        diff out good
        diff python/out python/good
        diff c++/out c++/good
        python/norm python/good | diff - good
        wc good

As said verify_all does verify for all three languages, here starts with NodeJS from top level directory:

Code: Select all

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
...

In the end the output files are checked against checked in version, normalized diff is done and final "wc" shows that >55KB output file consists of 1800 lines:

Code: Select all

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 $ 

6coloring demo is run on 10000 vertices graph, but adds only 4 lines of output, since the 10000 vertex colors (0-5) are printed as a single string in one line:

Code: Select all

pi@pi400-64:~/planar_graph_playground/python $ ./rpy python_6coloring.py ../graphs/10000.a 2>err | wc
      4      13   10074
pi@pi400-64:~/planar_graph_playground/python $ 

Theory is, that if an unintended change is done in undirected_graph (.hpp/.js/.py), a difference is likely to result.


As shown before, 6 of the demos generate PostScript output. Output of floats had different precision for NodeJS and Python at least. I normalized float outputs to 6 digits right of decimal point, for Python with this function:

Code: Select all

    def frm (self, f):
        return format(f, ".6f")

"verify_all" revealed quite some small mistakes in one or the other language implementation, but now all is fine, no diffs.

P.S:
JavaScript/NodeJS function for normalization:

Code: Select all

    exports.frm = function (d) {
        return d.toFixed(6);
    }

[HermannSW]

I worked on a planar face traversal vertex indicator feature many days, that does allow to easily follow the face traversal, in JavaScript thread:
viewtopic.php?p=2010496#p2010496

I did not yet move that functionality into PostScript define as planned, but instead moved the complicated calculations in new "ps.vertex_indicator()" function. And created new embedding_demo.4.(js|py) because I ported all to Python today. Also "ps.d2r()" converts angle in degrees into radians, and "ps.r2d()" converts radians into degree.

New Python demo:
https://github.com/Hermann-SW/planar_gr ... _demo.4.py

It generates this PostScript file, which is best viewed with "gv":

Code: Select all

pi@pi400-64:~/planar_graph_playground/python $ ./rpy embedding_demo.4.py | gv -

Below is the output. Because of teh crossing edge, this is not a planar embedding. Therefore K4-e graph has only 1 face instead of 3. You can follow the face over edges 0_a into vertex 1, then 0_b, 0_c, ..., 0_j and then 0_a again. The blue vertex indicators show which edge to follow next (as next_incident_edge()):

embedding_demo.4.py.png

embedding_demo.4.py.png (25.66 KiB) Viewed 1201 times

In case of a too pointed angle, there is not enough place for the arc, and the line and parrow need to be moved away from vertex to common intersection point. The radius R of that intersection point wrt the vertex to the radius r of the vertex indicator arc is really "interesting" (da=15° is angle left out on left and right arc side, t is the angle at the vertex traversed). In previous screenshots in JavaScript thread there was always additional debug output appended to the edge labels. Now that all works, that debug output is not needed anymore:


The factor "f" so that later "R = r * f" is computed here:
https://github.com/Hermann-SW/planar_gr ... #L209-L219

Code: Select all

        w = opposite(G, v, e)
        deg = r2d(math.atan2(coords[1][v] - coords[1][w], coords[0][w] - coords[0][v]))
        v = w
        e = next_incident_edge(G, v, e)
        w = opposite(G, v, e)
        deg2 = r2d(math.atan2(coords[1][v] - coords[1][w], coords[0][w] - coords[0][v]))
        R = r
        t = (deg + 540 - deg2) % 360
        T = math.tan(d2r(t))**2
        f = math.sin(d2r(da)) * math.sqrt((math.sqrt(T + 1) + 1)**2 / T + 1)