0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ynakayama(Yasuhiro Nakayama)

有向グラフの構造変更を追加・削除・変更量に分けて Python で検証する

0
Posted at

ソフトウェアの呼び出し関係を変更したとき、変更された関係の本数だけを記録すると、関係を増やしたのか減らしたのかが分かりません。例えば、入力検証から記録処理への経路を一本追加する操作と、同じ経路を一本削除する操作は、どちらも「一本の変更」です。しかし、一方では呼び出し関係が増え、もう一方では減っています。

この違いを測るため、 構造振幅（更新前後の構造間距離） と 更新方向（エッジ数の符号付き差分） を別々に計算します。両方の値を記録すれば、更新規模が同じでも構造の増減方向が逆になることを判定できます。構造振動モデルでは、構造を関係グラフとして表し、構造差分と更新方向を区別します[1]。

測定条件と実行環境

四つの部品を持つ仮想的なソフトウェアを対象とします。A は受付、B は入力検証、C は処理、D は記録を担当します。部品をノード、部品間の呼び出しを向き付きのエッジとします。A から B への呼び出しと、B から A への呼び出しは別のエッジです。

候補エッジは以下の六本に固定します。候補の並び順も、すべての時点で維持します。

識別子 始点 終点 想定する関係
e1 A B 受付から入力検証
e2 B C 入力検証から処理
e3 C D 処理から記録
e4 A D 受付から記録
e5 B D 入力検証から記録
e6 A C 受付から処理

各時点では、エッジがあれば 1、なければ 0 として、e1 から e6 の順に六つの数値を並べます。これを 二値ベクトル と呼びます。初期状態では e1、e2、e3 のみが存在するため、ベクトルは (1, 1, 1, 0, 0, 0) です。

実行には Python 3.8 以降を使用します。距離の計算には標準ライブラリの math.dist を用いるため、外部パッケージは必要ありません。掲載した実行結果は Python 3.13.5 で確認しました。

python3 --version

構造振幅と更新方向を定義する

時刻 t の構造を S_t、その二値ベクトルを x_t とします。隣接時点の二値ベクトルの ユークリッド距離 を構造振幅 A_t とします。ユークリッド距離は、各成分の差を二乗して合計し、平方根を取った値です。

A_t=\sqrt{\sum_{i=1}^{6}(x_{i,t}-x_{i,t-1})^2}

一つのエッジだけを追加または削除すると、一つの成分が 0 と 1 の間で切り替わるため、構造振幅は 1 になります。二本を同時に変更すると √2 です。構造振幅は差の大きさを測るため、追加と削除の符号は保持しません。

そこで、存在するエッジの総数を K(S_t) とし、更新方向 ΔK_t を次の差分で測ります。

\Delta K_t=K(S_t)-K(S_{t-1})

ΔK_t が正ならエッジが純増、負なら純減、ゼロなら総数は変わっていません。ただし、追加と削除が同数なら、内部の接続が入れ替わっていても ΔK_t はゼロになります。

更新の内訳を確認するため、追加された本数を a_t、削除された本数を r_t とします。固定した候補エッジの二値表現では、次の二式が成立します。

A_t^2=a_t+r_t,\qquad \Delta K_t=a_t-r_t

構造振幅の二乗は変更されたエッジの総本数、エッジ数の差分は 純増減 を表します。したがって、一本の追加と一本の削除はどちらも A_t=1 ですが、ΔK_t はそれぞれ +1 と -1 になります。

Python で構造更新を測定する

EDGE_ORDER に候補を固定し、各時点に存在するエッジを frozenset で保持します。encode() はエッジ集合を二値ベクトルへ変換し、候補外のエッジがあれば ValueError を送出します。measure() は構造振幅、符号付き差分、追加・削除されたエッジを返します。

math.dist() は座標列で与えた二点のユークリッド距離を計算する関数です[2]。

structure.py
"""Measure changes in a fixed directed binary graph."""

from math import dist

EDGE_ORDER = (
    ("A", "B"),
    ("B", "C"),
    ("C", "D"),
    ("A", "D"),
    ("B", "D"),
    ("A", "C"),
)

STATES = (
    frozenset(EDGE_ORDER[:3]),
    frozenset(EDGE_ORDER[:5]),
    frozenset(EDGE_ORDER[:4]),
    frozenset(EDGE_ORDER[:3]),
    frozenset((*EDGE_ORDER[:3], EDGE_ORDER[5])),
)


def encode(edges):
    """Return the binary vector in the fixed EDGE_ORDER."""
    edges = frozenset(edges)
    unknown = edges - frozenset(EDGE_ORDER)
    if unknown:
        raise ValueError(f"unknown edges: {sorted(unknown)}")
    return tuple(int(edge in edges) for edge in EDGE_ORDER)


