graphs.lanczos_eigenvectors
===========================

.. py:module:: graphs.lanczos_eigenvectors

.. autoapi-nested-parse::

   Lanczos Method for Finding Eigenvalues and Eigenvectors of a Graph.

   This module demonstrates the Lanczos method to approximate the largest eigenvalues
   and corresponding eigenvectors of a symmetric matrix represented as a graph's
   adjacency list. The method efficiently handles large, sparse matrices by converting
   the graph to a tridiagonal matrix, whose eigenvalues and eigenvectors are then
   computed.

   Key Functions:
   - `find_lanczos_eigenvectors`: Computes the k largest eigenvalues and vectors.
   - `lanczos_iteration`: Constructs the tridiagonal matrix and orthonormal basis vectors.
   - `multiply_matrix_vector`: Multiplies an adjacency list graph with a vector.

   Complexity:
   - Time: O(k * n), where k is the number of eigenvalues and n is the matrix size.
   - Space: O(n), due to sparse representation and tridiagonal matrix structure.

   Further Reading:
   - Lanczos Algorithm: https://en.wikipedia.org/wiki/Lanczos_algorithm
   - Eigenvector Centrality: https://en.wikipedia.org/wiki/Eigenvector_centrality

   Example Usage:
   Given a graph represented by an adjacency list, the `find_lanczos_eigenvectors`
   function returns the largest eigenvalues and eigenvectors. This can be used to
   analyze graph centrality.



Functions
---------

.. autoapisummary::

   graphs.lanczos_eigenvectors.find_lanczos_eigenvectors
   graphs.lanczos_eigenvectors.lanczos_iteration
   graphs.lanczos_eigenvectors.main
   graphs.lanczos_eigenvectors.multiply_matrix_vector
   graphs.lanczos_eigenvectors.validate_adjacency_list


Module Contents
---------------

.. py:function:: 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


.. py:function:: 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


.. py:function:: main() -> None

   Main driver function for testing the implementation with doctests.


.. py:function:: 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.])


.. py:function:: 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.