Layout Algorithms

def spring_layout(graph, pos = None, fixed = None, k = None, repulsive_exponent: int = 2, adaptive_cooling: bool = True, num_iter: int = 50, tol: float = 1e-6, weight_fn = None, default_weight: float = 1, scale: float = 1, center = None, seed = None) -> dict:
    """
    Position nodes using Fruchterman-Reingold force-directed algorithm.
    
    Simulates attractive forces between connected nodes and repulsive
    forces between all nodes to achieve balanced, aesthetically pleasing layout.
    
    Parameters:
    - graph: Input graph (PyGraph or PyDiGraph)
    - pos (dict, optional): Initial positions {node_id: (x, y)}
    - fixed (set, optional): Nodes to keep at initial positions
    - k (float, optional): Optimal distance between nodes, default 1/sqrt(n)
    - repulsive_exponent (int): Exponent for repulsive force calculation
    - adaptive_cooling (bool): Use adaptive temperature cooling
    - num_iter (int): Maximum number of iterations
    - tol (float): Convergence tolerance for position changes
    - weight_fn (callable, optional): Function to extract edge weights
    - default_weight (float): Default edge weight for attraction
    - scale (float): Scale factor for final positions
    - center (tuple, optional): Center point (x, y) for layout
    - seed (int, optional): Random seed for initial positions
    
    Returns:
    dict: Mapping of node indices to (x, y) coordinate tuples
    """

def circular_layout(graph, scale: float = 1, center = None):
    """
    Position nodes in circle.
    
    Arranges all nodes evenly spaced around a circle,
    useful for displaying cyclic relationships.
    
    Parameters:
    - graph: Input graph (PyGraph or PyDiGraph)
    - scale (float): Radius scaling factor
    - center (tuple, optional): Center point (x, y), defaults to origin
    
    Returns:
    Pos2DMapping: Mapping of node indices to (x, y) coordinates
    """

def shell_layout(graph, nlist = None, rotate = None, scale: float = 1, center = None):
    """
    Position nodes in concentric circles (shells).
    
    Arranges nodes in multiple circular shells, useful for
    hierarchical visualization and grouped node display.
    
    Parameters:
    - graph: Input graph (PyGraph or PyDiGraph)
    - nlist (list, optional): List of node lists for each shell
    - rotate (float, optional): Rotation angle between shells (radians)
    - scale (float): Overall scaling factor
    - center (tuple, optional): Center point (x, y)
    
    Returns:
    Pos2DMapping: Mapping of node indices to (x, y) coordinates
    """

def spiral_layout(graph, scale: float = 1, center = None, resolution: float = 0.35, equidistant: bool = False):
    """
    Position nodes in spiral pattern.
    
    Arranges nodes along an outward spiral, useful for
    displaying sequential or temporal relationships.
    
    Parameters:
    - graph: Input graph (PyGraph or PyDiGraph)
    - scale (float): Overall scaling factor
    - center (tuple, optional): Center point (x, y)
    - resolution (float): Spiral compactness (lower = more compressed)
    - equidistant (bool): Maintain equal distance between adjacent nodes
    
    Returns:
    Pos2DMapping: Mapping of node indices to (x, y) coordinates
    """

def bipartite_layout(graph, first_nodes, horizontal: bool = False, scale: float = 1, center = None, aspect_ratio: float = 4/3):
    """
    Position nodes for bipartite graph visualization.
    
    Places nodes from each partition on opposite sides,
    clearly showing bipartite structure.
    
    Parameters:
    - graph: Input graph (PyGraph or PyDiGraph)
    - first_nodes (set): Node indices for first partition
    - horizontal (bool): Horizontal layout if True, vertical if False
    - scale (float): Overall scaling factor
    - center (tuple, optional): Center point (x, y)
    - aspect_ratio (float): Width to height ratio
    
    Returns:
    Pos2DMapping: Mapping of node indices to (x, y) coordinates
    """

def random_layout(graph, center = None, seed = None):
    """
    Position nodes randomly.
    
    Useful as starting point for other algorithms or
    for testing layout-independent graph properties.
    
    Parameters:
    - graph: Input graph (PyGraph or PyDiGraph)
    - center (tuple, optional): Center point (x, y)
    - seed (int, optional): Random seed for reproducible layouts
    
    Returns:
    Pos2DMapping: Mapping of node indices to (x, y) coordinates
    """

import rustworkx as rx
import matplotlib.pyplot as plt

# Create sample graph
graph = rx.generators.erdos_renyi_gnp_random_graph(20, 0.3, seed=42)

