embedded_graph module

class embedded_graph.EmbeddedGraph(x, y, node1, node2, require_single_component=False, require_planar_embedding=False, _edges_are_sorted=None)

Class for embedded 2D graphs. Can be used to construct faces and check planarity.

Definitions:

• l-cycle:

  Cycle generated by traversing the embedded graph always taking the leftmost turn at every node.

• face-cycle:

  An l-cycle with positive oriented area (using shoelace formula). If the graph is planar, face cycles are the boundaries of faces.

Requirements:

• No self-loops

• Simple (no multigraph)

Parameters

x, y(N,) array

Coordinates of nodes of embedded graph.

node1, node2(E,) int array in range(N)

endpoint nodes of edges in embedded graph. Nodes are referred to by their index in the coordinate arrays.

require_single_component=False :

If True, an error is raised if the graph is not single-component.

require_planar_embedding=False :

If True, an error is raised if the graph is not a planar embedding.

Raises

NonSimpleError

If graph is not simple.

SelfLoopError

if graph contains self-loops.

NotSingleComponentError

if graph has disconnected components and require_single_component=True.

NotPlanarEmbeddingError

If graph in not a planar embedding and require_planar_embedding=True.

Methods

add_edges(node1, node2[, ...])	Add edges to graph.
add_nodes(x, y)	Add nodes to graph.
add_nodes_and_edges(x, y, node1, node2[, ...])	Add nodes and edges to graph.
adjacency_matrix()	Returns adjacency matrix.
coo()	Returns coordinates of nodes.
cut_space_matrix()	Returns cut-space matrix.
edge_count()	Returns number of edges in graph (abbreviated by E).
face_count()	Returns number of face cycles in graph (abbreviated by F).
face_cycle_matrix()	Returns cycle matrix build with face cycles
get_boundary_faces()	Returns indices of l_cycles that are boundary faces.
get_common_edge_of_l_cycles(cycle1, cycle2)	Returns index of an edge occurring in both cycles if it exists; otherwise -1.
get_components()	Returns components of graph.
get_edge_ids(node1, node2[, return_direction])	Return indices of edges with given endpoint nodes.
get_edges()	Return node endpoints of all edges.
get_face_areas()	Returns areas of face-cycles.
get_face_centroids()	Returns centroids of faces in graph
get_face_cycles([to_list])	Returns for all face-cycles the nodes it traverses in order.
get_l_cycle_areas()	Returns signed areas of l-cycles.
get_l_cycle_centroids()	Returns centroids of l_cycles in graph
get_l_cycles([to_list])	Returns for all l-cycles the nodes it traverses in order.
get_num_components()	Returns number of connected components of graph.
is_planar_embedding()	Returns if graph is planar embedding, which is true if edges only intersect at their endpoints.
l_cycle_count()	Returns number of l-cycles in graph.
l_cycle_matrix()	Returns cycle matrix build with l_cycles.
locate_faces(x, y)	Get faces whose centroids are closest to queried coordinate.
node_count()	Returns number of nodes in graph (abbreviated by N).
permute_faces(permutation)	Permute face order.
permute_nodes(permutation)	Permute node order.
plot([fig, ax, show_cycles, cycles, ...])	Visualize embedded graph.
remove_edges(node1, node2[, ...])	Remove edges from graph with node endpoints as input.
remove_edges_by_ids(edge_ids[, ...])	Remove edges from graph with edge ids as input.
remove_nodes(node_ids[, ...])	Remove nodes from graph.
shortest_path(node1, node2[, to_list])	Returns nodes encountered along a shortest path from node1 to node2 through graph.
split_components()	Returns list of individual components of graph as separate EmbeddedGraph objects.

face_dual_graph

add_edges(node1, node2, require_single_component=False, require_planar_embedding=False)

Add edges to graph.

Parameters

node1, node2arrays in range(N)

Endpoints of edges.

require_single_component=False :

If True; raises error if the resulting graph is not single-component.

require_planar_embedding=False :

If True; raises error if the resulting graph is not a planar embedding.

Returns

new_graphEmbeddedGraph

New graph with edges added to it.

add_nodes(x, y)

Add nodes to graph.

Parameters

x, yarrays

Coordinates of the nodes to be added to the graph

Returns

new_graphEmbeddedGraph

New graph with nodes added to it.

add_nodes_and_edges(x, y, node1, node2, require_single_component=False, require_planar_embedding=False)