def measure(before, after):
    """Return structural amplitude, signed edge count and exact changes."""
    before = frozenset(before)
    after = frozenset(after)
    x_before = encode(before)
    x_after = encode(after)
    added = after - before
    removed = before - after
    return {
        "vector": x_after,
        "amplitude": dist(x_before, x_after),
        "delta_edges": len(after) - len(before),
        "edge_count": len(after),
        "added": added,
        "removed": removed,
    }


def main():
    print("t  vector               edges  amplitude  delta")
    print(f"0  {str(encode(STATES[0])):<20} {len(STATES[0]):>5}  {'-':>9}  {'-':>5}")
    for t in range(1, len(STATES)):
        item = measure(STATES[t - 1], STATES[t])
        print(
            f"{t}  {str(item['vector']):<20} {item['edge_count']:>5}  "
            f"{item['amplitude']:>9.3f}  {item['delta_edges']:>+5}"
        )


if __name__ == "__main__":
    main()

STATES は原典の数値例と同じ更新履歴です。t=1 で e4 と e5 を追加し、t=2 で e5、t=3 で e4 を削除します。t=4 では e6 を追加します。e6 は入力検証 B を経由しないため、実際の設計では入力の妥当性を別の経路で確保することが前提です。ここでの測定結果は、経路を安全に利用できることの証明ではありません。

同じディレクトリで実行します。

python3 structure.py

実行結果は次のとおりです。

t  vector               edges  amplitude  delta
0  (1, 1, 1, 0, 0, 0)       3          -      -
1  (1, 1, 1, 1, 1, 0)       5      1.414     +2
2  (1, 1, 1, 1, 0, 0)       4      1.000     -1
3  (1, 1, 1, 0, 0, 0)       3      1.000     -1
4  (1, 1, 1, 0, 0, 1)       4      1.000     +1

t=1 の構造振幅は約 1.414、その後の三回はすべて 1.000 です。一方、更新方向は +2, -1, -1, +1 となります。t=2、t=3、t=4 の振幅が同じでも、前二者は削除、最後は追加です。

unittest で期待値と照合する

測定処理が期待値を返すことに加え、同じ振幅から異なる更新方向が得られること、候補外のエッジを拒否することをテストします。Python 標準の unittest では TestCase のアサーションを用いて期待値を検査できます[3]。

test_structure.py
import math
import unittest

from structure import EDGE_ORDER, STATES, encode, measure


class TestStructure(unittest.TestCase):
    def test_initial_vector(self):
        self.assertEqual(encode(STATES[0]), (1, 1, 1, 0, 0, 0))

    def test_order_is_fixed(self):
        self.assertEqual(
            encode(reversed(tuple(STATES[1]))),
            (1, 1, 1, 1, 1, 0),
        )

    def test_unknown_edge_is_rejected(self):
        with self.assertRaises(ValueError):
            encode({("D", "A")})

    def test_directed_edge_is_distinct(self):
        with self.assertRaises(ValueError):
            encode({("B", "A")})  # A -> B is a different edge.

    def test_unchanged_structure(self):
        item = measure(STATES[0], STATES[0])
        self.assertEqual(item["amplitude"], 0)
        self.assertEqual(item["delta_edges"], 0)
        self.assertFalse(item["added"] | item["removed"])

    def test_four_updates(self):
        expected = (
            ((1, 1, 1, 1, 1, 0), math.sqrt(2), +2, 5),
            ((1, 1, 1, 1, 0, 0), 1, -1, 4),
            ((1, 1, 1, 0, 0, 0), 1, -1, 3),
            ((1, 1, 1, 0, 0, 1), 1, +1, 4),
        )
        for t, (vector, amplitude, delta, count) in enumerate(expected, 1):
            with self.subTest(t=t):
                item = measure(STATES[t - 1], STATES[t])
                self.assertEqual(item["vector"], vector)
                self.assertAlmostEqual(item["amplitude"], amplitude)
                self.assertEqual(item["delta_edges"], delta)
                self.assertEqual(item["edge_count"], count)

    def test_same_amplitude_opposite_direction(self):
        deletion = measure(STATES[1], STATES[2])
        addition = measure(STATES[3], STATES[4])
        self.assertEqual(deletion["amplitude"], addition["amplitude"])
        self.assertEqual((deletion["delta_edges"], addition["delta_edges"]), (-1, 1))

    def test_same_metrics_different_removed_edges(self):
        first = measure(STATES[1], STATES[2])
        second = measure(STATES[2], STATES[3])
        self.assertEqual((first["amplitude"], first["delta_edges"]),
                         (second["amplitude"], second["delta_edges"]))
        self.assertEqual(first["removed"], {EDGE_ORDER[4]})
        self.assertEqual(second["removed"], {EDGE_ORDER[3]})

    def test_count_identity(self):
        for before, after in zip(STATES, STATES[1:]):
            with self.subTest(before=encode(before), after=encode(after)):
                item = measure(before, after)
                added = len(item["added"])
                removed = len(item["removed"])
                self.assertAlmostEqual(item["amplitude"] ** 2, added + removed)
                self.assertEqual(item["delta_edges"], added - removed)

    def test_return_to_initial_structure(self):
        self.assertEqual(STATES[0], STATES[3])
        self.assertEqual(measure(STATES[0], STATES[3])["amplitude"], 0)
        self.assertGreater(
            sum(measure(STATES[t - 1], STATES[t])["amplitude"] for t in range(1, 4)),
            0,
        )


