原因結果グラフ法がテストを減らすときの「考え方」

# 原因結果グラフとは
[原因結果グラフ(Cause-Effect Graph = CEG)](https://www.itmedia.co.jp/im/articles/1111/07/news199.html)とは、複雑なロジックを持つ仕様に対して抜け漏れの無いデシジョンテーブルを作成するために、論理関係をブールグラフで表したものです。

例えば、次の表に示すような遊園地の料金システムをグラフ化することを考えてみましょう。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/246520/c2d3e460-3126-fca0-e3cb-7805d591a3aa.png)

この事例は、「秋山浩一『組合せテストの設計』情報処理 Vol.49 No.2 Feb. 2008」より借用させて頂きました。
ニフティの加瀬さんが作成され、[CEGTestと名付けられたツールが無料で公開されています](https://softest.jp/?page_id=13)ので、そのツールを使用して描いてみたグラフを下図に示します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/246520/cdbe5f4a-e53e-89e4-79f8-d242a8ee0e46.png)

ディジタル論理回路(組合せ論理回路網)のようになりますが、電子工学の知識は必要ないです。ブール論理(論理命令としてのand, or, not)の理解があれば描き始められると思います。
一方、せっかく電子工学の知識がある人は、次の回路と見比べてみると理解が早まると思います。これは[SimcirJS](https://kazuhikoarase.github.io/simcirjs/
)を使用して描いたものです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/246520/b5d302e5-ad4a-858e-8998-a11f82a72af1.png)

# 原因結果グラフ法とは

原因結果グラフを作成した上で、条件の組合せを表現しながらテストケースを系統的に作成する技法です。
また、バグの発見のために、有効性の高いテストケースを選び出すのに有用な技法です。
グラフを描けば、あとは機械的手順でテストケースを選び出すことができるので、これはツールに任せるのが合理的です。実際、先にグラフを描くのに使ったCEGToolは、これをリアクティブに実行し、デシジョンテーブルの形で表示してくれます。

他にも有用な特徴があるのですが、それは別稿で解説することにしまして、ここでは有効性の高いテストケースを選び出す、つまりはテストを減らすときの「考え方」を解説します。

# テストケース数はどれぐらい減るのか？

まず、どれぐらいありがたいことなのかを確認しておくことにしましょう。「テストケース数はどれぐらい減るのか？」を見ておくことにします。

例えば、次の図に示すような4ノードの論理積のケースでは、デシジョンテーブルに#1～#5までの5つのテストケースが生成されていることがわかります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/246520/37fffa89-46a1-0075-75ae-e493d604d769.png)

続いて論理和のケース。同様に5つのテストケースが生成されていることがわかります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/246520/2d261dfb-98eb-a788-b1c5-1c26bc141e6d.png)

4ノードですから、抜け漏れなくデシジョンテーブル、あるいは真偽値表を作成すると、2の4乗、つまり16通りのケースが出てくるはずです。各図の右側に個の抜け漏れのない真偽値表を示しました。グレーに塗りつぶされたケースは選ばれなかったということになります。

このように、テスト数が２のN乗から、どちらの場合もN+1にまで減らすことができ、このようにして組合せの爆発を防ぐことができるのです。

もちろん、実際に必要なロジックは、論理積、論理和、否定などが混合することになるので、N+1にまでは減らないとは思いますが、オーダーが違うわけですから、「爆発を防ぐことができる」という表現は少しも大袈裟ではないと思います。

# 原因結果グラフ法がテストを減らすときの「考え方」

さて、それではやっと本題です。どういう「考え方」で減らしているのか、真偽値表でグレーに塗りつぶしたケースはなぜ選ばなかったのか、その説明に入ります。

## 論理積 (AND) の場合の減らし方

先に示した4ノードでは分かり難くなってしまうので、最も単純化した2ノードのケースで、また少し具体的な事例で説明していくことにします。

ある遊園地のジェットコースターに乗るのには、次のような制限があるものとします。

> 「10歳以上で身長は120cm以上の方のみお乗りいただけます」

フロー図とデシジョンテーブルを以下に示します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/246520/04dc9721-1159-9df2-fde8-cff85ba351e0.png)

