6

n個の頂点を持つすべての有向グラフのセットを作成したいと思います。各頂点にはk個の直接の後継者とk個の直接の先行者があります。nとkはそれほど大きくなく、n = 8 とk = 3 程度です。セットには循環グラフと非循環グラフが含まれます。各グラフは、多数の加重グラフをサンプリングするためのテンプレートとして機能します。

私の関心はトポロジー モチーフの役割にあるため、互いに対称な 2 つのグラフの重みをサンプリングしたくありません。対称性とは、一方のグラフを他方のグラフに変換する頂点の順列が存在しないことを意味します。

単純な解決策は、2 ^ ( n * ( n - 1)) 隣接行列を考慮し、直接の後継者または先行者の制約に違反しているすべての (それらのほとんど) を排除することです。n = 8 の場合でも、 a 内で各行列を快適に表現して単純に列挙するのに十分な数のビットuint64_tです。

行数と列数を追跡することは別の改善ですが、実際のボトルネックはグラフを結果セットに追加することです。その時点で、既にセットにある他のグラフに対して対称性をテストする必要があります。n = 8 の場合、挿入操作ごとに既に 40,000 を超える順列になります。

このすべてをよりスマートな方法で行うことができる、私が読むことができるアルゴリズムを誰かに紹介してもらえますか? このような包括的なグラフ ジェネレーターを既に実装している C、C++、Java、または Python 用のグラフ ライブラリはありますか? 合理的なnとkのすべてのグラフを誰かが既に「集計」しているリポジトリはありますか?

4

2 に答える 2

1

私はあなたの質問で何かを逃したように思われるので、これは答えというよりもコメントです。

まず第一に、そのようなグラフが非周期的である可能性はありますか？

私はあなたの対称性の制約についても疑問に思っています。これは、そのようなすべてのグラフを互いに対称にしませんか？接続マトリックスの行と列を並べ替えることはできますか？

たとえば、グラフで自己接続を許可する場合、次の接続行列は条件を満たしていますか？

 1     1     0     0     0     0     0     1
 1     1     1     0     0     0     0     0
 0     1     1     1     0     0     0     0
 0     0     1     1     1     0     0     0
 0     0     0     1     1     1     0     0
 0     0     0     0     1     1     1     0
 0     0     0     0     0     1     1     1
 1     0     0     0     0     0     1     1

この行列から始めて、その行と列を並べ替えて、すべての行と列の合計が3であるようなすべてのグラフを取得することはできませんか？

このような行列の一例は、上記の行列から次の方法で取得できますA（MATLABを使用）。

>> A(randperm(8),randperm(8))

ans =

     0     1     0     0     0     1     1     0
     0     0     1     0     1     0     1     0
     1     1     0     1     0     0     0     0
     1     1     0     0     0     1     0     0
     1     0     0     1     0     0     0     1
     0     0     1     1     0     0     0     1
     0     0     1     0     1     0     0     1
     0     0     0     0     1     1     1     0

PS。この場合、対角線にゼロのみを持つ行列を取得するために、コマンドを数回繰り返しました。:)

編集

ああ、あなたのコメントから、私は正しくなかったことがわかります。もちろん、順列インデックスは行と列で同じである必要があります。少なくとも、自己接続のあるグラフから始めて、順列の後にそれらのないグラフを取得したときに、それに気付くはずでした。

ランダムな同型順列は、代わりに次のようになります。

idx = randperm(8);
A(idx,idx);

これはすべての自己接続を維持します。

おそらく、これは行列が生成されるときに役立つ可能性がありますが、私が思っていたほど有用ではありません。

于 2013-01-18T16:13:30.833 に答える
1

私の意見では、グラフ同型は、自分で実装しようと考えるべきものではありません。現在の最先端は、Brendan McKay のNauty (および関連するプログラム/ライブラリ) だと思います。これを扱うのは少し面倒ですが、独自の素朴なグラフ同形を避けることには価値があるかもしれません。また、主に無向グラフを対象としていますが、有向グラフも同様に実行できます。Nauty に付属のgeng (無向グラフを生成する) およびdirectg (基になるグラフを指定して有向グラフを生成する) ユーティリティを確認することをお勧めします。

于 2013-01-18T17:20:26.297 に答える