枚舉圖

Question

我想與Ñ頂點，其中每個頂點有ķ直接後繼者和ķ直接前任創建該組的所有有向圖的。 Ñ和ķ不會那麼大，而圍繞Ñ = 8和ķ = 3該集包括環狀和無環圖。每個圖形將作爲抽樣大量加權圖形的模板。

我的興趣是在拓撲圖案的作用，所以我不想品嚐任何兩個圖是相互對稱，重量在那裏對稱意味着沒有頂點的排列在它變換一個圖形存在進入另一個。

甲幼稚的解決方案是考慮2 ^（Ñ *（Ñ - 1））鄰接矩陣和消除所有那些（大部分），用於其中直接後繼者或前導者限制被違反。對於ñ = 8，這仍然有足夠的位來表示，並簡單地枚舉每個矩陣在uint64_t內舒適。

跟蹤行數和列數將是另一個改進，但真正的瓶頸是將圖添加到結果集中，此時我們需要測試集合中已存在的每個其他圖的對稱性。對於n = 8每個插入操作已經超過40,000個排列。

任何人都可以引用我的算法，我可以閱讀，可以以更聰明的方式做到這一切？是否有C，C++，Java或Python的圖庫，已經實現了這樣一個全面的圖形生成器？是否有一個存儲庫，其中某人已經「合理」列出所有圖表n和k？

Answer 1

在我看來，圖同構不是你應該考慮實現自己的東西。我相信目前最先進的技術是Brendan McKay的Nauty（及相關程序/庫）。這與工作有點相似，但避免做自己的天真圖同構可能是值得的。此外，它主要面向無向圖，但它也可以做有向圖。您可能想查看與Nauty一起提供的geng（其生成無向圖）和（它生成有底圖的有向圖）實用程序。

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 

從這個矩陣開始，是那麼不可能置換它的行和列，以獲得所有這樣的圖，所有的行和列有三個的總和？

這樣的矩陣的一個例子可以通過以下方式（使用MATLAB）從上述矩陣A獲得。

>> 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); 

這將讓所有的自我連接。

也許這可能在矩陣生成時有些用處，但它並不像我想象的那樣有用。