Add nodes and edges to graph.

Parameters

x, yarrays

coordinates of the nodes to be added to the graph

node1, node2arrays in range(N + x.size)

endpoints of edges. The i-th new node must be referred to by index N + i.

require_single_component=False :

If True; raises error if the resulting graph is not single-component

require_planar_embedding=False :

If True; raises error if the resulting graph is not a planar embedding

Returns

new_graphEmbeddedGraph

new graph with nodes and edges added to it.

adjacency_matrix()

Returns adjacency matrix.

Adjacency matrix is an (N, N) sparse symmetric matrix where a node-pair entry is 1 if the nodes share an edge, 0 if not.

coo()

Returns coordinates of nodes.

Returns

x, y(N,) arrays

Coordinates of nodes in graph.

cut_space_matrix()

Returns cut-space matrix.

Cut-space matrix is an (N, E) sparse matrix where the i-th row corresponds to the i-th node. The entry is +1 or -1 if the node is an endpoint of that edge. It is +1 if the node is the endpoint with highest idx, -1 otherwise.

edge_count()

Returns number of edges in graph (abbreviated by E).

face_count()

Returns number of face cycles in graph (abbreviated by F). In a planar graph this equals the number of faces.

face_cycle_matrix()

Returns cycle matrix build with face cycles

Cycle matrix is an (F, E) sparse matrix where the i-th row corresponds to the i-th face. The entry is +1 or -1 if the cycle contains that edge.

The value +1 is assigned if traversing the cycle counter clockwise first encounters the endpoint node of the edge with lowest id. If not, -1 is assigned.

get_boundary_faces()

Returns indices of l_cycles that are boundary faces.

get_common_edge_of_l_cycles(cycle1, cycle2, return_orientation=False)

Returns index of an edge occurring in both cycles if it exists; otherwise -1.

Parameters

cycle1, cycle2int arrays in range(F)

Indices referring to l_cycles.

return_orientation=False :

If True, orientation of edge with respect to cycle pair is returned.

Returns

shared_edgearray in range(E) with same size as cycle1,2

Edge shared by l_cycle1 and l_cycle2. If multiple exist; returns one with the lowest index.

orientationbool array with same size as cycle1,2 (optional)

True if cycle1 passes edge counterclockwise first encountering its node with lowest index.

get_components()

Returns components of graph.

Returns

components(N,) int array in range(num_components)

Components of graph.

get_edge_ids(node1, node2, return_direction=False)

Return indices of edges with given endpoint nodes.

Parameters

node1, node2arrays in range(N)

Endpoints of edges.

return_direction=Falsebool

Returns

edge_idsarray with same size as node1 in range(E)

Returns indices of edges.

edge_directionsbool array with same size as node1

True if aligned with edge direction

Raises

EdgeNotExistError

If a queried node-pair does not exist.

get_edges()

Return node endpoints of all edges.

Returns

node1, node2(E,) int arrays in range(N)

Node endpoints of all edges.

get_face_areas()

Returns areas of face-cycles. These correspond to face-areas is the graph is planar.

Returns

areas(F,) array

Areas of face-cycles.

get_face_centroids()

Returns centroids of faces in graph

Returns

x, y(F,) arrays

Returns coordinates of centroids of faces.

get_face_cycles(to_list=True)

Returns for all face-cycles the nodes it traverses in order. If the graph is planar, these enclose individual faces.

Parameters

to_list=False :

If true, output is in form of list-of-lists, otherwise concatenated array.

Returns

nodeslist-of-lists or array

For all face-cycles the nodes it traverses in order.

lengths(F,) int array

Length of every face-cycle.

get_l_cycle_areas()

Returns signed areas of l-cycles.

Returns

areas(FR,) array

Signed areas of l-cycles.

get_l_cycle_centroids()

Returns centroids of l_cycles in graph

Returns

x, y(F,) arrays

Returns coordinates of centroids of l_cycles.

get_l_cycles(to_list=True)

Returns for all l-cycles the nodes it traverses in order.

Parameters

to_list=False :

If true, output is in form of list-of-lists, otherwise concatenated array.

Returns

nodeslist-of-lists or array

For all l-cycles the nodes it traverses in order.

lengths(FR,) int array

Length of every l-cycle.

get_num_components()

Returns number of connected components of graph.

is_planar_embedding()

Returns if graph is planar embedding, which is true if edges only intersect at their endpoints.

