How to verify if a graph has crossing edges in networkx?

Question

I am creating a genetic algorithm to solve the traveling salesman problem using python and networkx. And I'm adding a condition to converge to a satisfactory solution: the path must not have crossing edges. I wonder if there's a quick function in networkx to verify if the graph has crossing edges or, at least, want to know if it's possible to create one.

The graph is created with a list of points (path), each point has a coordinate in x, and a coordinate in y. The sequence of points index the path to tour. I created an object nx.Graph() like below:

        G = nx.Graph()
        for i in range(len(path)):
            G.add_node(i, pos=(path[i].x, path[i].y))
            
        for i in range(len(path)-1):
            G.add_edge(i, i+1)
        G.add_edge(len(path)-1, 0)

One example of converging not optimal solution:

printing out the points with nx.get_node_attributes(G,'pos'):

{0: (494, 680), 1: (431, 679), 2: (217, 565), 3: (197, 581), 4: (162, 586), 5: (90, 522), 6:(138, 508), 7: (217, 454), 8: (256, 275), 9: (118, 57), 10: (362, 139), 11: (673, 89), 12: (738, 153), 13: (884, 119), 14: (687, 542), 15: (720, 618), 16: (745, 737), 17: (895, 887), 18: (902, 574), 19: (910, 337), 20: (823, 371), 21: (601, 345), 22: (608, 302), 23: (436, 294), 24: (515, 384), 25: (646, 495)}

Here is an article supporting the condition of convergence: http://www.ams.org/publicoutreach/feature-column/fcarc-tsp

This looks like a good starting point: https://en.wikipedia.org/wiki/Multiple_line_segment_intersection — 0x5453, Oct 11 '22 at 17:43
Related question: [How check if there is intersection of any two edges given the fixed nodes positions, assuming the edges are drawn as straight lines with networkx?](https://stackoverflow.com/questions/65157139/how-check-if-there-is-intersection-of-any-two-edges-given-the-fixed-nodes-positi) — kirogasa, Oct 13 '22 at 14:23

score 6 · Accepted Answer · answered Oct 12 '22 at 16:43

My first reading was the same as @AveragePythonEngineer's. Normally in the travelling salesman problem, and graph theory in general, we don't care too much about the positions of the vertices, only the distances between them. And I thought you might be confusing the drawing of a graph with the graph (it's just one realization of infinite possible drawings). So while you can draw a planar graph with crossing edges if you wish (like your example), the point is that you could draw it in the plane.

On re-reading your question, I think you're actually introducing the 'no crossing paths' as a constraint. To put it another way using the jargon: the path must not be self-intersecting. If that's right, then I think this question in GIS Stack Exchange will help you. It uses shapely, a very useful tool for 2D geometric questions. From the first answer:

[Check out] .is_simple

Returns True if the feature does not cross itself.

from shapely.wkt import loads
l = loads('LINESTRING (9603380.577551289 2719693.31939431, 9602238.01822002 2719133.882441244, 9601011.900844947 2718804.012436028, 9599670.800095448 2718931.680117098, 9599567.204161201 2717889.384686942, 9600852.184025297 2721120.409265322, 9599710.80929024 2720511.270897166, 9602777.832940497 2718125.875545334)')
print(l.is_simple) # False

If you're looking to solve the problem from scratch then this answer to a similar question, but in a different framework, has some interesting leads, especially the Bentley–Ottmann algorithm, which might be useful.

Solving it through the Bentley-Ottmann algorithm seems the ideal way. I will adapt the graph to shapely and compare them. Thank you very much! For curiosity, my algorithm is in https://github.com/onofabricio/caixeiroViajante. (It is in Portuguese) Just run the main.py script and solve for random points — Fabricio Brum, Oct 13 '22 at 13:00

score 4 · Answer 2 · answered Oct 12 '22 at 14:23

4

I am not sure, whether it suits your problem, but it seems to me that it is related to the planarity of a graph.

You can check whether a graph is planar with:

nx.is_planar(G)

which returns True, if it is. See the documentation.

answered Oct 12 '22 at 14:23

AveragePythonEnjoyer

1,115
3
14

I actually tried this before and it always returned True, I don't know why. – Fabricio Brum Oct 13 '22 at 12:41

How to verify if a graph has crossing edges in networkx?

2 Answers2