0

What I want?

I want to check if there is any interscions beteewn edges in my graph. I have a graph with a lot of vertices and edges.

Here is a simple graph for example:

    G = nx.Graph().to_undirected()
    G.add_nodes_from(pos)
    G.add_edge(1, 3, weight=1)
    G.add_edge(2, 4, weight=1)
    G.add_edge(2, 3, weight=1)
    nx.draw_networkx(G, with_labels=True, pos=pos)
    plt.show()

Graph

What I have tried?

I already tried to use

    print(nx.check_planarity(G, False))

but because there is an option to draw this graph as a planar graph, the return value is True

How can I check if there are edge interscions in my graph? assuming the position is fixed and the edges are drawn as straight lines

Dean Taler
  • 737
  • 1
  • 10
  • 25
  • 1
    Since you already have the position, you can compute segments intersection: https://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-intersect – Elisha Dec 05 '20 at 13:00
  • thanks, but because I have graph with more than 1000 edges I am looking for a method of networkx who does the same. – Dean Taler Dec 05 '20 at 13:20
  • 2
    Such an implementation would presumably have to be in the [`drawing` submodule](https://github.com/networkx/networkx/blob/master/networkx/drawing/layout.py) (as from networkx's point of view this is only relevant for visualization purposes), but there isn't anything that deals with edge crossings. – Paul Brodersen Dec 07 '20 at 11:14

1 Answers1

0

NetworkX does not have this function, you need to implement it yourself (How can I check if two segments intersect?) or take it from another library (for example from Shapely).

kirogasa
  • 627
  • 5
  • 19