2.1. Embedded graphs

class ect.embed_graph.EmbeddedGraph

A class to represent a graph with 2D embedded coordinates for each vertex.

Attributes

graphnx.Graph

a NetworkX graph object

coordinatesdict

a dictionary mapping vertices to their (x, y) coordinates

__init__()

Initializes an empty EmbeddedGraph object.

add_node(vertex, x, y)

Add a vertex to the graph. If the vertex name is given as None, it will be assigned via the next_vert_name method.

Parameters:

• vertex (hashable like int or str, or None) – The name of the vertex to add.

• x (floats) – The function value of the vertex being added.

• y (floats) – The function value of the vertex being added.

• reset_pos (bool, optional) – If True, will reset the positions of the nodes based on the function values.

add_nodes_from(nodes, coordinates)

Adds multiple vertices to the graph and assigns them the given coordinates.

Parameters:

• nodes (list) – A list of vertices to be added.

• coordinates (dict) – A dictionary mapping vertices to their coordinates.

next_vert_name(s, num_verts=1)

Making a simple name generator for vertices. If you’re using integers, it will just up the count by one. Letters will be incremented in the alphabet. If you reach Z, it will return AA. If you reach ZZ, it will return AAA, etc.

Parameters:

s (str or int) – The name of the vertex to increment.

Returns:

str or int

The next name in the sequence.

add_edge(u, v)

Adds an edge between the vertices u and v if they exist.

Parameters:

• u (str) – The first vertex of the edge.

• v (str) – The second vertex of the edge.

add_cycle(coord_matrix)

Add nodes and edges from a cycle of coordinates. Specifically, will add a node for each row and the edges connecting the nodes in the order they appear in the matrix as a closed cycle.

Parameters:

coord_matrix – numpy array An (n x 2) matrix of coordinates.

get_coordinates(vertex)

Returns the coordinates of the given vertex.

Parameters:

vertex (str) – The vertex whose coordinates are to be returned.

Returns:

The coordinates of the vertex.

Return type:

tuple

set_coordinates(vertex, x, y)

Sets the coordinates of the given vertex.

Parameters:

• vertex (str) – The vertex whose coordinates are to be set.

• x (float) – The new x-coordinate of the vertex.

• y (float) – The new y-coordinate of the vertex.

Raises:

ValueError – If the vertex does not exist in the graph.

get_bounding_box()

Method to find a bounding box of the vertex coordinates in the graph.

Returns:

A list of tuples representing the minimum and maximum \(x\) and \(y\) coordinates.

Return type:

list

get_center(type='origin')

Calculate and return the center of the graph. This can be done by either returning the average of the coordiantes (mean), the center of the bounding box (min_max), or the origin (origin).

Parameters:

type (str) – The type of center to calculate. Options are mean, min_max, or origin.

Returns:

The \((x, y)\) coordinates of the center.

Return type:

numpy.ndarray

get_bounding_radius(type='origin')

Method to find the radius of the bounding circle of the vertex coordinates in the graph.

Parameters:

type (str) – The type of center to calculate the radius relative to. Options are mean, min_max, or origin.

Returns:

The radius of the bounding circle.

Return type:

float

get_centered_coordinates(type='min_max')

Method to find the centered coordinates of the vertices in the graph.

If type is min_max, the coordinates are centered at the mean of the min and max values of the \(x\) and \(y\) coordinates. If type is mean, the coordinates are centered at the mean of the \(x\) and \(y\) coordinates.

set_centered_coordinates(type='min_max')

Method to set the centered coordinates of the vertices in the graph. Warning: This overwrites the original coordinates.

get_scaled_coordinates(radius=1)

Method to find the scaled coordinates of the vertices in the graph to fit in the disk centered at 0 with radius given by radius.

Parameters:

radius (float) – The radius of the bounding disk.

Returns:

A dictionary mapping vertices to their scaled coordinates.

Return type:

dict

set_scaled_coordinates(radius=1)

Method to set the scaled coordinates of the vertices in the graph to fit in the disk centered at 0 with radius given by radius. Warning: This overwrites the original coordinates

rescale_to_unit_disk(preserve_center=True, center_type='origin')

Rescales the graph coordinates to fit within a radius 1 disk.

Parameters:

preserve_center (bool) – If True, maintains the current center point of type center_type. If False, centers the graph at (0, 0).

Returns:

Returns the instance for method chaining.

Return type:

self

Raises:

ValueError – If the graph has no coordinates or all coordinates are identical.

get_PCA_coordinates()

Method to find the PCA coordinates of the vertices in the graph.

Returns:

A dictionary mapping vertices to their PCA normalized coordinates.

Return type:

dict

set_PCA_coordinates(center_type=None, scale_radius=None)

Method to set the PCA coordinates of the vertices in the graph which is helpful for coarse alignment. If you also want to center at zero, the options for center_type are mean or min_max. Set scale_radius to a value to scale to a specific radius. Warning: This overwrites the original coordinates.

g_omega(theta)

Function to compute the function \(g_\omega(v)\) for all vertices \(v\) in the graph in the direction of \(\theta \in [0,2\pi]\) . This function is defined by \(g_\omega(v) = \langle \texttt{pos}(v), \omega \rangle\) .