l_cycle_count()

Returns number of l-cycles in graph. (abbreviated by FR)

l_cycle_matrix()

Returns cycle matrix build with l_cycles.

Cycle matrix is an (F, E) sparse matrix where the i-th row corresponds to the i-th l_cycle. The entry is +1 or -1 if the cycle contains that edge.

The value +1 is assigned if traversing the cycle counter clockwise first encounters the endpoint node of the edge with lowest id. If not, -1 is assigned.

locate_faces(x, y)

Get faces whose centroids are closest to queried coordinate. Graph must be planar embedding.

Returns

face_idsint array with same size as x in range(F)

Returns indices of located faces.

Attributes

x, y: arrays :

Coordinates at which one wants to locate faces.

node_count()

Returns number of nodes in graph (abbreviated by N).

permute_faces(permutation)

Permute face order.

permute_nodes(permutation)

Permute node order. Because edges refer to nodes by their position, this also changes node1 and node2.

plot(fig=None, ax=None, show_cycles=True, cycles='face_cycles', figsize=[5, 5], show_node_ids=False, show_edge_ids=False, show_face_ids=False, face_shrink_factor=0.9, markersize=5, linewidth=1, ax_position=None, title='')

Visualize embedded graph. Can optionally show indices of nodes, edges and faces.

Returns

figmatplotlib figure handle

Returns figure handle

axmatplotlib axis handle

Returns axis handle

Attributes

fig=None: None or matplotlib figure :

Figure to embed the axis in. If None, new figure is created.

ax=None: None or matplotlib axes :

Axes to plot the graph in. If None, a new axis is created.

show_cycles=Truebool

If true, the cycles are displayed.

cycles=”face_cycles”str

What cycles to show. Options are “face_cycles” or “l_cycles”.

figsize=[5, 5]array-like

Size of figure.

show_node_ids=Falsebool

If True, node ids are shown.

show_edge_ids=Falsebool

If True, edge ids are shown.

show_face_ids=Falsebool

If True, face ids are shown.

face_shrink_factor=0.9float

Shrinks faces around their centroid. This ensures they do not overlap with edges and are easier to make out.

markersize=5int

Size of nodes.

linewidth=1int

Width of lines representing edges and faces.

ax_position=NoneNone or array-like

Manual position of axis.

title=””str

Title of figure.

remove_edges(node1, node2, require_single_component=False, require_planar_embedding=False)

Remove edges from graph with node endpoints as input.

Parameters

node1, node2int arrays in range(N)

The indices of node endpoints of edges to be removed.

require_single_component=False :

If True; raises error if the resulting graph is not single-component.

require_planar_embedding=False :

If True; raises error if the resulting graph is not a planar embedding.

Returns

new_graphEmbeddedGraph

new graph with edges removed from it.

Raises

EdgeNotExistError

If a queried node-pair does not exist.

remove_edges_by_ids(edge_ids, require_single_component=False, require_planar_embedding=False)

Remove edges from graph with edge ids as input.

Parameters

edge_idsint array in range(E)

Indices of nodes to be removed.

require_single_component=False :

If True; raises error if the resulting graph is not single-component.

require_planar_embedding=False :

If True; raises error if the resulting graph is not a planar embedding.

Returns

new_graphEmbeddedGraph

new graph with edges removed from it.

remove_nodes(node_ids, require_single_component=False, require_planar_embedding=False)

Remove nodes from graph.

Parameters

node_idsint array in range(N)

Indices of nodes to be removed.

require_single_component=False :

If True; raises error if the resulting graph is not single-component.

require_planar_embedding=False :

If True; raises error if the resulting graph is not a planar embedding.

Returns

new_graphEmbeddedGraph

New graph with nodes removed from it.

shortest_path(node1, node2, to_list=True)

Returns nodes encountered along a shortest path from node1 to node2 through graph.

• paths include node1 and node2.

• If node1, node2 are (P,) arrays, returns P paths where path i goes from node1[i] to node2[i].

Parameters

node1, node2(P,) array

Start- and end-nodes of paths.

to_list=False :

If true, output is in form of list-of-lists, otherwise concatenated array.

Returns

pathslist-of-lists or array

All nodes that are traversed in path

lengths(FR,) int array

Length of every l-cycle.

split_components()

Returns list of individual components of graph as separate EmbeddedGraph objects.

