Clarify a Machine Topology Coding Task

Problem Statement

In large-scale distributed training, accelerators (GPUs/TPUs) are connected via high-speed interconnects. When hardware faults occur or node allocations are dynamic, the physical interconnect fabric can degrade into disconnected sub-graphs with varying topologies.

Write a function analyze_topology(num_nodes: int, edges: list[tuple[int, int]]) -> dict that analyzes an undirected interconnect graph and returns both aggregate summary statistics and structural topology classifications for each connected component.

Each component must be classified into exactly one of the following topology types:

• "singleton": A component with exactly 1 node.
• "clique": A component with k >= 2 nodes where every node is directly connected to every other node in the component.
• "ring": A component with k >= 3 nodes where every node has degree exactly 2.
• "linear": A component with k >= 2 nodes that forms a simple path (two nodes have degree 1, all others have degree 2). Note: a 2-node component is classified as a "clique" (or 2-clique), not linear.
• "star": A component with k >= 4 nodes where one center node has degree k - 1 and all other k - 1 nodes have degree 1. (A 3-node star is identical to a 3-node linear path, which must be classified as "linear").
• "other": Any connected component that does not match the criteria above.

Function Signature

def analyze_topology(num_nodes: int, edges: list[tuple[int, int]]) -> dict:
    """
    Analyzes the accelerator network topology.

    Returns:
      {
        "component_count": int,
        "components": list[dict] # sorted by min node_id ascending
      }
    where each component dict contains:
      {
        "nodes": list[int],       # sorted in ascending order
        "topology": str,          # "singleton" | "clique" | "ring" | "linear" | "star" | "other"
        "diameter": int           # maximum shortest-path distance between any pair (0 for singleton)
      }
    """

Constraints

• 1 <= num_nodes <= 2000
• 0 <= len(edges) <= 10000
• 0 <= u, v < num_nodes for each edge (u, v)
• Edges are undirected. Input may contain duplicate edges or self-loops; duplicate edges should be treated as a single edge, and self-loops should be ignored.

Examples

# Example 1
num_nodes = 5
edges = [(0, 1), (1, 2), (2, 0), (3, 4)]

# Output:
# {
#   "component_count": 2,
#   "components": [
#     {"nodes": [0, 1, 2], "topology": "clique", "diameter": 1},
#     {"nodes": [3, 4], "topology": "clique", "diameter": 1}
#   ]
# }

# Example 2
num_nodes = 4
edges = [(0, 1), (1, 2), (2, 3)]

# Output:
# {
#   "component_count": 1,
#   "components": [
#     {"nodes": [0, 1, 2, 3], "topology": "linear", "diameter": 3}
#   ]
# }

Edge Cases

• Isolated nodes (num_nodes > 0, edges = []).
• Disconnected graph with mixed sub-graphs.
• Redundant parallel edges or self-loops.