列挙グラフ

Question

。 NとKむしろN = 8とK = 3の周りに、大規模なセットは、環状および非環状グラフを含むことができません。各グラフは、多数の重み付けされたグラフをサンプリングするためのテンプレートとして機能します。

私の関心は、トポロジモチーフの役割であるので、私はお互いに対称である任意の二つのグラフの重みをサンプリングしたくない、対称は、頂点のない順列はそれを変換1つのグラフ内に存在しないことを意味しますもう一方に直接の後継者または前任者の制限に違反しているため（それらのほとんど）隣接行列とすべてのそれらを排除 -

素朴な解決策は、2 ^（1）N *（N）を考慮するだろう。 n = 8の場合、それはまだ表現するのに十分なビット数であり、uint64_tの中に各マトリックスを快適に列挙します。

行数と列数を追跡することはもう1つ改善されますが、実際のボトルネックは結果セットにグラフを追加することです。この時点で、すでにセット内にあるグラフに対して対称性をテストする必要があります。 n = 8の場合、挿入操作あたりすでに40,000を超える置換があります。

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

Answer 1

グラフの同型性は、私の意見では、あなた自身を実装することについて考えるべきではありません。現在の最先端技術はBrendan McKayのNauty（および関連するプログラム/ライブラリ）であると私は信じています。これはちょっとした苦労ですが、あなた自身の素朴なグラフ同型性を避ける価値があります。また、主に無向グラフに対応していますが、有向グラフも可能です。 geng（無向グラフを生成する）とdirectg（下にあるグラフが与えられた有向グラフを生成する）ユーティリティをチェックアウトすることができます。

Answer 2

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

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

私はあなたの対称性制約についても疑問に思います。このようなグラフをすべて対称にするわけではありませんか？接続行列の行と列を並べ替えることはできますか？

たとえば、グラフで自己接続を許可する場合、次の接続マトリックスが条件を満たすかどうかを確認します。

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 

このマトリックスから出発し、すべての行と列三の和を持っている場合、全てのこのようなグラフを得ることの行と列を入れ替えすることが可能ではないのですか？

このようなマトリックスの一例は、上記のマトリックス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。この場合、私は対角に唯一0個の行列を得るためにコマンドを数回繰り返しました。:)

編集

ああ、私は私が間違っていたことをあなたのコメントから参照してください。もちろん、パーミュテーションインデックスは行と列で同じでなければなりません。私はグラフと自己接続で始まり、順列の後にそれらなしで得たときにそれを気づいたはずです。

ランダム同型順列は、代わりに次のようになります。すべて自己の接続を維持します

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

を。

おそらく、これは行列が生成されるときには何らかの使用になる可能性がありますが、それは私が思ったほど有用ではありません。