uknfire / tsmpy

An orthogonal layout algorithm, using TSM approach
MIT License
7 stars 4 forks source link

No planarizing in planarization step #5

Closed MobiZaman closed 3 years ago

MobiZaman commented 3 years ago

As far as I understand, the code in the planarization steps checks if the input graph is planar or not, and if it is not planar, it gives an error of bad embedding. But tsm approach's planarization step actually includes planarizing the code i.e. replacing edge crossings with dummy nodes. So, I think that this is a feature that should be added to the code.

Secondly, I wrote a code which actually does planarize the graph (wrote it in javascript because thats where i am mainly working) if it is not planar by introducing dummy nodes at edge crossings, but there is still a problem that I am facing here. Before planarizing, I am applying the cose-bilkent layout on the graph.

So, I have this example after applying the cose layout: Screenshot from 2021-06-22 17-23-12

As you can see in the image, there are some node overlaps, but there is one that I think is causing the following error:

"networkx.exception.NetworkXException: Bad embedding. The graph does not match Euler's formula
"

And that seems to be the edge between 5 and 7, overlapping with node 2. Now the overlap position that i found out seems to have the coordinates of: 'cdnode4': [286.5537524104812, 240.79906890662897] and the coordinates of node 2 are: '2': [287.3433442244177, 241.51810301218927]

Well they are not exactly overlapping so I dont understand why I am getting this error. To replicate the example:

NodeData: {'0': [180.2737240899976, 264.36586953431856], '1': [120.06762623467239, 114.4499172812466], '2': [287.3433442244177, 241.51810301218927], '3': [290.05982458378116, 110.71641351702715], '4': [209.29784025704862, 104.31303486475588], '5': [269.600245617032, 193.0634370994943], '6': [99.95732123421385, 288.10871690557894], '7': [304.8288584305524, 294.1996753996526], '8': [237.872743295419, 285.66795834267725], '9': [176.18134738031108, 353.0107971095598], '10': [30, 162.48616676565564], '11': [257.84834517947706, 30], '12': [374.43731394105316, 98.06770193537079], '13': [217.62190644493307, 175.611348934361], '14': [57.06209304467575, 90.99330069568339], '15': [84.143401607849, 237.91039655125132], '16': [363.27419187960845, 180.90822385170964], '17': [155.82634628796768, 190.21025982520473], '18': [377.2718863793182, 258.922598586904], '19': [88.1507982702326, 184.05866246123924], 'cdnode1': [250.79005957999524, 249.92496581202852], 'cdnode2': [95.08747608328036, 241.28465019966933], 'cdnode3': [73.74062166119, 139.92441442674192], 'cdnode4': [286.5537524104812, 240.79906890662897], 'cdnode5': [261.9009495121646, 217.49510000272585], 'cdnode6': [243.06137788175374, 153.7688323378362], 'cdnode7': [94.05100194918165, 232.15027673407496]}

Edge data: [['0', '6'], ['0', '9'], ['1', '4'], ['1', '17'], ['2', '18'], ['2', '16'], ['3', '5'], ['3', '11'], ['3', '12'], ['4', '13'], ['4', '11'], ['7', '18'], ['8', '9'], ['10', '15'], ['10', '14'], ['12', '16'], ['0', 'cdnode1'], ['cdnode1', '2'], ['cdnode1', '8'], ['0', 'cdnode2'], ['cdnode2', '15'], ['6', 'cdnode2'], ['1', 'cdnode3'], ['cdnode3', '10'], ['14', 'cdnode3'], ['cdnode3', '19'], ['2', 'cdnode4'], ['5', 'cdnode4'], ['cdnode4', '7'], ['cdnode4', 'cdnode5'], ['cdnode5', '13'], ['5', 'cdnode5'], ['cdnode5', 'cdnode1'], ['3', 'cdnode6'], ['cdnode6', '13'], ['4', 'cdnode6'], ['cdnode6', '5'], ['cdnode2', 'cdnode7'], ['cdnode7', '19'], ['15', 'cdnode7'], ['cdnode7', '17']]

uknfire commented 3 years ago

You didn't turn all intersections into dummy nodes, and there exists a intersection between cdnode1--2 and cdnode4--7. Use tsmpy.precheck(G, pos), you will get an exception means it is invalid input.

uknfire commented 3 years ago

As for the first question, if this step is not hard to implement, I will consider doing so. Or you can make a pull request.