Symmetry

This module defines some symmetry metrics.

Methods

class symmetry.SymmetryType(value, names=None, *, module=None, qualname=None, type=None, start=1, boundary=None)

Bases: Enum

Type of symmetry used for edge_based_symmetry()

REFLECTIVE = (0,)

ROTATIONAL = (1,)

TRANSLATIONAL = 2

symmetry.edge_based_symmetry(g: Graph, symmetry_type: SymmetryType, pos: str | dict | None = None, axes_count: int = 1, sigma_scale: float = 0.1, sigma_distance: float = 2, is_distance_bound: bool = False, angle_merge: float = 5, pixel_merge: float = 5, x_min: float = 10, y_min: float = 10) → float

This calculates the symmetry metric proposed by Klapaukh et al.[1]. It is capable of estimating either translational, reflective or rotational symmetry.

The implementation follows the Java implementation by the original authors.

Parameters:

• g (nx.Graph) – A networkX graph

• symmetry_type (gdMetriX.SymmetryType) – The type of symmetry that should be evaluated.

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

• axes_count (int) – Only the top axes_count axes are selected and evaluated.

• sigma_scale (float) – The tolerance for when two features are considered to have the same scale.

• sigma_distance (float) – The tolerance for when two features are considered to have the same position.

• is_distance_bound (bool) – Whether to bound the distance

• angle_merge (float) – The tolerance between angles for merging two axes.

• pixel_merge (float) – The tolerance between positions for merging two axes.

• x_min (float) – Tolerance in the x direction for when two points are considered equal.

• y_min (float) – Tolerance in the y direction for when two points are considered equal.

Returns:

A symmetry estimate

Return type:

float

symmetry.even_neighborhood_distribution(g: Graph, pos: str | dict | None = None) → float

Estimates symmetry by calculating how central each node is within its neighborhood as proposed by Xu et al.[2].

Let \(N_v\) be defined as the neighborhood of a node \(v \in V\) and \(W_v := N_v \cup \{v\}\). Let \(C(W_v)\) be the smallest enclosing circle of \(W_v\) and \(\text{bary}(W_v)\) its barycenter. The symmetry metric \(\sigma_v\) for a node \(v \in V\) is defined as the distance between the barycenter \(\text{bary}(W_v)\) and the center of \(\text{center}(C(W_v))\), scaled by the radius of \(C(W_v)\), i.e., \(\frac{|\text{bary}(W_v) - \text{center}(C(W_v))}{\text{radius}(C(W_v))}\).

The final metric is defined by the average over all nodes, i.e., \(\frac{1}{n} \sum_{v \in V} \sigma_v\).

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 symmetry metric defined by the neighborhood distribution.

Return type:

float

symmetry.reflective_symmetry(g: Graph, pos: str | dict | None = None, threshold: int = 2, tolerance: float = 0.01, fraction: float = 1) → float

Computes a metric for axial symmetry between 0 and 1 as defined by Purchase[3].

The metric sums up the symmetry for all axes defined by pairs of points. For each such axis, a symmetry value is calculated for all subgraphs with sufficiently many reflected nodes. The symmetry values for each subgraph are weighted by the area of the subgraph and summed up.

Note that, with a worst-case runtime of \(O(n^7)\) and a best-case runtime of \(O(n^5)\), the metric is computationally very expensive.

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.

• threshold (int) – The minimum number of edges a subgraph needs in order to be considered to be symmetric

• tolerance (float) – The tolerance for when two points should be considered to be at the same position.

• fraction – A weighing of how much crossings and endpoints should be distinguished between 0 and 1. 1 means that we do not care about whether a point is a crossing or an endpoint regarding detecting symmetry and the two are treated equally.

Returns:

Axial symmetry estimate between 0 and 1

Return type:

float

symmetry.stress(g: Graph, pos: str | dict | None = None, scale_minimization: bool = True) → float

Estimates symmetry by utilizing the stress of the graph embedding as proposed by Welch and Kobourov[4].

The stress of a graph \(G=(V,E)\) is defined as \(\sum{i,j \in V} (||p_j - p_j|| - d_{ij})^2\), where \(||p_i - p_j||\) denotes the Euclidean distance between two vertices and $d_{ij}$ the length of the shortest path between \(i\) and \(j\).

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.

• scale_minimization – If true, the scale of the drawing is adjusted to minimize the stress. To be precise, a parameter \(s\) is calculated using a binary search, minimizing the following function: \(\sum{i,j \in V} (s \cdot ||p_j - p_j|| - d_{ij})^2\)

Returns:

Stress of the graph embedding

Return type:

float

symmetry.visual_symmetry(g: Graph, pos: str | dict | None = None, resolution: int = 100, sigma: float = 2, rotational: bool = True, reflective: bool = True, dihedral: bool = True) → float

Tries to estimate the perceived symmetry of the drawing by visually testing reflective, rotational and dihedral symmetry.

Parameters:

• g (nx.Graph) – graph

• pos (dic) – Dictionary of node positions. If not supplied, it is expected that the positions are included in g.

• resolution (int) – Width and height of the image the graph is drawn to. The higher the resolution, the more sensitive the measure is to local details.

• sigma (float) – Sigma of the Gaussian blur applied to the drawing of g. The higher the value, the more the symmetry reflects just the general shape of the graph instead of local details.

• rotational (bool) – If true, rotational symmetry is measured and considered for the final symmetry value.

• reflective (bool) – If true, reflective symmetry is measured and considered for the final symmetry value.

• dihedral (bool) – If true, dihedral symmetry is measured and considered for the final symmetry value.

Returns:

A value in [0,1] estimating the perceived symmetry.

Return type:

float

Bibliography

[1]

Roman Klapaukh, Stuart Marshall, and David Pearce. A Symmetry Metric for Graphs and Line Diagrams. In Peter Chapman, Gem Stapleton, Amirouche Moktefi, Sarah Perez-Kriz, and Francesco Bellucci, editors, Diagrammatic Representation and Inference, volume 10871, pages 739–742. Springer International Publishing, Cham, 2018. doi:10.1007/978-3-319-91376-6_71.

[2]

Taihua Xu, Jie Yang, and Guanglei Gou. A Force-Directed Algorithm for Drawing Directed Graphs Symmetrically. Mathematical Problems in Engineering, 2018:1–24, November 2018. doi:10.1155/2018/6208509.

[3]

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.

[4]

E. Welch and S. Kobourov. Measuring Symmetry in Drawings of Graphs. Computer Graphics Forum, 36(3):341–351, June 2017. doi:10.1111/cgf.13192.