Pythonで最も難しい大学入試のアプリを作る話

# はじめに
![スクリーンショット 2024-11-18 233623.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3885292/67ac84dc-abef-5ea8-b838-57ed193d2188.png)
![todai-math1.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3885292/4a0fd590-2468-2f68-3815-46d59e266b57.jpeg)


今回の記事では、Pythonを使って最も難しい大学入試と言われる1998年東京大学後期理系数学第3問のグラフ理論を用いた問題のルールに沿ったアプリを実装したというのを要件定義から実装までを解説しようと考えます。

# グラフ作成アプリケーションの設計仕様

## 1. 要件定義

### 機能要件
1. モードによる操作の切り替え
2. 選択ノードと新規ノードをエッジで接続
3. ノード選択時の視覚的フィードバック（色反転）
4. 2ノード間への新規ノード挿入機能

### 非機能要件
1. ユーザーフレンドリーなUI
2. 視覚的な分かりやすさ
3. 直感的な操作性
4. システムの安定性

## 2. 仕様策定

### GUI/メニュー仕様
1. 操作機能
   - ノード追加モード
   - ノード挿入モード
2. 編集機能
   - Undo/Redo
   - リセット機能
3. プルダウンメニューでの機能切替

### 描画/UI仕様
1. ノード操作の視覚化
   - ホバー時：赤色表示
   ![スクリーンショット 2024-11-19 203838.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3885292/fab8cf84-1476-24d2-e643-d1e0677d9565.png)

   - 選択時（挿入モード）：青色表示
   ![スクリーンショット 2024-11-19 203919.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3885292/cc51a5f4-f401-996c-2db2-3397264a7064.png)

   - 通常時：白黒表示
2. 高コントラストな白背景デザイン

## 3.実装
上記の通りに、Pythonでコードを書いて実装します。

### 3.1使用するライブラリ
- networkx

    概要: networkx は、ネットワークやグラフ構造を扱うためのPythonライブラリです。グラフは、ノード（点）とエッジ（線）で構成されるデータ構造であり、ネットワークの構造を表現するのに適しています。
    
    主な機能:
        グラフ（有向・無向）の作成と操作
        グラフアルゴリズムの実装（最短経路探索、最小全域木、クリーク検出など）
        グラフの描画（matplotlibとの統合）
        ノード間の関係や構造解析（中央性、クラスタリング係数、コミュニティ検出など）

用途: ソーシャルネットワーク解析、通信ネットワーク、経路探索など、グラフ構造を扱うアプリケーション全般で利用されます。

- matplotlib.pyplot

    概要: matplotlib はPythonの2Dグラフ描画ライブラリで、その中でも pyplot モジュールは簡単にプロットを作成するためのインターフェースを提供します。データの可視化に非常に優れています。
    
    主な機能:
        折れ線グラフ、散布図、棒グラフ、ヒストグラム、箱ひげ図など多種多様なグラフの作成
        グラフのスタイル設定（色、線、ラベル、タイトルなど）
        描画の保存や表示

用途: データの視覚化や分析結果のプレゼンテーションに使われ、科学技術計算や機械学習、統計分析などで広く利用されます。

- matplotlib.backends.backend_tkagg.FigureCanvasTkAgg

    概要: FigureCanvasTkAgg は、matplotlib の描画キャンバスを Tkinter（Pythonの標準GUIライブラリ）のウィンドウ内に埋め込むためのクラスです。これにより、Tkinterアプリケーション内でmatplotlibのグラフを表示できます。
    
    主な機能:
        Tkinterのウィジェットとしてmatplotlibのプロットを表示する
        描画をGUIとインタラクティブに操作可能にする

用途: Tkinterベースのデスクトップアプリケーションにおいて、動的なデータの可視化を行う場面で使われます。

- tkinter

    概要: tkinter はPythonに組み込まれている標準GUIライブラリで、ウィンドウベースのアプリケーションを作成するためのツールを提供します。
    
    主な機能:
        ボタン、ラベル、エントリー、リストボックスなどの基本的なウィジェットの提供
        レイアウト管理、イベント処理、ウィンドウ管理の機能