class embedded_graph.EmbeddedSquareGraph(count_x, count_y, x_scale=1.0, y_scale=1.0)

Generate Embedded graph for a square lattice.

Parameters

count_x, count_yint scalar

Node count of square lattice in x- and y-direction respectively.

x_scale, y_scale=1.0float scalar

Stretch factors for square lattice in x- and y-direction respectively. Bottom-left node is at origin.

Methods

add_edges(node1, node2[, ...])	Add edges to graph.
add_nodes(x, y)	Add nodes to graph.
add_nodes_and_edges(x, y, node1, node2[, ...])	Add nodes and edges to graph.
adjacency_matrix()	Returns adjacency matrix.
coo()	Returns coordinates of nodes.
cut_space_matrix()	Returns cut-space matrix.
edge_count()	Returns number of edges in graph (abbreviated by E).
face_count()	Returns number of face cycles in graph (abbreviated by F).
face_cycle_matrix()	Returns cycle matrix build with face cycles
get_boundary_faces()	Returns indices of l_cycles that are boundary faces.
get_common_edge_of_l_cycles(cycle1, cycle2)	Returns index of an edge occurring in both cycles if it exists; otherwise -1.
get_components()	Returns components of graph.
get_edge_ids(node1, node2[, return_direction])	Return indices of edges with given endpoint nodes.
get_edges()	Return node endpoints of all edges.
get_face_areas()	Returns areas of face-cycles.
get_face_centroids()	Returns centroids of faces in graph
get_face_cycles([to_list])	Returns for all face-cycles the nodes it traverses in order.
get_l_cycle_areas()	Returns signed areas of l-cycles.
get_l_cycle_centroids()	Returns centroids of l_cycles in graph
get_l_cycles([to_list])	Returns for all l-cycles the nodes it traverses in order.
get_num_components()	Returns number of connected components of graph.
is_planar_embedding()	Returns if graph is planar embedding, which is true if edges only intersect at their endpoints.
l_cycle_count()	Returns number of l-cycles in graph.
l_cycle_matrix()	Returns cycle matrix build with l_cycles.
locate_faces(x, y)	Get faces whose centroids are closest to queried coordinate.
node_count()	Returns number of nodes in graph (abbreviated by N).
permute_faces(permutation)	Permute face order.
permute_nodes(permutation)	Permute node order.
plot([fig, ax, show_cycles, cycles, ...])	Visualize embedded graph.
remove_edges(node1, node2[, ...])	Remove edges from graph with node endpoints as input.
remove_edges_by_ids(edge_ids[, ...])	Remove edges from graph with edge ids as input.
remove_nodes(node_ids[, ...])	Remove nodes from graph.
shortest_path(node1, node2[, to_list])	Returns nodes encountered along a shortest path from node1 to node2 through graph.
split_components()	Returns list of individual components of graph as separate EmbeddedGraph objects.

face_dual_graph

class embedded_graph.EmbeddedHoneycombGraph(count_x, count_y, x_scale=1.0, y_scale=1.0)

Generate Embedded graph for a honeycomb lattice.

Parameters

count_x, count_yint scalar

The amount of times the unit cell (with shape /¯and has 4 nodes) is repeated in the x- and y-direction; generating a honeycomb lattice.

x_scale, y_scale=1.0float scalar

Stretch factors for honeycomb lattice in x- and y-direction respectively. Bottom-left node is at origin.

Methods

