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