用途: シンプルなデスクトップアプリケーションを開発する際に広く使われます。

- tkinter.messagebox

    概要: tkinter.messagebox は、Tkinterで使用できるメッセージボックスを作成するためのサブモジュールです。ユーザーに情報を表示したり、質問形式のダイアログを提供できます。
    
    主な機能:
        showinfo: 情報メッセージボックス
        showwarning: 警告メッセージボックス
        showerror: エラーメッセージボックス
        askquestion, askokcancel: 質問ダイアログ

用途: GUIアプリケーションにおいて、ユーザーとの対話を行うためのメッセージ表示に利用されます。

- numpy

    概要: numpy は数値計算のためのライブラリで、高速な配列（ndarray）を使って効率的な数値計算を行えます。多次元配列の操作や線形代数、フーリエ変換、乱数生成など、科学技術計算に必要な機能が多数揃っています。
    
    主な機能:
        高速な配列演算（ベクトル・行列演算）
        線形代数、統計、乱数生成
        配列のスライス、ブロードキャスティングなどの便利な機能

用途: 機械学習、データサイエンス、統計解析、画像処理など、数値計算が必要な場面で頻繁に使用されます。

### 3.2コードにして実装
　実際に仕様策定に基づき実装していきます。以下はその例です。
```graph.py
import networkx as nx
import matplotlib.pyplot as plt
from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg
import tkinter as tk
from tkinter import messagebox
import numpy as np

class GraphApp:
    def __init__(self, root):
        self.root = root
        self.root.title("1998年東京大学後期理系数学第3問のグラフ理論")

        # 初期グラフを作成（ノード1を白で追加）
        self.G = nx.Graph()
        self.G.add_node(1, pos=(0, 0), state=0)  # 初期ノードの状態は0（白）
        self.selected_node = None  # 選択されたノードを追跡
        self.hovered_node = None   # ホバーされたノードを追跡
        self.mode = "add_node"     # 操作モード（"add_node" または "insert_node_between"）

        # 操作履歴管理（Undo/Redo用）
        self.history = []
        self.redo_stack = []

        # Tkinterレイアウトの設定
        self.canvas = tk.Canvas(root)
        self.canvas.pack(side=tk.TOP, fill=tk.BOTH, expand=True)

        # グラフ描画用のmatplotlib Figure
        self.fig, self.ax = plt.subplots(figsize=(6, 6))
        self.canvas_plot = FigureCanvasTkAgg(self.fig, master=self.canvas)
        self.canvas_plot.get_tk_widget().pack(side=tk.TOP, fill=tk.BOTH, expand=True)

        self.setup_menu()

        # クリックイベントとホバーイベントのバインディング
        self.canvas_plot.mpl_connect("button_press_event", self.on_click)
        self.canvas_plot.mpl_connect("motion_notify_event", self.on_hover)

        self.draw_graph()

    def setup_menu(self):
        """ メニューバーの設定 """
        menubar = tk.Menu(self.root)

        # 操作メニュー
        operation_menu = tk.Menu(menubar, tearoff=0)
        operation_menu.add_command(label="ノードを追加", command=self.set_add_node_mode, accelerator="Ctrl+N")
        operation_menu.add_command(label="間にノードを追加", command=self.set_insert_node_mode, accelerator="Ctrl+B")
        menubar.add_cascade(label="操作", menu=operation_menu)

        # 編集メニュー
        edit_menu = tk.Menu(menubar, tearoff=0)
        edit_menu.add_command(label="リセット", command=self.reset_graph, accelerator="Ctrl+D")
        edit_menu.add_command(label="Undo", command=self.undo, accelerator="Ctrl+Z")
        edit_menu.add_command(label="Redo", command=self.redo, accelerator="Ctrl+Y")
        menubar.add_cascade(label="編集", menu=edit_menu)

        # メニューバーを表示
        self.root.config(menu=menubar)

        # ショートカットキーの設定
        self.root.bind("<Control-n>", lambda event: self.set_add_node_mode())
        self.root.bind("<Control-b>", lambda event: self.set_insert_node_mode())
        self.root.bind("<Control-d>", lambda event: self.reset_graph())
        self.root.bind("<Control-z>", lambda event: self.undo())
        self.root.bind("<Control-y>", lambda event: self.redo())

    def set_add_node_mode(self):
        """ ノード追加モードに切り替え """
        self.mode = "add_node"
        self.selected_node = None
        self.draw_graph()  # ハイライトが残らないように再描画

    def set_insert_node_mode(self):
        """ ノード間挿入モードに切り替え """
        self.mode = "insert_node_between"
        self.selected_node = None
        self.draw_graph()  # ハイライトが残らないように再描画

    def draw_graph(self):
        """ グラフを描画 """
        self.ax.clear()  # 以前のグラフをクリア
        pos = nx.get_node_attributes(self.G, 'pos')

        # ノードの状態に基づいて色を決定
        colors = []
        for node in self.G.nodes:
            if node == self.hovered_node:
                colors.append('red')  # ホバーされているノードは赤
            elif node == self.selected_node:
                colors.append('blue')  # 選択されたノードは青
            else:
                # ノードの状態（0=白、1=黒）に基づいて色を設定
                state = self.G.nodes[node]['state']
                colors.append('white' if state == 0 else 'black')

        # ノードを描画（白いノードには黒い枠をつける）
        nx.draw(self.G, pos, with_labels=False, node_color=colors, node_size=500, font_size=16, 
                edgecolors='black')  # 黒い枠

        # ノードラベルの描画
        labels = {node: node for node in self.G.nodes}
        label_colors = {node: 'white' if self.G.nodes[node]['state'] == 1 else 'black' for node in self.G.nodes}
        nx.draw_networkx_labels(self.G, pos, labels=labels, font_color=label_colors)

        # 描画の更新
        self.canvas_plot.draw()

    def add_node_with_branch(self, selected_node):
        """ 選択されたノードから新しいノードを追加 """
        pos = nx.get_node_attributes(self.G, 'pos')
        x, y = pos[selected_node]

        # 新しいノードの位置をランダムに計算
        angle = np.random.uniform(0, 2 * np.pi)
        r = 1
        new_x = x + r * np.cos(angle)
        new_y = y + r * np.sin(angle)

        # 新しいノードを追加（状態は白）
        new_node = len(self.G.nodes) + 1
        self.G.add_node(new_node, pos=(new_x, new_y), state=0)  # 新しいノードは状態0（白）
        self.G.add_edge(selected_node, new_node)

        # 選択されたノードの色を反転
        self.flip_state(selected_node)

        # グラフを再描画
        self.draw_graph()

    def insert_node_between(self, node1, node2):
        """ 2つのノードの間に新しいノードを挿入 """
        if self.G.has_edge(node1, node2):
            pos1 = self.G.nodes[node1]['pos']
            pos2 = self.G.nodes[node2]['pos']
            mid_pos = [(p1 + p2) / 2 for p1, p2 in zip(pos1, pos2)]

            # エッジを削除し、新しいノードを追加
            self.G.remove_edge(node1, node2)
            new_node = len(self.G.nodes) + 1
            self.G.add_node(new_node, pos=mid_pos, state=0)  # 新しいノードは状態0（白）
            self.G.add_edge(node1, new_node)
            self.G.add_edge(new_node, node2)

            # 両端のノードの色を反転
            self.flip_state(node1)
            self.flip_state(node2)

            self.draw_graph()

    def flip_state(self, node):
        """ ノードの状態を反転（0→1または1→0） """
        current_state = self.G.nodes[node]['state']
        self.G.nodes[node]['state'] = 1 - current_state  # 状態を反転

    def on_hover(self, event):
        """ ホバーイベント処理（ノードのハイライト表示） """
        if event.xdata is None or event.ydata is None or len(self.G.nodes) == 0:
            return  # 無効なホバーやノードがない場合は無視

        nearest_node = self.find_nearest_node(event.xdata, event.ydata)
        if nearest_node != self.hovered_node:  # 別のノードにホバーしている場合
            self.hovered_node = nearest_node

        # グラフを再描画して変更を反映
        self.draw_graph()

    def on_click(self, event):
        """ クリックイベント処理（ノードの追加・挿入） """
        if event.xdata is None or event.ydata is None:
            return  # 無効なクリックは無視

        if self.mode == "add_node":
            if self.selected_node is None:  # ノードを選択
                self.selected_node = self.find_nearest_node(event.xdata, event.ydata)
            else:  # 選択されたノードから新しいノードを追加
                self.add_node_with_branch(self.selected_node)
                self.selected_node = None

        elif self.mode == "insert_node_between":
            if self.selected_node is None:  # 最初のノードを選択
                self.selected_node = self.find_nearest_node(event.xdata, event.ydata)
            else:  # 2つ目のノードを選択して、その間にノードを挿入
                second_node = self.find_nearest_node(event.xdata, event.ydata)
                if not self.G.has_edge(self.selected_node, second_node):
                    messagebox.showerror("エラー", "選択したノードの間にエッジが存在しません")
                else:
                    self.insert_node_between(self.selected_node, second_node)
                self.selected_node = None

        # 操作履歴を更新し、redoスタックをクリア
        self.history.append(self.G.copy())
        self.redo_stack.clear()

        # グラフを再描画
        self.draw_graph()

    def find_nearest_node(self, x, y, threshold=0.05):
        """ マウス位置に最も近いノードを見つけ、一定の距離以内なら返す """
        pos = nx.get_node_attributes(self.G, 'pos')
    
        # ノードとマウスの距離を計算し、最も近いノードを見つける
        nearest_node = min(self.G.nodes, key=lambda n: np.linalg.norm(np.array(pos[n]) - np.array([x, y])))
    
        # 最近接ノードとの距離を計算
        distance = np.linalg.norm(np.array(pos[nearest_node]) - np.array([x, y]))
    
        # 閾値よりも近い場合のみノードを返す。それ以外は None を返す
        if distance <= threshold:
            return nearest_node
        else:
            return None

    def reset_graph(self):
        """ グラフを初期状態にリセット """
        self.G.clear()  # すべてのノードとエッジを削除
        self.G.add_node(1, pos=(0, 0), state=0)  # 初期ノードを追加（状態0=白）

        # 操作履歴とredoスタックをクリア
        self.history.clear()
        self.redo_stack.clear()

        # ホバーと選択されたノードをリセット
        self.hovered_node = None
        self.selected_node = None

        # グラフを再描画
        self.draw_graph()

    def undo(self):
        """ 最後の操作を元に戻す """
        if self.history:
            self.redo_stack.append(self.G.copy())
            self.G = self.history.pop()
            self.draw_graph()

    def redo(self):
        """ 最後の元に戻した操作をやり直す """
        if self.redo_stack:
            self.history.append(self.G.copy())
            self.G = self.redo_stack.pop()
            self.draw_graph()

# Tkinterアプリケーションの実行
root = tk.Tk()
app = GraphApp(root)
root.mainloop()
```

