rlgt.graphs.utils

module documentation

This Python module provides auxiliary functions for working with k-edge-colored looped complete graphs. The functions include computing flattened lengths, converting between various graph formats, and calculating edge (resp. arc) indices according to a specified edge (resp. arc) ordering.

Function binary_slices_to_color_numbers This function performs a format representation conversion from a graph format with binary slices to the corresponding format with color numbers. In other words, it performs the following conversions:
Function color_numbers_to_binary_slices This function performs a format representation conversion from a graph format with color numbers to the corresponding format with binary slices. In other words, it performs the following conversions:
Function compute_edge_indices This function considers a k-edge-colored looped complete graph and computes the index of each edge (resp. arc) from a given list, with respect to the row-major or clockwise ordering as described in the ...
Function flatten_from_adjacency_matrix This function converts a graph or batch of graphs from an adjacency matrix format to a flattened format. In other words, it performs one of the following conversions depending on the input:
Function flattened_length_to_graph_order This function computes the order of a k-edge-colored looped complete graph given its flattened length. The flattened length is the number of entries in the numpy.ndarray vector that represents the graph structure in either the flattened row-major format with color numbers or the flattened clockwise format with color numbers.
Function graph_order_to_flattened_length This function computes the flattened length of a k-edge-colored looped complete graph given its order. The flattened length is the number of entries in the numpy.ndarray vector that represents the graph structure in either the flattened row-major format with color numbers or the flattened clockwise format with color numbers.
Function unflatten_to_adjacency_matrix This function converts a graph or a batch of graphs from a flattened format to an adjacency matrix format. Specifically, it performs one of the following conversions depending on the input:
def binary_slices_to_color_numbers(input_representation: np.ndarray, is_flattened_format: bool, edge_colors: int = 2, allow_loops: bool = False) -> np.ndarray:

This function performs a format representation conversion from a graph format with binary slices to the corresponding format with color numbers. In other words, it performs the following conversions:

  1. adjacency matrix format with binary slices → adjacency matrix format with color numbers;
  2. flattened row-major format with binary slices → flattened row-major format with color numbers; and
  3. flattened clockwise format with binary slices → flattened clockwise format with color numbers.

The function also supports batch-mode operations. If the input contains multiple graphs arranged along leading dimensions, the conversion is applied independently to each graph, while preserving all leading dimensions.

Parameters
input_representation:np.ndarrayThe input format representation, given as a numpy.ndarray of type numpy.uint8.
is_flattened_format:boolA bool that determines whether the input format is one of the two possible flattened formats, i.e., the flattened row-major format with color numbers or the flattened clockwise format with color numbers.
edge_colors:intA positive int (not below 2) that represents the number of proper edge colors, i.e., k, in the considered graph or batch of graphs. The default value is 2.
allow_loops:boolA bool that indicates whether the considered graph or batch of graphs is allowed to have loops. The default value is False, i.e., loops are not allowed by default.
Returns
np.ndarrayThe corresponding output format representation, given as a numpy.ndarray of type numpy.uint8.
Note
The input format representation can be given in either the reduced binary slice format or the standard (non-reduced) binary slice format.
def color_numbers_to_binary_slices(input_representation: np.ndarray, is_flattened_format: bool, edge_colors: int = 2, allow_loops: bool = False) -> np.ndarray:

This function performs a format representation conversion from a graph format with color numbers to the corresponding format with binary slices. In other words, it performs the following conversions:

  1. adjacency matrix format with color numbers → adjacency matrix format with binary slices;
  2. flattened row-major format with color numbers → flattened row-major format with binary slices; and
  3. flattened clockwise format with color numbers → flattened clockwise format with binary slices.

The function also supports batch-mode operations. If the input has leading dimensions, the conversion is applied independently to each matrix slice defined by the last two dimensions (for adjacency matrices) or vector slice defined by the last dimension (for flattened formats), while preserving all leading dimensions.

