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

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*np.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*np.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

plot(bounding_circle=False, bounding_center_type='origin', 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. This is centered at the center type defined by bounding_center_type.

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.

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.

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