if __name__ == "__main__":
    unittest.main()

同じディレクトリで次のコマンドを実行します。

python3 -m unittest -v

Python 3.13.5 での実行結果は、10 件すべて成功、終了コード 0 でした。

test_count_identity (test_structure.TestStructure.test_count_identity) ... ok
test_directed_edge_is_distinct (test_structure.TestStructure.test_directed_edge_is_distinct) ... ok
test_four_updates (test_structure.TestStructure.test_four_updates) ... ok
test_initial_vector (test_structure.TestStructure.test_initial_vector) ... ok
test_order_is_fixed (test_structure.TestStructure.test_order_is_fixed) ... ok
test_return_to_initial_structure (test_structure.TestStructure.test_return_to_initial_structure) ... ok
test_same_amplitude_opposite_direction (test_structure.TestStructure.test_same_amplitude_opposite_direction) ... ok
test_same_metrics_different_removed_edges (test_structure.TestStructure.test_same_metrics_different_removed_edges) ... ok
test_unchanged_structure (test_structure.TestStructure.test_unchanged_structure) ... ok
test_unknown_edge_is_rejected (test_structure.TestStructure.test_unknown_edge_is_rejected) ... ok

----------------------------------------------------------------------
Ran 10 tests in 0.001s

OK

test_four_updates は四回の更新それぞれについて、ベクトル、振幅、純増減、エッジ総数を固定値と比較します。test_same_amplitude_opposite_direction は、一本削除した場合と一本追加した場合の振幅がどちらも 1 であることを検証します。

さらに、test_count_identity では距離から求めた値 A_t² が集合差分から数えた変更本数に一致することを、各更新で確認します。これにより、距離計算と追加・削除の集合演算を別の経路で検証できます。

測定結果を解釈するときの境界

振幅と純増減が一致しても、変更対象までは特定できません。 t=2 と t=3 はともに振幅 1、純増減 -1 ですが、前者では e5、後者では e4 が削除されています。変更された関係を追跡するには、added と removed、または各時点のエッジ集合を記録する必要があります。

開始時点と終了時点の距離だけでは、途中の更新履歴を表せません。 t=0 と t=3 のベクトルは一致するため、両時点の直接距離は 0 です。しかし、その間には二本の追加と二本の削除が実施されています。各更新の構造振幅の合計は √2 + 2 ≈ 3.414、追加・削除の総本数は 4 です。直接距離、振幅の合計、変更本数の合計は、測定する対象が異なります。

エッジ数は保守費用や安全性の尺度ではありません。 この例の K(S_t) はエッジの本数だけを表します。実際のソフトウェアでは、一本の重要な呼び出し関係を削除するだけでも障害が生じ得ます。また、t=2 の削除が競合による障害を改善したかどうかは、変更前後の入力条件と障害記録を比較して確かめる必要があります。

今回のベクトルは六つの固定候補エッジだけを表すため、候補に含めていない依存関係、ノード内部の処理変更、呼び出し頻度や通信時間の変化は測定対象外です。これらを測る場合には、構造表現と距離の定義を追加する必要があります。

結論

固定した六つの候補エッジを二値ベクトルで表すと、構造振幅は math.dist() で、更新方向はエッジ数の符号付き差分で再現可能に計算できます。四回の更新履歴では、振幅 1 の三回の操作に削除と追加の両方が含まれることを確認しました。

変更の規模を判断するときは構造振幅、関係の純増減を判断するときは ΔK_t、変更対象を特定するときは集合差分を参照します。この三つを分けて記録すれば、更新前後の構造が同じ場合も、途中の追加・削除を含めて追跡できます。

参考文献

  1. id774, 構造振動モデルの定義を測定と検証まで含めて整理する（2026-11-11）. https://blog.id774.net/entry/2026/11/11/5869/
  2. Python Software Foundation, math — Mathematical functions. https://docs.python.org/3/library/math.html
  3. Python Software Foundation, unittest — Unit testing framework. https://docs.python.org/3/library/unittest.html
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?