Edge directions

This module collects metrics concerning the orientation of edges.

Methods

edge_directions.angular_resolution(g: Graph, pos: str | dict | None = None, deg: bool = False) → float

Returns the deviation from the optimal angle between any two edges sharing an endpoint as defined by Purchase[1].

More precisely, the deviation from the optimal angle is defined as \(\sum \lvert \frac{o_i - \theta_i}{o_i}\rvert\), where \(o_i\) is the optimal angle \(\frac{360^\circ}{\text{deg}(i)}\) of a vertex \(i\) and \(\theta_i\) the actual minimal angle formed by edges at \(i\).

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.

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

Returns:

Angular resolution between 0 and 1

Return type:

float

edge_directions.average_flow(g: DiGraph, pos: str | dict | None = None) → Tuple[float, float] | None

Calculates the average edge direction as defined by Purchase[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.

Returns:

The average edge direction, as a normalized vector.

Return type:

Optional[Tuple[float, float]]

edge_directions.coherence_to_average_flow(g: DiGraph, pos: str | dict | None = None) → float | None

Calculates the upwards flow along the average edge direction. This is equal to calling upwards_flow(g, average_flow(g))().

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.

Returns:

The coherence to the average flow

Return type:

Optional[float]

edge_directions.combinatorial_embedding(g: Graph, pos: str | dict | None = None) → dict

Returns the combinatorial embedding for the given networkX graph g.

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.

Returns:

The new node positions

Return type:

dict

edge_directions.edge_angles(g: Graph, node: object, pos: str | dict | None = None, deg: bool = False) → List

Returns a list of edge angles for the given node present in the networkX graph.

Parameters:

• g (nx.Graph) – A networkX graph

• node (object) – A node key present in the given 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.

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

Returns:

List of angles between the edges in a clockwise order

Return type:

List

edge_directions.edge_length_deviation(g: Graph, pos: str | dict | None = None, ideal_length: float = None) → float

Calculates the average edge length deviation as defined by Mooney et al.[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.

• ideal_length (float) – The ideal length an edge should have. If not supplied, the average edge length is assumed to be the ideal edge length.

Returns:

Edge length deviation between 0 and 1

Return type:

float

edge_directions.edge_orthogonality(g: Graph, pos: str | dict | None = None) → float

Returns the extend to which edges are vertical or horizontal.

The measure was first defined by Purchase[1].

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None] :return: Edge orthogonality between 0 and 1) – 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.

Return type:

float

edge_directions.minimum_angle(g: Graph, pos: str | dict | None = None, deg: bool = False) → float

Returns the shallowest angle between any two edges sharing an endpoint.

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.

• deg (bool :return: Minimum angle between two adjacent edges) – If true, the angles are returned as degrees in the range of (0,360). Otherwise, the angles are returned as radians.

Return type:

float

edge_directions.ordered_neighborhood(g: Graph, node: object, pos: str | dict | None = None) → List

Returns the neighborhood of the given node in the networkX graph ordered clockwise.

Parameters:

• g (nx.Graph) – A networkX graph

• node (object) – A node key present in the given 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.

Returns:

List of neighbors of ‘node’ ordered clockwise

Return type:

List

edge_directions.upwards_flow(g: DiGraph, pos: str | dict | None = None, direction_vector: Tuple[int | float, int | float] = (0, 1)) → float | None

Calculates the percentage of edges pointing in the ‘upwards’ direction. An edge points ‘upwards’ if the angle between the upwards vector and the edge is smaller than 90 degrees.

The measure was first defined by Purchase[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.

• direction_vector (Tuple[numeric, numeric]) – Defines the direction of ‘upwards’

Returns:

Percentage of edges pointing ‘upwards’

Return type:

Optional[float]

Bibliography

[1] (1,2,3,4)

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.

[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.