## 4.実装のポイント
### 4.1グラフ構造の操作性
ノードとエッジを自由に追加・挿入できる機能を備えた。グラフの構造を視覚的に編集できるため、要素間の関係性を簡単に表現できるようにした。
### 4.2視覚的なフィードバック
ノードの状態は色で区別した。ホバー時は赤、選択時は青と、操作状態が一目で分かるようにした。
### 4.3直感的な操作
マウスでの操作を基本とし、クリックやホバーで簡単にグラフを編集できるようにした。近くのノードが強調表示されるため、操作ミスも防げるようにした。
### 4.4操作の履歴管理
Undo/Redo機能で操作を取り消したり、やり直したりできるようにした。気軽に試行錯誤できる環境を整えた。
### 4.5データ構造の視覚化
NetworkXとMatplotlibを使って、グラフ構造を見やすく表示するようにした。理論的な概念も視覚的に理解しやすくした。
### 4.6使いやすいUI
メニューバーやショートカットキーを備えたGUIで、複雑なグラフ操作も手軽に実行できるようにした。

## 5.まとめ
前二作品

https://qiita.com/Wing2C1/items/796192eceac90aa89693

https://qiita.com/Wing2C1/items/22c5c481075401eed4fd

のように堅苦しく書くのに疲れてきました（笑）
とりあえず、三回目となるためまとめとしてはプログラマとしてしっかり作品を残す際には要件定義からやると楽々に作業を進めることができるということです。Pythonには豊富なライブラリがあるため、そこまで大きなアプリケーションではない今回のような単発ネタだったらおすすめです。大きくなると、こんなインタプリタ型ではなくコンパイル型の言語(C/C++など)を使用しましょう。Xのフォローもお願いします。

