gistfile1.txt

import random
import math
import matplotlib.pyplot as plt
import networkx as nx

def generate_star_graph_edges(K, N):
    edges = []
    central_node = "C"
    for i in range(K):
        prev = central_node
        for j in range(1, N + 1):
            node = f"L{i}_{j}"
            edges.append((prev, node))
            prev = node
    return edges, central_node

def random_rename_edges(edges, central_node):
    nodes = {u for edge in edges for u in edge}
    random_labels = random.sample(range(1000, 9999), len(nodes))
    name_map = dict(zip(nodes, random_labels))
    renamed_edges = [(name_map[u], name_map[v]) for u, v in edges]
    renamed_central = name_map[central_node]
    return renamed_edges, name_map, renamed_central

def radial_layout(name_map, central_node, K, N, radius_step=3.0):
    pos = {}
    angle_step = 2 * math.pi / K
    pos[central_node] = (0, 0)

    for i in range(K):
        angle = i * angle_step
        for j in range(1, N + 1):
            node_label = f"L{i}_{j}"
            node = name_map[node_label]
            r = j * radius_step
            x = r * math.cos(angle)
            y = r * math.sin(angle)
            pos[node] = (x, y)

    return pos

def plot_graph(edges, pos, central_node, target_leaf, title="Star Graph with Target Highlighted"):
    G = nx.Graph()
    G.add_edges_from(edges)

    node_colors = []
    for node in G.nodes():
        if node == central_node:
            node_colors.append('orange')
        elif node == target_leaf:
            node_colors.append('red')
        else:
            node_colors.append('skyblue')

    plt.figure(figsize=(10, 10))
    nx.draw(G, pos, with_labels=True, node_color=node_colors,
            edge_color='gray', node_size=1000, font_size=10, font_weight='bold')
    plt.title(title)
    plt.axis('off')
    plt.tight_layout()
    plt.show()

def find_path(edges, start, end):
    G = nx.Graph()
    G.add_edges_from(edges)
    try:
        return nx.shortest_path(G, source=start, target=end)
    except nx.NetworkXNoPath:
        return None

# Parameters
K = 8
N = 10
radius_step = 3.0

# Step 1: Generate and rename
original_edges, central_node = generate_star_graph_edges(K, N)
renamed_edges, name_map, renamed_central = random_rename_edges(original_edges, central_node)

# Step 2: Pick a random leaf node
leaf_nodes = [name_map[f"L{i}_{N}"] for i in range(K)]
random_leaf = random.choice(leaf_nodes)

# Step 3: Layout and plot
pos = radial_layout(name_map, renamed_central, K, N, radius_step=radius_step)
plot_graph(renamed_edges, pos, central_node=renamed_central, target_leaf=random_leaf)

# Step 4: Print prompt and solve
print("I will give you the edge list of a star graph and I want you to find a path from the center node to a leaf node")
for u, v in renamed_edges:
    print(f"({u}, {v})")

print(f"\nShow me a valid path from {renamed_central} to {random_leaf}:")

path = find_path(renamed_edges, renamed_central, random_leaf)
if path:
    print("Valid path found:")
    print(" -> ".join(str(node) for node in path))
else:
    print("No path found.")