graphs.graph_peripherality

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

find_far_node(→ tuple[int, float])

Identify the node with maximal farness among reachable nodes.

find_peripheral_and_far_node(→ tuple[tuple[int, ...)

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

find_peripheral_node(→ tuple[int, float])

Identify the node with maximal eccentricity among reachable nodes.

floyd_warshall_algorithm(→ numpy.ndarray)

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

get_reachable_distances(→ numpy.ndarray)

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

initialize_distance_matrix(→ numpy.ndarray)

Initialize the distance matrix and validate edge weights.

test_cyclic_graph(→ None)

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

test_directed_acyclic_graph(→ None)

Test a directed acyclic graph (DAG).

test_disconnected_graph(→ None)

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

test_fully_connected_graph(→ None)

Test a fully connected graph.

test_graph_with_negative_weight(→ None)

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

test_graph_with_zero_weight(→ None)

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

test_large_fully_connected_graph(→ None)

Test a larger fully connected graph with random weights.

test_single_node(→ None)

Test a graph with a single node.

test_sparse_graph(→ None)

Test a larger sparse graph.

test_two_nodes_positive_weight(→ None)

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

Module Contents

graphs.graph_peripherality.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.

graphs.graph_peripherality.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).

graphs.graph_peripherality.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.

graphs.graph_peripherality.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.

graphs.graph_peripherality.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).

graphs.graph_peripherality.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.

graphs.graph_peripherality.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)
graphs.graph_peripherality.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)
graphs.graph_peripherality.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)
graphs.graph_peripherality.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)
graphs.graph_peripherality.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.
graphs.graph_peripherality.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.
graphs.graph_peripherality.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
graphs.graph_peripherality.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)
graphs.graph_peripherality.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)
graphs.graph_peripherality.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)