Parameters
input_representation:np.ndarrayThe input format representation, given as a numpy.ndarray of type numpy.uint8.
is_flattened_format:boolA bool that determines whether the input format is one of the two possible flattened formats, i.e., the flattened row-major format with color numbers or the flattened clockwise format with color numbers.
edge_colors:intA positive int (not below 2) that represents the number of proper edge colors, i.e., k, in the considered graph or batch of graphs. The default value is 2.
allow_loops:boolA bool that indicates whether the considered graph or batch of graphs is allowed to have loops. The default value is False, i.e., loops are not allowed by default.
Returns
np.ndarrayThe corresponding output format representation, given as a numpy.ndarray of type numpy.uint8.
Note
The output is given in the corresponding reduced format with binary slices whenever possible, i.e., when all the considered graphs are fully colored.
def compute_edge_indices(graph_order: int, starting_vertices: np.ndarray, ending_vertices: np.ndarray, flattened_ordering: FlattenedOrdering = FlattenedOrdering.ROW_MAJOR, is_directed: bool = False, allow_loops: bool = False) -> np.ndarray:

This function considers a k-edge-colored looped complete graph and computes the index of each edge (resp. arc) from a given list, with respect to the row-major or clockwise ordering as described in the FlattenedOrdering enumeration. The edges (resp. arcs) are given as ordered pairs of vertices consisting of the starting vertex and the ending vertex. The user can select the edge (resp. arc) ordering, the graph order, whether the graphs are directed or undirected, and whether loops are allowed. For undirected graphs, the starting and ending vertices of a pair are interchangeable. If loops are not allowed, then the starting and the ending vertex from each pair must be distinct.

Parameters
graph_order:intA positive int that specifies the order of the considered graph.
starting_vertices:np.ndarrayA numpy.ndarray of type numpy.int32 containing the starting vertices of the edges (resp. arcs) whose indices are to be computed.
ending_vertices:np.ndarrayA numpy.ndarray of type numpy.int32 containing the ending vertices of the edges (resp. arcs) whose indices are to be computed.
flattened_ordering:FlattenedOrderingAn item of the FlattenedOrdering enumeration that specifies whether the edges (resp. arcs) should be arranged in row-major order or clockwise order. The default value is FlattenedOrdering.ROW_MAJOR.
is_directed:boolA bool that indicates whether the graph is directed. The default value is False, i.e., the graph is undirected by default.
allow_loops:boolA bool that indicates whether loops are allowed in the graph. The default value is False, i.e., loops are not allowed by default.
Returns
np.ndarrayA numpy.ndarray of type numpy.int32 containing the indices of the edges (resp. arcs) with respect to the selected edge (resp. arc) ordering.
def flatten_from_adjacency_matrix(adjacency_matrix: np.ndarray, flattened_ordering: FlattenedOrdering, is_directed: bool = False, allow_loops: bool = False) -> np.ndarray:

This function converts a graph or batch of graphs from an adjacency matrix format to a flattened format. In other words, it performs one of the following conversions depending on the input:

  1. adjacency matrix format with color numbers → flattened row-major format with color numbers;
  2. adjacency matrix format with binary slices → flattened row-major format with binary slices;
  3. adjacency matrix format with color numbers → flattened clockwise format with color numbers; and
  4. adjacency matrix format with binary slices → flattened clockwise format with binary slices.

The function also supports batch-mode operations. Specifically, the input may have an arbitrary number of leading dimensions, in which case the conversion is applied independently to each matrix slice defined by the last two dimensions, while all leading dimensions remain unchanged.

