ある記号列の列挙 #8

#2のen2.cや#3のen3.cでは多重エッジを含むグラフを生成しており、
#2ではこれを除去するためにtredを使ってフィルタリングした。
いちいちフィルタするのも面倒な場合、
DOTの方でこれに対処する方法がある。
たとえば、en3.cの場合なら、

en3strict.c

#include <stdio.h>

static void enumerate(unsigned int a, unsigned int b)
{
    if (a > 0) {
        printf("\"%d %d\" -> \"%d %d\" [label=\"a\"];\n", a, b, a - 1, b);
        enumerate(a - 1, b);
    }
    if (b > 0) {
        printf("\"%d %d\" -> \"%d %d\" [label=\"b\"];\n", a, b, a, b - 1);
        enumerate(a, b - 1);
    }
}

int main(void)
{
    puts("strict digraph {");
    enumerate(2, 1);
    puts("}");
    return 0;
}

念のために全コードを示したが、en3.cとの違いは、

    puts("strict digraph {");

のdigraphをstrictで修飾しただけである。
これを実行すると、

$ ./en3strict | dot -Tpng -o en3strict.png

tredを通さなくても多重エッジが無くなっている。
dot User's Manual (dotguide)の記述では、

In the top-level graph heading, a graph may be declared a strict digraph.
This forbids the creation of self-arcs and multi-edges; they are ignored in the input file.

であり、strict修飾によって自己帰還エッジや多重エッジは無視されるようになる。
DOTの仕様であるので、

$ ./en3 | gc
       6       8 %1 (<stdin>)
$ ./en3strict | gc
       6       7 %1 (<stdin>)

dotコマンドだけでなくgcコマンドでもきちんとstrictが効いているのが分かる。

気をつけないといけないことがあり、strictなグラフでは、
開始ノードと終了ノードのそれぞれが一致していれば、それらのエッジは多重エッジと判断されるため、
例えエッジのラベルやIDが異なっていても、そのうちの一つ以外は無視されてしまうことになる。

$ gc << FOO
> digraph {
> a -> b [label=first,id=first_id];
> a -> b [label=second,id=second_id];
> }
> FOO
       2       2 %1 (<stdin>)
$ gc << FOO
> strict digraph {
> a -> b [label=first,id=first_id];
> a -> b [label=second,id=second_id];
> }
> FOO
       2       1 %1 (<stdin>)

とはいえ、en2.cやen3.cの生成するグラフでは、
始まりと終わりのノードがそれぞれ一致するエッジは全て、
「同じラベル」＝「同じ記号による遷移」であるので、これによる問題はないだろう。
ちなみに、

$ gvpr 'E{print($.label, " ", $.id)}' << FOO
> strict digraph {
> a -> b [label=first,id=first_id];
> a -> b [label=second,id=second_id];
> }
> FOO
second second_id

となり、この場合に残ったのは二つ目に記述している方のエッジであった。