Functions¶

Module Contents¶

graphs.lanczos_eigenvectors.find_lanczos_eigenvectors(graph: list[list[int | None]], num_eigenvectors: int) → tuple[numpy.ndarray, numpy.ndarray]¶

Computes the largest eigenvalues and their corresponding eigenvectors using the Lanczos method.

Args:

graph: The graph as a list of adjacency lists. num_eigenvectors: Number of largest eigenvalues and eigenvectors to compute.

Returns:

A tuple containing:

• eigenvalues: 1D array of the largest eigenvalues in descending order.

• eigenvectors: 2D array where each column is an eigenvector corresponding

  to an eigenvalue.

Raises:

ValueError: If the graph format is invalid or num_eigenvectors is out of bounds.

>>> eigenvalues, eigenvectors = find_lanczos_eigenvectors(
...     [[1, 2], [0, 2], [0, 1]], 2
... )
>>> len(eigenvalues) == 2 and eigenvectors.shape[1] == 2
True

graphs.lanczos_eigenvectors.lanczos_iteration(graph: list[list[int | None]], num_eigenvectors: int) → tuple[numpy.ndarray, numpy.ndarray]¶

Constructs the tridiagonal matrix and orthonormal basis vectors using the Lanczos method.

Args:

graph: The graph represented as a list of adjacency lists. num_eigenvectors: The number of largest eigenvalues and eigenvectors

to approximate.

Returns:

A tuple containing:

• tridiagonal_matrix: A (num_eigenvectors x num_eigenvectors) symmetric

  matrix.

• orthonormal_basis: A (num_nodes x num_eigenvectors) matrix of orthonormal

  basis vectors.

Raises:

ValueError: If num_eigenvectors is less than 1 or greater than the number of

nodes.

>>> graph = [[1, 2], [0, 2], [0, 1]]
>>> T, Q = lanczos_iteration(graph, 2)
>>> T.shape == (2, 2) and Q.shape == (3, 2)
True

graphs.lanczos_eigenvectors.main() → None¶

Main driver function for testing the implementation with doctests.

graphs.lanczos_eigenvectors.multiply_matrix_vector(graph: list[list[int | None]], vector: numpy.ndarray) → numpy.ndarray¶

Performs multiplication of a graph’s adjacency list representation with a vector.

Args:

graph: The adjacency list of the graph. vector: A 1D numpy array representing the vector to multiply.

Returns:

A numpy array representing the product of the adjacency list and the vector.

Raises:

ValueError: If the vector’s length does not match the number of nodes in the

graph.

>>> multiply_matrix_vector([[1, 2], [0, 2], [0, 1]], np.array([1, 1, 1]))
array([2., 2., 2.])
>>> multiply_matrix_vector([[1, 2], [0, 2], [0, 1]], np.array([0, 1, 0]))
array([1., 0., 1.])

graphs.lanczos_eigenvectors.validate_adjacency_list(graph: list[list[int | None]]) → None¶

Validates the adjacency list format for the graph.

Args:

graph: A list of lists where each sublist contains the neighbors of a node.

Raises:

ValueError: If the graph is not a list of lists, or if any node has

invalid neighbors (e.g., out-of-range or non-integer values).

>>> validate_adjacency_list([[1, 2], [0], [0, 1]])
>>> validate_adjacency_list([[]])  # No neighbors, valid case
>>> validate_adjacency_list([[1], [2], [-1]])  # Invalid neighbor
Traceback (most recent call last):
    ...
ValueError: Invalid neighbor -1 in node 2 adjacency list.