# Apply spring layout with default parameters
pos = rx.spring_layout(graph, seed=42)

print(f"Positioned {len(pos)} nodes")
print(f"Sample positions: {dict(list(pos.items())[:3])}")

# Plot using matplotlib (if available)
if 'matplotlib' in globals():
    node_x = [pos[node][0] for node in graph.node_indices()]
    node_y = [pos[node][1] for node in graph.node_indices()]
    plt.scatter(node_x, node_y)
    plt.title("Spring Layout")
    plt.axis('equal')
    plt.show()

# Create weighted graph
weighted_graph = rx.PyGraph()
nodes = weighted_graph.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
weighted_graph.add_edges_from([
    (nodes[0], nodes[1], 0.5),  # Weak connection
    (nodes[1], nodes[2], 2.0),  # Strong connection
    (nodes[2], nodes[3], 1.0),  # Medium connection
    (nodes[3], nodes[4], 0.3),  # Very weak connection
    (nodes[0], nodes[4], 1.5),  # Strong connection
])

# Spring layout with edge weights and custom parameters
weighted_pos = rx.spring_layout(
    weighted_graph,
    k=2.0,                    # Larger optimal distance
    weight_fn=lambda x: x,    # Use edge weights
    num_iter=100,             # More iterations
    adaptive_cooling=True,    # Better convergence
    seed=42
)

print("Weighted spring layout positions:")
for i, node_name in enumerate(['A', 'B', 'C', 'D', 'E']):
    x, y = weighted_pos[i]
    print(f"  {node_name}: ({x:.2f}, {y:.2f})")

# Circular layout for cycle graph
cycle = rx.generators.cycle_graph(8)
circular_pos = rx.circular_layout(cycle, scale=2.0)

# Shell layout for hierarchical structure
hierarchical = rx.PyGraph()
# Level 0: root
root = [hierarchical.add_node("Root")]
# Level 1: children  
level1 = hierarchical.add_nodes_from(["Child1", "Child2", "Child3"])
# Level 2: grandchildren
level2 = hierarchical.add_nodes_from(["GC1", "GC2", "GC3", "GC4"])

# Connect hierarchy
for child in level1:
    hierarchical.add_edge(root[0], child, None)
for i, grandchild in enumerate(level2):
    parent = level1[i % len(level1)]  # Distribute grandchildren
    hierarchical.add_edge(parent, grandchild, None)

# Shell layout with explicit shell assignments
shell_pos = rx.shell_layout(
    hierarchical,
    nlist=[root, level1, level2],  # Define shells
    scale=3.0
)

print(f"Circular layout range: x=[{min(pos[0] for pos in circular_pos.values()):.1f}, {max(pos[0] for pos in circular_pos.values()):.1f}]")
print(f"Shell layout has {len(shell_pos)} positioned nodes")

# Create bipartite graph
bipartite = rx.PyGraph()
# Partition A: servers
servers = bipartite.add_nodes_from(["Server1", "Server2", "Server3"])
# Partition B: clients  
clients = bipartite.add_nodes_from(["Client1", "Client2", "Client3", "Client4"])

# Add bipartite edges (only between partitions)
connections = [
    (servers[0], clients[0]),
    (servers[0], clients[2]),
    (servers[1], clients[1]),
    (servers[1], clients[3]),
    (servers[2], clients[0]),
    (servers[2], clients[1])
]
bipartite.add_edges_from([(s, c, None) for s, c in connections])

# Bipartite layout
bip_pos = rx.bipartite_layout(
    bipartite,
    first_nodes=set(servers),  # Left side
    horizontal=True,           # Horizontal arrangement
    scale=4.0
)

print("Bipartite layout:")
print("Servers (left side):")
for server in servers:
    x, y = bip_pos[server]
    print(f"  Node {server}: ({x:.1f}, {y:.1f})")
print("Clients (right side):")
for client in clients:
    x, y = bip_pos[client]
    print(f"  Node {client}: ({x:.1f}, {y:.1f})")

# Spiral layout for sequential data
sequence = rx.generators.path_graph(15)
spiral_pos = rx.spiral_layout(
    sequence,
    scale=2.0,
    resolution=0.3,      # Tighter spiral
    equidistant=True     # Equal spacing
)

# Analyze spiral properties
distances = []
positions = [spiral_pos[i] for i in range(len(spiral_pos))]
for i in range(len(positions) - 1):
    x1, y1 = positions[i]
    x2, y2 = positions[i + 1]
    dist = ((x2 - x1)**2 + (y2 - y1)**2)**0.5
    distances.append(dist)

