Precheck raises issue of edge crossing even when there is no edge crossing

[MobiZaman]

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.

[MobiZaman]

So, if I bypass the preCheck function, and I dont use it, then the code works fine. So, the error is in the number_of_cross function.

[MobiZaman]

The following function works now:

def number_of_cross(G, pos): ''' not accurate, may be equal to actual number or double ''' def doIntersect(p1, q1, p2, q2): def orientation(p, q, r): val = (q[1] - p[1]) (r[0] - q[0]) - (q[0] - p[0]) (r[1] - q[1]) if (val == 0): return 0 elif (val > 0): return 1 else: return 2

    def onSegment(p, q, r):
        if (q[0] <= max(p[0], r[0]) 
            and q[0] >= min(p[0], r[0]) 
            and q[1] <= max(p[1], r[1]) 
            and q[1] >= min(p[1], r[1])):
            return True;
        return False;

    o1 = orientation(p1, q1, p2);
    o2 = orientation(p1, q1, q2);
    o3 = orientation(p2, q2, p1);
    o4 = orientation(p2, q2, q1);

    if (o1 != o2 and o3 != o4):
        return True;

    if (o1 == 0 and onSegment(p1, p2, q1)): 
        return True;

    if (o2 == 0 and onSegment(p1, q2, q1)): 
          return True;

    if (o3 == 0 and onSegment(p2, p1, q2)): 
          return True;

    if (o4 == 0 and onSegment(p2, q1, q2)): 
          return True;

    return False
    #end of doIntersect function

count = 0
for a, b in G.edges:
    for c, d in G.edges:
        if a not in (c, d) and b not in (c, d):
            if doIntersect(pos[a], pos[b], pos[c], pos[d]):
                count += 1
return count

[uknfire]

Thanks for your feedback. ~I will remove this function, because I think validating the input shouldn't be a part of TSM algorithm. Less code, less bug.~ For backward compatibility, I will correct it.