#（参考）一筆書きのコード
import networkx as nx
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML
import time

# --- 1. グラフの定義 ---
# 画像のグラフ構造を再現
G = nx.Graph()
edges = [
    (1, 2), (1, 3), (1, 4),
    (2, 3), (2, 4),
    (3, 4), (3, 5),
    (4, 5)
]
G.add_edges_from(edges)

# ノードの固定位置（画像に近づける）
pos = {
    1: (0, 1),   # 左上
    2: (0, 0),   # 左下
    3: (1, 1),   # 中上
    4: (1, 0),   # 中下
    5: (1.5, 0.5) # 右
}

# --- 2. 一筆書き判定と経路計算 ---
degrees = dict(G.degree())
odd_nodes = [node for node, deg in degrees.items() if deg % 2 != 0]
num_odd = len(odd_nodes)

is_possible = False
euler_path = []

if nx.is_connected(G) and (num_odd == 0 or num_odd == 2):
    is_possible = True
    # 奇数次のノードがある場合は、そこからスタートする
    start_node = odd_nodes[0] if odd_nodes else 1
    # 経路を計算 (Hierholzerのアルゴリズム)
    euler_path = list(nx.eulerian_path(G, source=start_node))

# --- 3. 視覚化（アニメーション）のセットアップ ---
fig, ax = plt.subplots(figsize=(8, 6))

def update(step):
    ax.clear()  # 画面を一度クリア
    plt.axis('off')

    # タイトルの設定
    if not is_possible:
        ax.set_title(f"判定: 一筆書き不可 (奇数次のノードが {num_odd} 個)", fontsize=15, color='red')
        # 不可の場合でもグラフ自体は描画
        nx.draw_networkx_nodes(G, pos, node_color='orange', node_size=1000, ax=ax)
        nx.draw_networkx_labels(G, pos, font_size=12, font_family='sans-serif', ax=ax)
        nx.draw_networkx_edges(G, pos, edge_color='gray', width=2, ax=ax)
        return

    # 一筆書き可能な場合の描画
    total_steps = len(euler_path)
    current_edge_idx = step % (total_steps + 1) # ループさせるため

    # タイトル
    if current_edge_idx == 0:
        title_text = f"判定: 一筆書き可能！\nスタート準備 (ノード {euler_path[0][0]} から)"
    elif current_edge_idx <= total_steps:
        u, v = euler_path[current_edge_idx - 1]
        title_text = f"判定: 一筆書き可能！\nステップ {current_edge_idx}/{total_steps}: {u} -> {v}"
    else:
         title_text = "判定: 一筆書き可能！\n完了！"
    ax.set_title(title_text, fontsize=14, color='green')

    # 基本のグラフ（薄い灰色）
    nx.draw_networkx_nodes(G, pos, node_color='orange', node_size=1000, ax=ax)
    nx.draw_networkx_labels(G, pos, font_size=12, font_family='sans-serif', ax=ax)
    nx.draw_networkx_edges(G, pos, edge_color='lightgray', width=2, style='dashed', ax=ax)

    # 通過済みの経路（青色）
    if current_edge_idx > 1:
        past_edges = euler_path[:current_edge_idx-1]
        nx.draw_networkx_edges(G, pos, edgelist=past_edges, edge_color='blue', width=3, ax=ax)

    # 現在通っている辺（赤色・太線・矢印）
    if 0 < current_edge_idx <= total_steps:
        current_edge = [euler_path[current_edge_idx - 1]]
        # 矢印を描画するためにDiGraphに変換
        ED = nx.DiGraph()
        ED.add_edges_from(current_edge)
        nx.draw_networkx_edges(ED, pos, edgelist=current_edge, edge_color='red', width=5, arrows=True, arrowsize=30, ax=ax)

# アニメーションの作成
# framesを total_steps + 2 (準備と完了画面) に設定
frames = len(euler_path) + 2 if is_possible else 1
ani = animation.FuncAnimation(fig, update, frames=frames, interval=1000, repeat=True)

# Jupyter/Colabで表示するための処理
plt.close() # 最初の静止画を消す
HTML(ani.to_jshtml()) # JavaScriptベースのアニメーションとして出力