Crossings

This module provides functions for dealing with crossings, including obtaining crossing angles.

Usage

Get a quality metric based on the number of crossings using crossing_density():

>>> g = nx.random_geometric_graph(20, 0.5)
>>> quality = crossing_density(g)

To obtain a list of all crossings, simply call get_crossings():

>>> crossing_list = get_crossings(g)

To planarize a graph, call planarize():

>>> planarize(g)

This will replace all crossings with new nodes at the same positions.

Methods

crossings.crossing_angles(crossing: Crossing, pos: str | dict | None, deg: bool = False) → List[float]

Returns a list of angles in clockwise order formed by the edges at the crossing point.

Parameters:

• crossing (gdMetriX.Crossing) – A crossing point

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• deg (bool) – If true, the angles are returned as degrees in the range of (0,360). Otherwise, the angles are returned as radians.

Returns:

A list of angles at that crossing in clockwise order

Return type:

List[float]

crossings.crossing_angular_resolution(g: Graph, pos: str | dict | None = None, include_node_crossings: bool = False) → float

Returns the deviation from the optimal angle between two edges at crossing points similar to edge_directions.angular_resolution().

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• include_node_crossings (bool) – Indicate whether crossings involving vertices should be returned as well. A crossing involves a vertex if an endpoint of an edge lies on another edge without actually crossing it. Singletons will never be considered, even if the vertex lies exactly on another edge.

Returns:

The average deviation from the optimal angle between two edges in any of the crossings

Return type:

float

crossings.crossing_density(g: Graph, pos: str | dict | None = None, include_node_crossings: bool = False, tighter_bound: bool = False, precision: float = 1e-09) → float

Weighs the number of crossings in the embedding against the estimated maximum number of potential crossings.

The estimated maximum number of potential crossings is is implemented as defined by Mooney et al.[1].

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• include_node_crossings (bool) – Indicate whether crossings involving vertices should be returned as well. A crossing involves a vertex if an endpoint of an edge lies on another edge without actually crossing it. Singletons will never be considered, even if the vertex lies exactly on another edge.

• tighter_bound – If set to true, a tighter bound on the maximum number of potential crossings is calculated, which might however lie below the actual maximum number of crossings. See Mooney et al.[1] for details. If set to false, the original estimate by Purchase[2] is used.

• precision (float) – Sets the absolute numeric precision. Usually, it should not be necessary to adjust the default.

Returns:

A crossing quality metric between 0 and 1

Return type:

float

crossings.get_crossings(g: Graph, pos: str | dict | None = None, include_node_crossings: bool = False, precision: float = 1e-09) → List[Crossing]

Calculates all crossings occurring in the graph. This uses the Bentley-Ottmann algorithm [3] - adapted to handle degenerate cases - and runs in \(O((n+k) \log n)\) time and space, where \(k\) is the number of reported crossings.

The sweepline approach is susceptible to precision errors. Set the precision parameter to a value big enough but smaller than the smallest distance expected between two crossings. In case of issues, use get_crossings_quadratic() instead.

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• include_node_crossings (bool) – Indicate whether crossings involving vertices should be returned as well. A crossing involves a vertex if an endpoint of an edge lies on another edge without actually crossing it. Singletons will never be considered, even if the vertex lies exactly on another edge.

• precision (float) – Sets the absolute numeric precision. Usually, it should not be necessary to adjust the default.

Returns:

A list of crossings, with a list of involved edges per crossing.

Return type:

List[Crossing]

crossings.get_crossings_quadratic(g: Graph, pos: str | dict | None = None, include_node_crossings: bool = False, precision: float = 1e-09) → List[Crossing]

This alternative crossing detection function is in general slower, but in certain worst-cases might outperform the get_crossings() method. Use this method if you have problems with precision using the get_crossings() method.

The get_crossings() method has an asymptotic runtime of \(O((n+k) \text{log} n)\), where \(k\) is the number of crossings. This method runs in \(O(n^2)\) time, which might outperform the optimized function slightly when the number of crossing is \(\Theta(n^2)\).

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• include_node_crossings (bool) – Indicate whether crossings involving vertices should be returned as well. A crossing involves a vertex if an endpoint of an edge lies on another edge without actually crossing it. Singletons will never be considered, even if the vertex lies exactly on another edge.

• precision (float) – Sets the absolute numeric precision. Usually, it should not be necessary to adjust the default.

Returns:

A list of crossings, with a list of involved edges per crossing.

Return type:

List[Crossing]

crossings.number_of_crossings(g: Graph, pos: str | dict | None = None, include_node_crossings: bool = False, precision: float = 1e-09) → int

Counts the total number of crossings in the given embedding.

Crossings involving more than 2 edges are counted for each pair of involved edges separately. Two edges crossing in a line are counted as a single crossing as if they would cross in a point only.

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• include_node_crossings (bool) – Indicate whether crossings involving vertices should be returned as well. A crossing involves a vertex if an endpoint of an edge lies on another edge without actually crossing it. Singletons will never be considered, even if the vertex lies exactly on another edge.

• precision (float) – Sets the absolute numeric precision. Usually, it should not be necessary to adjust the default.

Returns:

Number of crossings

Return type:

int

crossings.planarize(g: Graph, pos: str | dict | None = None, include_node_crossings: bool = False) → None

Planarizes the graph by replacing all crossings with nodes.

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• include_node_crossings (bool) – Indicate whether crossings involving vertices should be returned as well. A crossing involves a vertex if an endpoint of an edge lies on another edge without actually crossing it. Singletons will never be considered, even if the vertex lies exactly on another edge.

Bibliography

[1] (1,2)

Gavin J. Mooney, Helen C. Purchase, Michael Wybrow, and Stephen G. Kobourov. The multi-dimensional landscape of graph drawing metrics. In 17th IEEE Pacific Visualization Symposium. Pacific Visualization 2024, 2024.

[2]

Helen C. Purchase. Metrics for Graph Drawing Aesthetics. Journal of Visual Languages & Computing, 13(5):501–516, October 2002. doi:10.1006/jvlc.2002.0232.

[3]

Bentley and Ottmann. Algorithms for Reporting and Counting Geometric Intersections. IEEE Transactions on Computers, C-28(9):643–647, September 1979. doi:10.1109/TC.1979.1675432.