https://x.com/Wing2C1

## 6.exe化したものの配布

https://drive.google.com/drive/folders/12JS-1oNkJe3jvxdaLBqzQfdIrI_MuJua

手順は下記に記します。
　・すべてダウンロード
　・ファイルを展開
　・distファイルを開く
　・mainファイルを開く
　・main.exeを起動

## 8.コメント対応:実装

　実際に私はプログラミングが全然できない方です。そのため、指摘事項、改善の内容があるならば、コメント欄を参照ください。
全体
![スクリーンショット 2024-11-18 233623.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3885292/67ac84dc-abef-5ea8-b838-57ed193d2188.png)
![todai-math1.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3885292/4a0fd590-2468-2f68-3815-46d59e266b57.jpeg)
   ![スクリーンショット 2024-11-19 203838.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3885292/fab8cf84-1476-24d2-e643-d1e0677d9565.png)
   ![スクリーンショット 2024-11-19 203919.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3885292/cc51a5f4-f401-996c-2db2-3397264a7064.png)
```graph.py
import networkx as nx
import matplotlib.pyplot as plt
from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg
import tkinter as tk
from tkinter import messagebox
import numpy as np

class GraphApp:
    def __init__(self, root):
        self.root = root
        self.root.title("1998年東京大学後期理系数学第3問のグラフ理論")

        # 初期グラフを作成（ノード1を白で追加）
        self.G = nx.Graph()
        self.G.add_node(1, pos=(0, 0), state=0)  # 初期ノードの状態は0（白）
        self.selected_node = None  # 選択されたノードを追跡
        self.hovered_node = None   # ホバーされたノードを追跡
        self.mode = "add_node"     # 操作モード（"add_node" または "insert_node_between"）

        # 操作履歴管理（Undo/Redo用）
        self.history = []
        self.redo_stack = []

        # Tkinterレイアウトの設定
        self.canvas = tk.Canvas(root)
        self.canvas.pack(side=tk.TOP, fill=tk.BOTH, expand=True)

        # グラフ描画用のmatplotlib Figure
        self.fig, self.ax = plt.subplots(figsize=(6, 6))
        self.canvas_plot = FigureCanvasTkAgg(self.fig, master=self.canvas)
        self.canvas_plot.get_tk_widget().pack(side=tk.TOP, fill=tk.BOTH, expand=True)

        self.setup_menu()

        # クリックイベントとホバーイベントのバインディング
        self.canvas_plot.mpl_connect("button_press_event", self.on_click)
        self.canvas_plot.mpl_connect("motion_notify_event", self.on_hover)

        self.draw_graph()

    def setup_menu(self):
        """ メニューバーの設定 """
        menubar = tk.Menu(self.root)

        # 操作メニュー
        operation_menu = tk.Menu(menubar, tearoff=0)
        operation_menu.add_command(label="ノードを追加", command=self.set_add_node_mode, accelerator="Ctrl+N")
        operation_menu.add_command(label="間にノードを追加", command=self.set_insert_node_mode, accelerator="Ctrl+B")
        menubar.add_cascade(label="操作", menu=operation_menu)

        # 編集メニュー
        edit_menu = tk.Menu(menubar, tearoff=0)
        edit_menu.add_command(label="リセット", command=self.reset_graph, accelerator="Ctrl+D")
        edit_menu.add_command(label="Undo", command=self.undo, accelerator="Ctrl+Z")
        edit_menu.add_command(label="Redo", command=self.redo, accelerator="Ctrl+Y")
        menubar.add_cascade(label="編集", menu=edit_menu)

        # メニューバーを表示
        self.root.config(menu=menubar)

        # ショートカットキーの設定
        self.root.bind("<Control-n>", lambda event: self.set_add_node_mode())
        self.root.bind("<Control-b>", lambda event: self.set_insert_node_mode())
        self.root.bind("<Control-d>", lambda event: self.reset_graph())
        self.root.bind("<Control-z>", lambda event: self.undo())
        self.root.bind("<Control-y>", lambda event: self.redo())

    def set_add_node_mode(self):
        """ ノード追加モードに切り替え """
        self.mode = "add_node"
        self.selected_node = None
        self.draw_graph()  # ハイライトが残らないように再描画

    def set_insert_node_mode(self):
        """ ノード間挿入モードに切り替え """
        self.mode = "insert_node_between"
        self.selected_node = None
        self.draw_graph()  # ハイライトが残らないように再描画

    def draw_graph(self):
        """ グラフを描画 """
        self.ax.clear()  # 以前のグラフをクリア
        pos = nx.get_node_attributes(self.G, 'pos')

        # ノードの状態に基づいて色を決定
        colors = []
        for node in self.G.nodes:
            if node == self.hovered_node:
                colors.append('red')  # ホバーされているノードは赤
            elif node == self.selected_node:
                colors.append('blue')  # 選択されたノードは青
            else:
                # ノードの状態（0=白、1=黒）に基づいて色を設定
                state = self.G.nodes[node]['state']
                colors.append('white' if state == 0 else 'black')

        # ノードを描画（白いノードには黒い枠をつける）
        nx.draw(self.G, pos, with_labels=False, node_color=colors, node_size=500, font_size=16, 
                edgecolors='black')  # 黒い枠

        # ノードラベルの描画
        labels = {node: node for node in self.G.nodes}
        label_colors = {node: 'white' if self.G.nodes[node]['state'] == 1 else 'black' for node in self.G.nodes}
        nx.draw_networkx_labels(self.G, pos, labels=labels, font_color=label_colors)

        # 描画の更新
        self.canvas_plot.draw()

    def add_node_with_branch(self, selected_node):
        """ 選択されたノードから新しいノードを追加 """
        pos = nx.get_node_attributes(self.G, 'pos')
        x, y = pos[selected_node]

        # 新しいノードの位置をランダムに計算
        angle = np.random.uniform(0, 2 * np.pi)
        r = 1
        new_x = x + r * np.cos(angle)
        new_y = y + r * np.sin(angle)

        # 新しいノードを追加（状態は白）
        new_node = len(self.G.nodes) + 1
        self.G.add_node(new_node, pos=(new_x, new_y), state=0)  # 新しいノードは状態0（白）
        self.G.add_edge(selected_node, new_node)

        # 選択されたノードの色を反転
        self.flip_state(selected_node)

        # グラフを再描画
        self.draw_graph()

    def insert_node_between(self, node1, node2):
        """ 2つのノードの間に新しいノードを挿入 """
        if self.G.has_edge(node1, node2):
            pos1 = self.G.nodes[node1]['pos']
            pos2 = self.G.nodes[node2]['pos']
            mid_pos = [(p1 + p2) / 2 for p1, p2 in zip(pos1, pos2)]

            # エッジを削除し、新しいノードを追加
            self.G.remove_edge(node1, node2)
            new_node = len(self.G.nodes) + 1
            self.G.add_node(new_node, pos=mid_pos, state=0)  # 新しいノードは状態0（白）
            self.G.add_edge(node1, new_node)
            self.G.add_edge(new_node, node2)

            # 両端のノードの色を反転
            self.flip_state(node1)
            self.flip_state(node2)

            self.draw_graph()

    def flip_state(self, node):
        """ ノードの状態を反転（0→1または1→0） """
        current_state = self.G.nodes[node]['state']
        self.G.nodes[node]['state'] = 1 - current_state  # 状態を反転

    def on_hover(self, event):
        """ ホバーイベント処理（ノードのハイライト表示） """
        if event.xdata is None or event.ydata is None or len(self.G.nodes) == 0:
            return  # 無効なホバーやノードがない場合は無視

        nearest_node = self.find_nearest_node(event.xdata, event.ydata)
        if nearest_node != self.hovered_node:  # 別のノードにホバーしている場合
            self.hovered_node = nearest_node

        # グラフを再描画して変更を反映
        self.draw_graph()

    def on_click(self, event):
        """ クリックイベント処理（ノードの追加・挿入） """
        if event.xdata is None or event.ydata is None:
            return  # 無効なクリックは無視

        if self.mode == "add_node":
            if self.selected_node is None:  # ノードを選択
                self.selected_node = self.find_nearest_node(event.xdata, event.ydata)
            else:  # 選択されたノードから新しいノードを追加
                self.add_node_with_branch(self.selected_node)
                self.selected_node = None

        elif self.mode == "insert_node_between":
            if self.selected_node is None:  # 最初のノードを選択
                self.selected_node = self.find_nearest_node(event.xdata, event.ydata)
            else:  # 2つ目のノードを選択して、その間にノードを挿入
                second_node = self.find_nearest_node(event.xdata, event.ydata)
                if not self.G.has_edge(self.selected_node, second_node):
                    messagebox.showerror("エラー", "選択したノードの間にエッジが存在しません")
                else:
                    self.insert_node_between(self.selected_node, second_node)
                self.selected_node = None

        # 操作履歴を更新し、redoスタックをクリア
        self.history.append(self.G.copy())
        self.redo_stack.clear()

        # グラフを再描画
        self.draw_graph()

    def find_nearest_node(self, x, y, threshold=0.05):
        """ マウス位置に最も近いノードを見つけ、一定の距離以内なら返す """
        pos = nx.get_node_attributes(self.G, 'pos')
    
        # ノードとマウスの距離を計算し、最も近いノードを見つける
        nearest_node = min(self.G.nodes, key=lambda n: np.linalg.norm(np.array(pos[n]) - np.array([x, y])))
    
        # 最近接ノードとの距離を計算
        distance = np.linalg.norm(np.array(pos[nearest_node]) - np.array([x, y]))
    
        # 閾値よりも近い場合のみノードを返す。それ以外は None を返す
        if distance <= threshold:
            return nearest_node
        else:
            return None

    def reset_graph(self):
        """ グラフを初期状態にリセット """
        self.G.clear()  # すべてのノードとエッジを削除
        self.G.add_node(1, pos=(0, 0), state=0)  # 初期ノードを追加（状態0=白）

        # 操作履歴とredoスタックをクリア
        self.history.clear()
        self.redo_stack.clear()

        # ホバーと選択されたノードをリセット
        self.hovered_node = None
        self.selected_node = None

        # グラフを再描画
        self.draw_graph()

    def undo(self):
        """ 最後の操作を元に戻す """
        if self.history:
            self.redo_stack.append(self.G.copy())
            self.G = self.history.pop()
            self.draw_graph()

    def redo(self):
        """ 最後の元に戻した操作をやり直す """
        if self.redo_stack:
            self.history.append(self.G.copy())
            self.G = self.redo_stack.pop()
            self.draw_graph()

# Tkinterアプリケーションの実行
root = tk.Tk()
app = GraphApp(root)
root.mainloop()
```