Parameters:

theta (float) – The angle in \([0,2\pi]\) for the direction to compute the \(g(v)\) values.

Returns:

A dictionary mapping vertices to their \(g(v)\) values.

Return type:

dict

g_omega_edges(theta)

Calculates the function value of the edges of the graph by making the value equal to the max vertex value

Parameters:

theta (float) – The direction of the function to be calculated.

Returns:

dict

A dictionary of the function values of the edges.

sort_vertices(theta, return_g=False)

Function to sort the vertices of the graph according to the function g_omega(v) in the direction of \(\theta \in [0,2\pi]\).

TODO: eventually, do we want this to return a sorted list of g values as well? Since we’re already doing the sorting work, it might be helpful.

Parameters:

• theta (float) – The angle in \([0,2 \pi]\) for the direction to sort the vertices.

• return_g (bool) – Whether to return the \(g(v)\) values along with the sorted vertices.

Returns:

list

A list of vertices sorted in increasing order of the \(g(v)\) values. If return_g is True, also returns the g dictionary with the function values g[vertex_name]=func_value.

sort_edges(theta, return_g=False)

Function to sort the edges of the graph according to the function

\[g_\omega(e) = \max \{ g_\omega(v) \mid v \in e \}\]

in the direction of \(\theta \in [0,2\pi]\) .

Parameters:

• theta (float) – The angle in \([0,2\pi]\) for the direction to sort the edges.

• return_g (bool) – Whether to return the \(g(v)\) values along with the sorted edges.

Returns:

A list of edges sorted in increasing order of the \(g(v)\) values. If return_g is True, also returns the g dictionary with the function values g[vertex_name]=func_value.

lower_edges(v, omega)

Function to compute the number of lower edges of a vertex v for a specific direction (included by the use of sorted v_list).

Parameters:

• v (str) – The vertex to compute the number of lower edges for.

• omega (tuple) – The direction vector to consider given as an angle in [0, 2pi].

Returns:

The number of lower edges of the vertex v.

Return type:

int

get_all_normals_matrix(num_rounding_digits=None)

Function to get all angles of normals to any line between vertices in the graph, returned as a matrix. Note this includes both adjacent vertices and non-adjacent. This function is useful for knowing the angle of the circle where two vertices switch in order.

Parameters:

num_rounding_digits (int) – The number of digits to round the angles in the matrix. If None, no rounding is done.

Returns:

A tuple consissting of a matrix of angles, and the sorted label list for the rows/columns.

get_normals_dict(num_rounding_digits=None, edges_only=False, opposites=False)

Function to get all angles of normals to any line between vertices in the graph, returned as a dictionary of angles with dict[theta] returning the list of pairs of vertices with vector normal to \(\overrightarrow{AB}\) at angle theta. Note this includes both adjacent vertices and non-adjacent unless edges_only is set to True. This function is useful for knowing the angle of the circle where two vertices switch in order, especially when we want to sort the events around the circle. All angles are rounded to the number of digits given by num_rounding_digits, and are returned in the range \([0, 2\pi]\) .

Parameters:

• num_rounding_digits (int) – The number of digits to round the angles in the dictionary. If None, no rounding is done.

• edges_only (bool) – If True, the dictionary version only returns the angle of the normals to the lines between vertices sharing an edge. The matrix version is unchanged.

• opposites (bool) – If True, will also include both \(\theta\) and \(\theta + \pi\) in the dictionary keys.

Returns:

A dictionary of angles with dict[theta] returning the list of pairs of vertices with vector normal to \(\overrightarrow\{AB\}\) at angle theta, e.g. dict[theta] = [('A','B'), ('C', 'D')].

Return type:

dict

plot(bounding_circle=False, color_nodes_theta=None, ax=None, with_labels=True, **kwargs)

Function to plot the graph with the embedded coordinates.

If bounding_circle is True, a bounding circle is drawn around the graph.

If color_nodes_theta is not None, it should be given as a \(theta\) in \([0,2\pi]\). Then the nodes are colored according to the \(g(v)\) values in the direction of \(\theta\).

If with_labels is True, the nodes are labeled with their names.

If ax is not None, the plot is drawn on the given axis.

plot_bounding_circle(ax=None, bounding_center_type='origin', **kwargs)

Function to plot the bounding circle of the graph.

If ax is not None, the plot is drawn on the given axis.

If bounding_center_type is ‘origin’, the bounding circle is centered at the origin. If it is min_max, the bounding circle is centered at the mean of the min and max values of the \(x\) and :math`y` coordinates.

plot_angle_circle(ax=None, edges_only=False)

Function to plot the circle of angles for the graph.

Example Usage:

fig, ax = plt.subplots()
G.plot(ax = ax)
G.plot_angle_circle(ax = ax)

ect.embed_graph.create_example_graph(centered=True, center_type='min_max')

Function to create an example EmbeddedGraph object. Helpful for testing. If centered is True, the coordinates are centered using the center type given by center_type, either mean or min_max.

Returns:

An example EmbeddedGraph object.

Return type:

EmbeddedGraph