add_edges(node1, node2[, ...])	Add edges to graph.
add_nodes(x, y)	Add nodes to graph.
add_nodes_and_edges(x, y, node1, node2[, ...])	Add nodes and edges to graph.
adjacency_matrix()	Returns adjacency matrix.
coo()	Returns coordinates of nodes.
cut_space_matrix()	Returns cut-space matrix.
edge_count()	Returns number of edges in graph (abbreviated by E).
face_count()	Returns number of face cycles in graph (abbreviated by F).
face_cycle_matrix()	Returns cycle matrix build with face cycles
get_boundary_faces()	Returns indices of l_cycles that are boundary faces.
get_common_edge_of_l_cycles(cycle1, cycle2)	Returns index of an edge occurring in both cycles if it exists; otherwise -1.
get_components()	Returns components of graph.
get_edge_ids(node1, node2[, return_direction])	Return indices of edges with given endpoint nodes.
get_edges()	Return node endpoints of all edges.
get_face_areas()	Returns areas of face-cycles.
get_face_centroids()	Returns centroids of faces in graph
get_face_cycles([to_list])	Returns for all face-cycles the nodes it traverses in order.
get_l_cycle_areas()	Returns signed areas of l-cycles.
get_l_cycle_centroids()	Returns centroids of l_cycles in graph
get_l_cycles([to_list])	Returns for all l-cycles the nodes it traverses in order.
get_num_components()	Returns number of connected components of graph.
is_planar_embedding()	Returns if graph is planar embedding, which is true if edges only intersect at their endpoints.
l_cycle_count()	Returns number of l-cycles in graph.
l_cycle_matrix()	Returns cycle matrix build with l_cycles.
locate_faces(x, y)	Get faces whose centroids are closest to queried coordinate.
node_count()	Returns number of nodes in graph (abbreviated by N).
permute_faces(permutation)	Permute face order.
permute_nodes(permutation)	Permute node order.
plot([fig, ax, show_cycles, cycles, ...])	Visualize embedded graph.
remove_edges(node1, node2[, ...])	Remove edges from graph with node endpoints as input.
remove_edges_by_ids(edge_ids[, ...])	Remove edges from graph with edge ids as input.
remove_nodes(node_ids[, ...])	Remove nodes from graph.
shortest_path(node1, node2[, to_list])	Returns nodes encountered along a shortest path from node1 to node2 through graph.
split_components()	Returns list of individual components of graph as separate EmbeddedGraph objects.

face_dual_graph

class embedded_graph.EmbeddedTriangularGraph(count_x, count_y, x_scale=1.0, y_scale=1.0)

Generate Embedded graph for a triangular lattice.

Parameters

count_x, count_yint scalar

The amount of times the unit cell (with shape / and has 2 nodes) is repeated in the x- and y-direction; generating a triangular lattice.

x_scale, y_scale=1.0float scalar

Stretch factors for triangular lattice in x- and y-direction respectively. Bottom-left node is at origin.

Methods

add_edges(node1, node2[, ...])	Add edges to graph.
add_nodes(x, y)	Add nodes to graph.
add_nodes_and_edges(x, y, node1, node2[, ...])	Add nodes and edges to graph.
adjacency_matrix()	Returns adjacency matrix.
coo()	Returns coordinates of nodes.
cut_space_matrix()	Returns cut-space matrix.
edge_count()	Returns number of edges in graph (abbreviated by E).
face_count()	Returns number of face cycles in graph (abbreviated by F).
face_cycle_matrix()	Returns cycle matrix build with face cycles
get_boundary_faces()	Returns indices of l_cycles that are boundary faces.
get_common_edge_of_l_cycles(cycle1, cycle2)	Returns index of an edge occurring in both cycles if it exists; otherwise -1.
get_components()	Returns components of graph.
get_edge_ids(node1, node2[, return_direction])	Return indices of edges with given endpoint nodes.
get_edges()	Return node endpoints of all edges.
get_face_areas()	Returns areas of face-cycles.
get_face_centroids()	Returns centroids of faces in graph
get_face_cycles([to_list])	Returns for all face-cycles the nodes it traverses in order.
get_l_cycle_areas()	Returns signed areas of l-cycles.
get_l_cycle_centroids()	Returns centroids of l_cycles in graph
get_l_cycles([to_list])	Returns for all l-cycles the nodes it traverses in order.
get_num_components()	Returns number of connected components of graph.
is_planar_embedding()	Returns if graph is planar embedding, which is true if edges only intersect at their endpoints.
l_cycle_count()	Returns number of l-cycles in graph.
l_cycle_matrix()	Returns cycle matrix build with l_cycles.
locate_faces(x, y)	Get faces whose centroids are closest to queried coordinate.
node_count()	Returns number of nodes in graph (abbreviated by N).
permute_faces(permutation)	Permute face order.
permute_nodes(permutation)	Permute node order.
plot([fig, ax, show_cycles, cycles, ...])	Visualize embedded graph.
remove_edges(node1, node2[, ...])	Remove edges from graph with node endpoints as input.
remove_edges_by_ids(edge_ids[, ...])	Remove edges from graph with edge ids as input.
remove_nodes(node_ids[, ...])	Remove nodes from graph.
shortest_path(node1, node2[, to_list])	Returns nodes encountered along a shortest path from node1 to node2 through graph.
split_components()	Returns list of individual components of graph as separate EmbeddedGraph objects.

face_dual_graph