print(f"Spiral layout: {len(positions)} nodes")
print(f"Average distance between consecutive nodes: {sum(distances)/len(distances):.3f}")
print(f"Distance variation: {max(distances) - min(distances):.3f}")

# Layout with some nodes fixed in position
mixed_graph = rx.generators.complete_graph(6)

# Fix some nodes at specific positions
fixed_positions = {
    0: (0.0, 0.0),    # Center
    1: (2.0, 0.0),    # Right
    2: (-2.0, 0.0),   # Left
}

# Spring layout with fixed nodes
mixed_pos = rx.spring_layout(
    mixed_graph,
    pos=fixed_positions,        # Initial positions
    fixed=set(fixed_positions.keys()),  # Keep these fixed
    num_iter=50,
    seed=42
)

print("Layout with fixed nodes:")
for node in mixed_graph.node_indices():
    x, y = mixed_pos[node]
    status = "FIXED" if node in fixed_positions else "free"
    print(f"  Node {node}: ({x:.2f}, {y:.2f}) [{status}]")

# Compare layouts for the same graph
test_graph = rx.generators.karate_club_graph()

layouts = {
    'spring': rx.spring_layout(test_graph, seed=42),
    'circular': rx.circular_layout(test_graph, scale=2.0),
    'random': rx.random_layout(test_graph, seed=42),
    'spiral': rx.spiral_layout(test_graph, scale=2.0)
}

# Analyze layout properties
for name, pos in layouts.items():
    # Calculate bounding box
    x_coords = [p[0] for p in pos.values()]
    y_coords = [p[1] for p in pos.values()]
    
    width = max(x_coords) - min(x_coords)
    height = max(y_coords) - min(y_coords)
    
    print(f"{name.capitalize()} layout:")
    print(f"  Bounding box: {width:.2f} x {height:.2f}")
    print(f"  Aspect ratio: {width/height:.2f}")

def normalize_layout(pos, target_size=1.0):
    """Normalize layout to fit within target size."""
    if not pos:
        return pos
    
    # Find current bounds
    x_coords = [p[0] for p in pos.values()]
    y_coords = [p[1] for p in pos.values()]
    
    min_x, max_x = min(x_coords), max(x_coords)
    min_y, max_y = min(y_coords), max(y_coords)
    
    # Calculate scaling factor
    current_size = max(max_x - min_x, max_y - min_y)
    if current_size == 0:
        return pos
    
    scale = target_size / current_size
    
    # Center and scale
    center_x = (min_x + max_x) / 2
    center_y = (min_y + max_y) / 2
    
    normalized = {}
    for node, (x, y) in pos.items():
        new_x = (x - center_x) * scale
        new_y = (y - center_y) * scale
        normalized[node] = (new_x, new_y)
    
    return normalized

# Apply custom normalization
raw_layout = rx.spring_layout(test_graph, seed=42)
normalized_layout = normalize_layout(raw_layout, target_size=5.0)

print("Layout normalization:")
print(f"Raw layout range: {max(max(p) for p in raw_layout.values()):.2f}")
print(f"Normalized range: {max(max(abs(coord) for coord in p) for p in normalized_layout.values()):.2f}")

# Efficient layout for larger graphs
large_graph = rx.generators.erdos_renyi_gnp_random_graph(200, 0.02, seed=42)

# Use lower tolerance and fewer iterations for speed
fast_layout = rx.spring_layout(
    large_graph,
    num_iter=30,        # Fewer iterations
    tol=1e-3,          # Lower precision
    adaptive_cooling=True,  # Better convergence
    seed=42
)

# Calculate layout quality metrics
def layout_quality(graph, pos):
    """Simple metric based on edge lengths."""
    edge_lengths = []
    for source, target in graph.edge_list():
        x1, y1 = pos[source]
        x2, y2 = pos[target]
        length = ((x2 - x1)**2 + (y2 - y1)**2)**0.5
        edge_lengths.append(length)
    
    return {
        'mean_edge_length': sum(edge_lengths) / len(edge_lengths),
        'edge_length_std': (sum((l - sum(edge_lengths)/len(edge_lengths))**2 for l in edge_lengths) / len(edge_lengths))**0.5
    }

quality = layout_quality(large_graph, fast_layout)
print(f"Large graph layout ({large_graph.num_nodes()} nodes):")
print(f"  Mean edge length: {quality['mean_edge_length']:.3f}")
print(f"  Edge length std: {quality['edge_length_std']:.3f}")