以下の命題表現を使うと、P∧Qが真(T)であれば乗ることができるということになります。
<dl>
 <dt>P</dt><dd>年齢は10歳以上である</dd>
 <dt>Q</dt><dd>身長は120cm以上である</dd>
</dl>

プログラムには評価順序が考えられますが、原因結果グラフの論理表現では、特にPとQの評価順序は決まりません。なので、どっちが先でも構わないように二通りのフロー図を示してあります。
フロー図でのパスの矢印に、色が付けてありますが、同じ色で同時に示してあるデシジョンテーブルの対応づく部分を塗りつぶしてあり、対応関係がわかるようにしてあります。

\#4の列(テストパターン)は、グレーに塗りつぶしてありますが、これは選ばないことにします。
その理由こそがここで示したい「考え方」ということになります。
\#4を、他の列と比べてみましょう。#4は他の列が既に通った経路しか通らないことがわかります。
しかも、もしも仮にPあるいはQのどちらかの条件記述に誤り(バグ)があったとしても、複数経路があるのでもう一方が合っていれば正解に辿り着いてしまうことがわかります。
⇒ つまり他のケースに比して#4の有効性が低いことがわかります。

これが#4を選ばない理由であり、テストを減らすときの「考え方」ということになります。

CEGTestツールでグラフを描いて、生成されたデシジョンテーブルを以下に示します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/246520/1229a48f-2923-6c61-3cff-19b201cf29f1.png)

\#4のケースはデシジョンテーブルに出て来ないことが確認できます。

## 論理和 (OR) の場合の減らし方

では今度は論理和 (OR) の場合について、同じように単純化した2ノードのケースで、また少し具体的な事例で説明していくことにします。

ある遊園地のジェットコースターに乗るのに、今度は次のような制限があるものとします。

> 「10歳以下の方と、80歳以上の方はご遠慮ください」

フロー図とデシジョンテーブルを以下に示します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/246520/d6c05bec-bab1-1121-9549-5694217510ff.png)

以下の命題表現を使うと、P∨Qが真(T)であれば、今度は乗ることができない、ということになります。
<dl>
 <dt>P</dt><dd>年齢は10歳以下である</dd>
 <dt>Q</dt><dd>年齢は80歳以上である</dd>
</dl>

これもまた全く同様に、プログラムには評価順序が考えられますが、原因結果グラフの論理表現では、特にPとQの評価順序は決まりません。なので、どっちが先でも構わないように二通りのフロー図を示してあります。
フロー図でのパスの矢印に、色が付けてありますが、同じ色で同時に示してあるデシジョンテーブルの対応づく部分を塗りつぶしてあり、対応関係がわかるようにしてあります。

\#4の列(テストパターン)は、グレーに塗りつぶしてありますが、これは選ばないことにします。
その理由こそがここで示したい「考え方」ということになります。
\#4を、他の列と比べてみましょう。#4は他の列が既に通った経路しか通らないことがわかります。
しかも、もしも仮にPあるいはQのどちらかの条件記述に誤り(バグ)があったとしても、複数経路があるのでもう一方が合っていれば正解に辿り着いてしまうことがわかります。
⇒ つまり他のケースに比して#4の有効性が低いことがわかります。

これが#4を選ばない理由であり、テストを減らすときの「考え方」ということになります。

CEGTestツールでグラフを描いて、生成されたデシジョンテーブルを以下に示します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/246520/32088c72-89df-4a6d-c2ec-24f0836ae95b.png)

\#4のケースはデシジョンテーブルに出て来ないことが確認できます。

# おまけ

[原因結果グラフ法の制約関係の記述](https://qiita.com/sho1884/items/32f8d4d6454e48f1c33c)について知っている方は、テストケースに出てくるものは、次のようにEXCL制約を付けた場合と同じになると覚えておくと良いでしょう。

## 論理積の場合
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/246520/7c8d2e96-50ed-70cf-b731-bcde7fbc4600.png)

## 論理和の場合

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/246520/4ef54096-00b2-28f8-ba9e-6e20e2695916.png)