graphs.graph_centrality
=======================

.. py:module:: graphs.graph_centrality

.. autoapi-nested-parse::

   Graph Centrality Algorithms for Determining Central and Median Nodes in a Graph.

   This module provides functions to compute the central and median nodes in a weighted
   graph based on graph-theoretical centrality measures. The central node minimizes the
   maximum shortest-path distance to all other reachable nodes (eccentricity), while the
   median node maximizes the sum of the reciprocals of the shortest-path distances to all
   other reachable nodes (harmonic closeness centrality).

   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:

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

   - Median Node: The node with maximal harmonic closeness centrality. The harmonic
     closeness centrality of a node v is the sum of the reciprocals 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 Harmonic Closeness Centrality.

   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]

   Central and Median Node Calculation:
   ------------------------------------
   For each node i:
       - Eccentricity[i] = maximum distance from node i to any other reachable node.
       - Closeness[i] = sum of reciprocals of distances from node i to all reachable nodes.

   Select:
       - Central Node: node with minimal eccentricity.
       - Median Node: node with maximal closeness.

   References:
   - https://en.wikipedia.org/wiki/Centrality
   - Floyd-Warshall Algorithm: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
   - Closeness Centrality: https://en.wikipedia.org/wiki/Closeness_centrality

   Example Application:
   These algorithms can be applied to real-world problems, such as determining the optimal
   location for facilities (e.g., emergency response centers) to minimize response times
   within a network. By identifying the central or median nodes, organizations can make
   informed decisions on resource placement to improve efficiency and accessibility.



Functions
---------

.. autoapisummary::

   graphs.graph_centrality.find_central_and_median_node
   graphs.graph_centrality.find_central_node
   graphs.graph_centrality.find_median_node
   graphs.graph_centrality.floyd_warshall_algorithm
   graphs.graph_centrality.get_reachable_distances
   graphs.graph_centrality.initialize_distance_matrix
   graphs.graph_centrality.test_cyclic_graph
   graphs.graph_centrality.test_directed_acyclic_graph
   graphs.graph_centrality.test_disconnected_graph
   graphs.graph_centrality.test_fully_connected_graph
   graphs.graph_centrality.test_graph_with_negative_weight
   graphs.graph_centrality.test_graph_with_zero_weight
   graphs.graph_centrality.test_large_fully_connected_graph
   graphs.graph_centrality.test_single_node
   graphs.graph_centrality.test_sparse_graph
   graphs.graph_centrality.test_two_nodes_positive_weight


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

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

   Determine the central and median nodes based on shortest-path distances.

   For each node, calculates its eccentricity and harmonic closeness centrality,
   considering only reachable nodes. Then, identifies the central node (minimal
   eccentricity) and median node (maximal closeness).

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

   Returns:
       A tuple containing:
           - central_node: A tuple (node index, eccentricity) for the node with
             minimal eccentricity.
           - median_node: A tuple (node index, closeness) for the node with maximal
             harmonic closeness centrality.


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

   Identify the node with minimal eccentricity among reachable nodes.

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

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


.. py:function:: find_median_node(closenesses: list[tuple[int, float]]) -> tuple[int, float]

   Identify the node with maximal closeness among reachable nodes.

   Args:
       closenesses: List of tuples (node index, closeness centrality).

   Returns:
       The node with maximal closeness 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)
   >>> central_node, median_node = find_central_and_median_node(distance_matrix)
   >>> central_node
   (0, 2.0)
   >>> median_node
   (0, 1.5)


.. 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)
   >>> central_node, median_node = find_central_and_median_node(distance_matrix)
   >>> central_node
   (2, 1.0)
   >>> median_node
   (0, 1.8333333333333333)


.. 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)
   >>> central_node, median_node = find_central_and_median_node(distance_matrix)
   >>> central_node
   (-1, inf)
   >>> median_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)
   >>> central_node, median_node = find_central_and_median_node(distance_matrix)
   >>> central_node
   (0, 1.0)
   >>> median_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)
   >>> central_node, median_node = find_central_and_median_node(distance_matrix)
   >>> central_node[0] is not None  # Ensure it found a central node
   True
   >>> median_node[0] is not None  # Ensure it found a median node
   True


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

   Test a graph with a single node.

   >>> graph = {0: []}
   >>> distance_matrix = floyd_warshall_algorithm(graph)
   >>> central_node, median_node = find_central_and_median_node(distance_matrix)
   >>> central_node
   (0, 0.0)
   >>> median_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)
   >>> central_node, median_node = find_central_and_median_node(distance_matrix)
   >>> central_node
   (3, 5.0)
   >>> median_node
   (0, 0.8825396825396825)


.. 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)
   >>> central_node, median_node = find_central_and_median_node(distance_matrix)
   >>> central_node
   (0, 5.0)
   >>> median_node
   (0, 0.2)