uknfire / tsmpy Goto Github PK

Sometimes, when i am running the layout, the precheck function gives an error and says that there is an edge crossing, even when there is no edge crossing. I tried to find a minimal example, but this bug was really hard to find, and the smallest example I could find has unfortunately almost 150 nodes. But since the issue is regarding a single edge crossing, so I dont think it should be hard to debug?

Since the node and edge Data is a bit large, I have added it to a text file and attached it here.
nodeEdgeData.odt

Now I get the following error with this:

Edge crossing:
cdnode12 cdnode29
2 cdnode11

Internal Server Error: /tsm/
Traceback (most recent call last):
File "/home/mobi/.local/lib/python3.8/site-packages/django/core/handlers/exception.py", line 47, in inner
response = get_response(request)
File "/home/mobi/.local/lib/python3.8/site-packages/django/core/handlers/base.py", line 181, in _get_response
response = wrapped_callback(request, *callback_args, **callback_kwargs)
File "/home/mobi/.local/lib/python3.8/site-packages/django/views/decorators/csrf.py", line 54, in wrapped_view
return view_func(*args, **kwargs)
File "/home/mobi/Desktop/temp/project0/communication/views.py", line 43, in dataTransport
tsm = TSM(G, pos)
File "/home/mobi/Desktop/temp/project0/communication/tsm/TSM.py", line 53, in init
compa = ortho_layout(G, init_pos, uselp)
File "/home/mobi/Desktop/temp/project0/communication/tsm/TSM.py", line 21, in ortho_layout
precheck(G, init_pos)
File "/home/mobi/Desktop/temp/project0/communication/tsm/TSM.py", line 43, in precheck
raise Exception("There are cross edges in given layout")
Exception: There are cross edges in given layout

Whereas, when i plotted the same point in a graph, and tried to find their intersection, I found none. It would be great, if you could help out with this issue.

Hi,
I am not sure if this is an issue or a missing feature, but according to your readme file, this code is based on the approach mentioned in "A Generic Framework for the Topology-Shape-Metrics Based Layout". Now, this paper mentions in the first paragraph of section 5.1 that

Tamassia defined some restrictions to make such a computation possible. The compaction by Tamassia requires orthogonal representations that contain no bends as input. Furthermore, each face of the input has to have a rectangular shape.

But I cannot find the section in your code which implements the part about making faces rectangular. Isnt this supposed to be a part of the compaction step? The output of the orthogonalization doesn't seem to be working well because of this. Or is this part already implemented somewhere in the code?

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:

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']]

Do you have any additional documentation on this repository? I would like to use the layout algorithm in my Python project

Thanks for sharing your library which I found to be very nice and useful.

I have tested it and compared its results against other other automatic-layout algorithms in one of my projects, which you may find interesting.

I am running the following code:

import networkx as nx
from topology_shape_metrics.TSM import TSM
from matplotlib import pyplot as plt

nodeData = {'0': [233.40717895650255, 245.2668161593756], '1': [197.16129504244714, 30], '2': [141.70696162531476, 231.32493034071877], '3': [60.65624829590422, 113.49167630171439], '4': [108.35736160598731, 76.64552177189921], '5': [87.0130296182083, 188.10311014236993], '6': [319.33416955603843, 259.2393822803765], '7': [30, 277.38385767958584], '8': [98.92200205792096, 284.1742280192017], '9': [179.4743438581056, 319.91589873409737], '10': [287.1444006787124, 72.41331541473198], '11': [31.12464635584422, 32.898914774980994], '12': [158.93331495445887, 99.4944443930458], '13': [139.43918552954983, 153.80882320636442], '14': [369.5136536406337, 104.14142146557003], '15': [290.598502710234, 165.863033803461], '16': [211.4553136831521, 174.1784364618411], '17': [228.30221376063673, 102.81798218614415], '18': [37.389296631515435, 206.8668863010132], '19': [387.48004971189835, 189.04480920874767], 'cdnode1': [70.62903289986328, 215.04295834065474], 'cdnode2': [91.39401162703457, 219.91146037454223], 'cdnode3': [98.17352514597789, 132.9352577570292], 'cdnode4': [120.30579006619145, 105.56723017608186], 'cdnode5': [102.94092788747736, 108.040441996923]}

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

G = nx.Graph()
pos = {}
for node in nodeData:
    G.add_node(node)
    pos[node] = nodeData[node]
for edge in edgeData:
    src = edge[0]
    tgt = edge[1]
    G.add_edge(src, tgt)
tsm = TSM(G, pos)
tsm.display()

So, basically I have positions of nodes and data of edges and I am constructing a graph with this data. Then I run the code with only planarization i.e. I am not running orthogonalization or compaction. The external face is determined incorrectly for this case.

The original document says that the allocation of sides in the faces has to be done in such a way as shown in the following figure:

It also says that
"All internal faces that are adjacent by an edge to the external face, have the edge on the same side of the external face. All internal faces connected with another internal face have the edge on the opposite side of the other internal face."

But when I debugged the code, the sides of internal faces with internal face are correct, but those of internal faces with external faces are incorrect. They seem to be the same as with internal faces.