LangGraph体験 : LLMなし、LangGraphでDFAを作ってみる

まえがき

LangGraph気になっていたのですが、LLMが怖くて手を出せてませんでした。
（API使ったらお金かかりそうなのが怖くて、手がだせなかったです。）

そんな時、末尾に記載の参考にした記事のところに挙げた記事を読んで目からウロコが落ちました。

参考記事をもとに、自分なりに一歩踏み込んで試行錯誤してみました。
せっかくなので記録に残しておきたいと思います。

用語について

LangGraphとは (Geminiに聞いてみた)

LangGraphは、LLM（大規模言語モデル）を活用した複雑な推論や意思決定プロセスをグラフ構造で表現し、実行するためのフレームワークです。Langchainを基盤としており、LLMの持つ能力を最大限に引き出しながら、より構造化された、信頼性の高いアプリケーション開発を可能にします。

通常、LLMアプリケーションは単一のプロンプトとレスポンスの繰り返しになりがちですが、LangGraphを用いることで、複数のステップや条件分岐、並列処理などを組み込んだ、より高度な処理フローを定義できます。各ノードがLLMの呼び出しやデータ処理などの特定の処理を担当し、エッジがそれらの間のデータの流れや制御の流れを定義します。

LLMの創造性や知識を活用しつつ、グラフ構造によって処理の順序や条件を明確にすることで、より予測可能でデバッグしやすいシステムを構築できるのがLangGraphの大きな特徴と言えるでしょう。

DFAとは (Geminiに聞いてみた)

DFA（Deterministic Finite Automaton、決定性有限オートマトン）は、計算理論における最も基本的なモデルの一つです。有限個の状態と、状態間の遷移規則、そして初期状態と受理状態の集合によって定義されます。

DFAは、入力として与えられた記号を一つずつ読み込みながら、現在の状態から遷移規則に従って次の状態へと移動していきます。入力の最後まで読み込んだ時点で、DFAが受理状態にあれば、その入力は「受理された」と判断されます。そうでなければ「拒否された」となります。

「決定性」という言葉が示すように、DFAの重要な特徴は、どの状態においても、入力された記号に対して次に遷移する状態が一意に決まることです。これにより、DFAの動作は完全に予測可能であり、曖昧さがありません。

DFAは、プログラミングにおける字句解析、テキスト検索、状態遷移を伴う制御システムなど、様々な分野で応用されています。非常に単純なモデルでありながら、コンピュータ科学の基礎を理解する上で重要な概念です。

自分が作ったもの

DFAの仕様

入力文字列に含まれる"1"の数が奇数であるかどうかを判定

ソースコード

from typing_extensions import TypedDict
from langgraph.graph import StateGraph

class State(TypedDict):
    input: str
    state: str

def even(state: State):
    print(f"even : {state['input']}")
    return {"input": state["input"], "state": "even" }

def odd(state: State):
    print(f"odd  :  {state['input']}")
    return {"input": state["input"], "state": "even"}

def even_step(state: State):
    print(f"even_step : {state['input'][1:]}")
    return {"input": state["input"][1:], "state": "even_step"}

def odd_step(state: State):
    print(f"odd_step  :  {state['input'][1:]}")
    return {"input": state["input"][1:], "state": "odd_step"}

def accept(state: State):
    print(f"accept  :  {state['input']}")
    return {"input": "", "state": "accept"}

def reject(state: State):
    print(f"reject  :  {state['input']}")
    return {"input": "", "state": "reject"}

def routing_even(state: State):
    print(f"routing_even :  {state['input']}")

    if state["input"] == "":
        return "accept"

    crr_char = state["input"][0]

    if crr_char == "1":
        return "odd_step"
    elif crr_char == "0":
        return "even_step"
    else:
        return "reject"

def routing_odd(state: State):
    print(f"routing_even :  {state['input']}")

    if state["input"] == "":
        return "reject"

    crr_char = state["input"][0]

    if crr_char == "1":
        return "even_step"
    elif crr_char == "0":
        return "odd_step"
    else:
        return "reject"

graph_builder = StateGraph(State)

graph_builder.add_node("odd",       odd)
graph_builder.add_node("even",      even)
graph_builder.add_node("odd_step",  odd_step)
graph_builder.add_node("even_step", even_step)
graph_builder.add_node("accept",    accept)
graph_builder.add_node("reject",    reject)

graph_builder.set_entry_point("odd")
graph_builder.set_finish_point("accept")
graph_builder.set_finish_point("reject")

graph_builder.add_conditional_edges(
    source="even",
    path=routing_even,
    path_map={"accept": "accept", "reject": "reject", "even_step": "even_step", "odd_step": "odd_step"},
)
graph_builder.add_conditional_edges(
    source="odd",
    path=routing_odd,
    path_map={"reject": "reject", "even_step": "even_step", "odd_step": "odd_step"},
)
graph_builder.add_edge("even_step", "even")
graph_builder.add_edge("odd_step", "odd")

graph = graph_builder.compile()

作ったグラフの構造をアスキーアートで表示

graph.get_graph().print_ascii()

作ったグラフの構造をmermaidで出力

print(graph.get_graph().draw_mermaid())

2個の"1" : 拒否

graph.invoke({"input": "11"})

1個の"1" : 受理

graph.invoke({"input": "01"})

4個の"1" : 拒否

graph.invoke({"input": "1010101"})

5個の"1" : 受理

graph.invoke({"input": "11111"})

対応してない文字("a")が含まれる : 拒否

graph.invoke({"input": "1a"})

作成したノートブックへのリンク

コメント

いっぱい無駄な記述ありますが、、、、一旦、狙い通り動くようにできるところまでたどり着いたので、記事に残しておきます。
勉強を続けて、きれいに書き直していきたいと考えています。

追記: 無駄なnodeを減らしてみました

参考にした記事