Parameters
adjacency_matrix:np.ndarrayThe adjacency matrix representation of the graph or batch of graphs (with color numbers or binary slices), given as a numpy.ndarray of type numpy.uint8.
flattened_ordering:FlattenedOrderingAn item of the FlattenedOrdering enumeration that specifies whether the output should use a row-major or clockwise edge (resp. arc) ordering.
is_directed:boolA bool indicating whether the graph or each graph in the batch is directed. The default value is False, i.e., the graphs are undirected by default.
allow_loops:boolA bool indicating whether loops are allowed in the graph or each graph in the batch. The default value is False, i.e., loops are not allowed by default.
Returns
np.ndarrayThe flattened format representation of the graph or batch of graphs, given as a numpy.ndarray of type numpy.uint8. The output shape preserves the leading dimensions of the input, with the last two dimensions replaced by the flattened length.
def flattened_length_to_graph_order(flattened_length: int, is_directed: bool = False, allow_loops: bool = False) -> int:

This function computes the order of a k-edge-colored looped complete graph given its flattened length. The flattened length is the number of entries in the numpy.ndarray vector that represents the graph structure in either the flattened row-major format with color numbers or the flattened clockwise format with color numbers.

Parameters
flattened_length:intThe flattened length of the considered graph, given as a nonnegative int.
is_directed:boolA bool indicating whether the considered graph is directed. The default value is False, i.e., the graph is undirected by default.
allow_loops:boolA bool indicating whether the considered graph is allowed to have loops. The default value is False, i.e., loops are not allowed by default.
Returns
intThe computed graph order, given as a positive int.
def graph_order_to_flattened_length(graph_order: int, is_directed: bool = False, allow_loops: bool = False) -> int:

This function computes the flattened length of a k-edge-colored looped complete graph given its order. The flattened length is the number of entries in the numpy.ndarray vector that represents the graph structure in either the flattened row-major format with color numbers or the flattened clockwise format with color numbers.

Parameters
graph_order:intThe order of the considered k-edge-colored looped complete graph, given as a positive int.
is_directed:boolA bool indicating whether the considered graph is directed. The default value is False, i.e., the graph is undirected by default.
allow_loops:boolA bool indicating whether the considered graph is allowed to have loops. The default value is False, i.e., loops are not allowed by default.
Returns
intThe computed flattened length, given as a nonnegative int.
def unflatten_to_adjacency_matrix(flattened: np.ndarray, flattened_ordering: FlattenedOrdering, is_directed: bool = False, allow_loops: bool = False, graph_order: int | None = None) -> np.ndarray:

This function converts a graph or a batch of graphs from a flattened format to an adjacency matrix format. Specifically, it performs one of the following conversions depending on the input:

  1. flattened row-major format with color numbers → adjacency matrix format with color numbers;
  2. flattened row-major format with binary slices → adjacency matrix format with binary slices;
  3. flattened clockwise format with color numbers → adjacency matrix format with color numbers; and
  4. flattened clockwise format with binary slices → adjacency matrix format with binary slices.

The function supports batch-mode operations. If the input has leading dimensions, the conversion is applied independently to each vector slice defined by the last dimension, while preserving the leading dimensions.

Parameters
flattened:np.ndarrayThe input flattened format representation (with color numbers or binary slices) for the graph or batch of graphs, given as a numpy.ndarray of type numpy.uint8.
flattened_ordering:FlattenedOrderingAn item of the FlattenedOrdering enumeration that specifies whether the input uses a flattened or clockwise edge (resp. arc) ordering.
is_directed:boolA bool indicating whether the graph or each graph in the batch is directed. The default value is False, i.e., the graphs are undirected by default.
allow_loops:boolA bool indicating whether loops are allowed in the graph or each graph in the batch. The default value is False, i.e., loops are not allowed by default.
graph_order:int | NoneEither None or a positive int specifying the order of the graph(s). If None, then the graph order is computed from the flattened length using flattened_length_to_graph_order. Otherwise, the provided value is used directly. The default value is None.
Returns
np.ndarrayThe adjacency matrix representation of the graph or batch of graphs, given as a numpy.ndarray of type numpy.uint8. The output preserves any leading dimensions and has the last two dimensions equal to the graph order.