graphs.graph_peripherality
==========================

.. py:module:: graphs.graph_peripherality

.. autoapi-nested-parse::

   Graph Peripheral and Farness Algorithms for Determining Peripheral and Farthest Nodes
   in a Graph.

   This module provides functions to compute the peripheral and farthest nodes in a
   weighted graph based on graph-theoretical distance measures. The peripheral node
   maximizes the maximum shortest-path distance to all other reachable nodes
   (eccentricity), while the far node maximizes the sum of shortest-path distances to
   all other reachable nodes (farness).

   Problem Description:
   Given a weighted graph G = (V, E), where V is the set of vertices, and E is the set
   of edges with positive weights representing distances between nodes, determine:

   - Peripheral Node: The node with maximal eccentricity. The eccentricity of a node v
     is defined as the greatest distance between v and any other node reachable from v.

   - Far Node: The node with maximal farness. Farness of a node v is the sum of the
     shortest-path distances from v to all other reachable nodes.

   Algorithms Implemented:
   - Floyd-Warshall Algorithm for All-Pairs Shortest Paths.
   - Calculation of Eccentricity and Farness for identifying Peripheral and Far nodes.

   Algorithm Descriptions:

   Floyd-Warshall Algorithm (Pseudo-code):
   ---------------------------------------
   for k from 1 to N:
       for i from 1 to N:
           for j from 1 to N:
               if distance[i][j] > distance[i][k] + distance[k][j]:
                   distance[i][j] = distance[i][k] + distance[k][j]

   Peripheral and Far Node Calculation:
   ------------------------------------
   For each node i:
       - Eccentricity[i] = maximum distance from node i to any other reachable node.
       - Farness[i] = sum of distances from node i to all reachable nodes.

   Select:
       - Peripheral Node: node with maximal eccentricity.
       - Far Node: node with maximal farness.

   References:
   - Floyd-Warshall Algorithm: https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm
   - Eccentricity and Farness: https://en.wikipedia.org/wiki/Distance_(graph_theory)

   Example Application:
   These algorithms can be applied to network analysis, such as identifying the most
   distant nodes within a network, analyzing communication delays, or planning
   infrastructure at the boundaries of a network.



Functions
---------

.. autoapisummary::

   graphs.graph_peripherality.find_far_node
   graphs.graph_peripherality.find_peripheral_and_far_node
   graphs.graph_peripherality.find_peripheral_node
   graphs.graph_peripherality.floyd_warshall_algorithm
   graphs.graph_peripherality.get_reachable_distances
   graphs.graph_peripherality.initialize_distance_matrix
   graphs.graph_peripherality.test_cyclic_graph
   graphs.graph_peripherality.test_directed_acyclic_graph
   graphs.graph_peripherality.test_disconnected_graph
   graphs.graph_peripherality.test_fully_connected_graph
   graphs.graph_peripherality.test_graph_with_negative_weight
   graphs.graph_peripherality.test_graph_with_zero_weight
   graphs.graph_peripherality.test_large_fully_connected_graph
   graphs.graph_peripherality.test_single_node
   graphs.graph_peripherality.test_sparse_graph
   graphs.graph_peripherality.test_two_nodes_positive_weight


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

.. py:function:: find_far_node(farnesses: list[tuple[int, float]]) -> tuple[int, float]

   Identify the node with maximal farness among reachable nodes.

   Args:
       farnesses: List of tuples (node index, farness).

   Returns:
       The node with maximal farness and its value. Returns (-1, inf) if
       no valid nodes are found.


.. py:function:: find_peripheral_and_far_node(distance_matrix: numpy.ndarray) -> tuple[tuple[int, float], tuple[int, float]]

   Determine the peripheral and far nodes based on shortest-path distances.

   For each node, calculates its eccentricity and farness (sum of distances to all
   reachable nodes). Identifies the peripheral node (maximal eccentricity) and
   farthest node (maximal farness).

   Args:
       distance_matrix: A numpy.ndarray representing shortest-path distances
                        between all pairs of nodes.

   Returns:
       A tuple containing:
           - peripheral_node: A tuple (node index, eccentricity) for the node with
             maximal eccentricity.
           - far_node: A tuple (node index, farness) for the node with maximal
             farness (sum of shortest-path distances).


.. py:function:: find_peripheral_node(eccentricities: list[tuple[int, float]]) -> tuple[int, float]

   Identify the node with maximal eccentricity among reachable nodes.

   Args:
       eccentricities: List of tuples (node index, eccentricity).

   Returns:
       The node with maximal eccentricity and its value. Returns (-1, inf) if
       no valid nodes are found.


.. py:function:: floyd_warshall_algorithm(graph: dict[int, list[tuple[int, float]]]) -> numpy.ndarray

   Compute all-pairs shortest paths using the Floyd-Warshall algorithm.

   Floyd-Warshall Complexity:
   --------------------------
   Time Complexity: O(N^3), where N is the number of nodes.
   Space Complexity: O(N^2), for storing the distance matrix.

   Args:
       graph: The graph represented as an adjacency list.

   Returns:
       The distance matrix with the shortest paths between all pairs of nodes.


