graph6格式如何工作？

我一直在尋找如何.g6或graph6格式工作，我不知道它如何工作，我發誓它就像魔術。graph6格式如何工作？

F?B~w

這是以ASCII形式表示的圖形。它可以被Wolfram Mathematica，Sage和Maple解釋，僅舉幾例，給我們一個視覺。然而，在深入Sage的開源代碼幾小時之後，我終於無法理解他們如何以圖表形式閱讀它。

我想知道是否有可能在上述圖中搜索哈密爾頓週期而不必將它們轉換爲鄰接矩陣？或者如果這是不可能的，我們甚至可以將它轉換成鄰接矩陣？

任何幫助，將不勝感激。

來源

2017-06-13 Sailanarmo

http://users.cecs.anu.edu.au/~bdm/data/formats.txt –

您拼寫錯誤的ASCII碼... –

@OliverCharlesworth我確實看到了這一點，但這是我有一個艱難的實時理解。它是否被轉換爲二進制，然後作爲一個鄰接矩陣存儲？它是否轉換爲Decimal，然後從中讀取並轉換爲可搜索的內容？它說，圖形表示爲N（n）R（x），但看起來不像上面的格式，我也不確定如何在程序中使用它來查找所有哈密爾頓路徑。 – Sailanarmo

Oliver Charlesworth已經提供了reference to the format description，但總之基本思想是用ASCII可打印的字符對圖的大小和鄰接矩陣的上三角形進行編碼。

從您的原始無向圖計算鄰接矩陣。這保證是對稱的，所以我們關心的是這個矩陣的上三角形，排除對角線，其將是相同的零。
接下來，通過逐行遍歷矩陣的上部三角形建立大小爲n*(n-1)/2的位向量。例如，對於4x4矩陣，遍歷將是（1,2），（1,3），（1,4），（2,3），（2,4），（3,4）。
將圖形大小爲n的前綴（作爲二進制字），並將得到的位向量分解爲6位的塊。
將每個6位塊轉換爲63到126範圍內的整數，然後將它們轉換爲相應的ASCII字符並連接它們。

注意graph6格式不支持定向或加權圖。我相信它是由Brendan McKay創建的（在nauty source中有一個實現），並且有兩種相關格式：sparse6（用於稀疏圖）和digraph6（用於有向圖）。

digraph6格式似乎是相當新的（添加到nauty 2.6中），除了爲了處理有向圖，格式編碼整個鄰接矩陣減去對角線而不是上面的三角形。

來源

2017-06-15 12:30:34 saforrest

graph6格式如何工作？

回答

相關問題