.. py:function:: get_reachable_distances(distances: numpy.ndarray) -> numpy.ndarray

   Filter reachable distances, excluding infinite values (unreachable nodes).

   Args:
       distances: Array of shortest-path distances from a specific node.

   Returns:
       An array of distances to reachable nodes only (finite values).


.. py:function:: initialize_distance_matrix(graph: dict[int, list[tuple[int, float]]], number_of_nodes: int) -> numpy.ndarray

   Initialize the distance matrix and validate edge weights.

   Args:
       graph: The graph represented as an adjacency list.
       number_of_nodes: The total number of nodes in the graph.

   Returns:
       A numpy.ndarray representing the initialized distance matrix.

   Raises:
       ValueError: If any edge has a non-positive weight.


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

   Test a cyclic graph where there is a cycle between nodes.

   >>> graph = {
   ...     0: [(1, 1.0)],
   ...     1: [(2, 1.0)],
   ...     2: [(0, 1.0)]
   ... }
   >>> distance_matrix = floyd_warshall_algorithm(graph)
   >>> peripheral_node, far_node = find_peripheral_and_far_node(distance_matrix)
   >>> peripheral_node
   (0, 2.0)
   >>> far_node
   (0, 3.0)


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

   Test a directed acyclic graph (DAG).

   >>> graph = {
   ...     0: [(1, 1.0), (2, 2.0)],
   ...     1: [(3, 3.0)],
   ...     2: [(3, 1.0)],
   ...     3: []
   ... }
   >>> distance_matrix = floyd_warshall_algorithm(graph)
   >>> peripheral_node, far_node = find_peripheral_and_far_node(distance_matrix)
   >>> peripheral_node
   (3, inf)
   >>> far_node
   (3, inf)


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

   Test a disconnected graph with nodes that cannot reach each other.

   >>> graph = {
   ...     0: [],
   ...     1: [],
   ...     2: []
   ... }
   >>> distance_matrix = floyd_warshall_algorithm(graph)
   >>> peripheral_node, far_node = find_peripheral_and_far_node(distance_matrix)
   >>> peripheral_node
   (-1, inf)
   >>> far_node
   (-1, inf)


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

   Test a fully connected graph.

   >>> graph = {
   ...     0: [(1, 1.0), (2, 1.0)],
   ...     1: [(0, 1.0), (2, 1.0)],
   ...     2: [(0, 1.0), (1, 1.0)],
   ... }
   >>> distance_matrix = floyd_warshall_algorithm(graph)
   >>> peripheral_node, far_node = find_peripheral_and_far_node(distance_matrix)
   >>> peripheral_node
   (0, 1.0)
   >>> far_node
   (0, 2.0)


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

   Test a graph with negative weight, which should raise a ValueError.

   >>> graph = {0: [(1, -2.0)], 1: []}
   >>> floyd_warshall_algorithm(graph)
   Traceback (most recent call last):
   ...
   ValueError: Edge weight must be positive. Found -2.0 between nodes 0 and 1.


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

   Test a graph with zero weight, which should raise a ValueError.

   >>> graph = {0: [(1, 0.0)], 1: []}
   >>> floyd_warshall_algorithm(graph)
   Traceback (most recent call last):
   ...
   ValueError: Edge weight must be positive. Found 0.0 between nodes 0 and 1.


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

   Test a larger fully connected graph with random weights.

   >>> import random
   >>> random.seed(42)
   >>> number_of_nodes = 10
   >>> graph = {i: [(j, random.uniform(1, 10)) for j in
   ...          range(number_of_nodes) if i != j]
   ...          for i in range(number_of_nodes)}
   >>> distance_matrix = floyd_warshall_algorithm(graph)
   >>> peripheral_node, far_node = find_peripheral_and_far_node(distance_matrix)
   >>> peripheral_node[0] is not None  # Ensure it found a peripheral node
   True
   >>> far_node[0] is not None  # Ensure it found a far node
   True


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

   Test a graph with a single node.

   >>> graph = {0: []}
   >>> distance_matrix = floyd_warshall_algorithm(graph)
   >>> peripheral_node, far_node = find_peripheral_and_far_node(distance_matrix)
   >>> peripheral_node
   (0, 0.0)
   >>> far_node
   (0, 0.0)


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

   Test a larger sparse graph.

   >>> graph = {
   ...     0: [(1, 2.0)],
   ...     1: [(2, 3.0)],
   ...     2: [(3, 4.0)],
   ...     3: [(4, 5.0)],
   ...     4: []
   ... }
   >>> distance_matrix = floyd_warshall_algorithm(graph)
   >>> peripheral_node, far_node = find_peripheral_and_far_node(distance_matrix)
   >>> peripheral_node
   (4, inf)
   >>> far_node
   (4, inf)


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

   Test a graph with two nodes connected by a positive weight.

   >>> graph = {0: [(1, 5.0)], 1: [(0, 5.0)]}
   >>> distance_matrix = floyd_warshall_algorithm(graph)
   >>> peripheral_node, far_node = find_peripheral_and_far_node(distance_matrix)
   >>> peripheral_node
   (0, 5.0)
   >>> far_node
   (0, 5.0)