如何序列化圖結構？

平面文件和關係數據庫爲我們提供了序列化結構化數據的機制。 XML非常適合序列化非結構化樹狀數據。如何序列化圖結構？

但很多問題最好用圖表來表示。例如，熱仿真程序將通過電阻邊緣與溫度節點相互連接。

那麼序列化圖結構的最佳方式是什麼？我知道XML在某種程度上可以做到 - 就像關係數據庫可以序列化一個複雜的對象網絡一樣：它通常可以工作，但很容易變得醜陋。

我知道graphviz程序使用的點語言，但我不確定這是實現它的最佳方式。這個問題可能是學術界可能正在研究的問題，我很樂意參考討論這個問題的任何論文。

來源

2008-09-09 lindelof

如何在內存中表示圖形？
基本上有兩種（好）選項：

其中鄰接列表表示最好用於稀疏圖，併爲稠密的圖的矩陣表示。

如果您使用了這樣的表示，那麼您可以將這些表示序列化。

如果必須是人類可讀的您仍然可以選擇創建自己的序列化算法。例如，你可以寫下矩陣表示喜歡你將任何「正常」的矩陣做的事：剛打印出的列和行，所有的數據在它像這樣：

1 2 3 
1 #t #f #f 
2 #f #f #t 
3 #f #t #f

（這是一個非優化的非加權表示，但可用於有向圖）

來源

2008-09-09 13:04:14 sven

XML非常冗長。每當我這樣做時，我都會自己推出。這是一個3節點有向無環圖的例子。這是相當緊湊，做一切我需要做的：

0: foo 
1: bar 
2: bat 
---- 
0 1 
0 2 
1 2

來源

2008-09-09 12:58:56 jodonnell

在一個較小的學術，更實際的音符，在CubicTest我們使用Xstream（Java）來測試序列化和XML。 Xstream處理圖形結構化的對象關係，因此您可以通過查看源代碼和生成的xml來學習一兩件事。你說得對醜陋部分雖然，生成的XML文件看起來不漂亮。

來源

2008-09-09 13:01:23

您可能會熟悉的一個示例是Java序列化。這有效地按圖進行序列化，每個對象實例都是一個節點，每個引用都是一個邊。使用的算法是遞歸的，但跳過重複。這樣的僞代碼將是：

serialize(x): 
    done - a set of serialized objects 
    if(serialized(x, done)) then return 
    otherwise: 
     record properties of x 
     record x as serialized in done 
     for each neighbour/child of x: serialize(child)

當然另一種方式是作爲節點和邊的列表，其可以做爲XML，或以任何其它優選的序列化格式，或作爲鄰接矩陣。

來源

2008-09-09 13:03:53

我試過使用Java序列化來連載圖形。但是我得到堆棧溢出異常。顯然這是一個常見的抱怨，推薦的解決方案是編寫低級代碼來覆蓋「readObject（）/ writeObject（）」。有沒有更好的辦法？ – 2010-04-07 06:35:25

通常，XML中的關係由父/子關係顯示。 XML可以處理圖形數據，但不能以這種方式處理。要處理XML圖形，您應該使用xs:ID和xs:IDREF模式類型。

在一個示例中，假設node/@ id是xs：ID類型，並且該鏈接/ @ ref是xs：IDREF類型。以下XML顯示了三個節點1→2→3→1的循環。

<data> 
    <node id="1"> 
    <link ref="2"/> 
    </node> 
    <node id="2"> 
    <link ref="3"/> 
    </node> 
    <node id="3"> 
    <link ref="1"/> 
    </node> 
</data>

許多開發工具也支持ID和IDREF。我用Java的JAXB（Java的XML綁定，它通過@XmlID和@XmlIDREF註解支持這些，你可以使用普通的Java對象建立你的圖，然後使用JAXB處理實際序列化XML。

來源

2008-09-09 13:12:52

鄰接表和鄰接矩陣是內存中表示圖形的兩種常用方式，在決定這兩者時需要做出的第一個決定是你想要優化的內容，如果需要，鄰接列表非常快，例如，獲取另一方面，如果您正在做邊緣存在的大量測試或者有一個馬爾可夫鏈的圖形表示，那麼您可能會偏好一個鄰接矩陣。

下一個問題你需要d要考慮的是你需要融入記憶的程度。在大多數情況下，如果圖中的邊數遠小於可能邊的總數，則鄰接列表將更加高效，因爲您只需存儲實際存在的邊。一個令人滿意的媒介是用壓縮的稀疏行格式表示鄰接矩陣，其中您保持從左上角到右下角的非零條目的向量，指示哪些列可以找到非零條目的對應向量，以及第三個向量表示列條目向量中每一行的開始。

[[0.0, 0.0, 0.3, 0.1] 
[0.1, 0.0, 0.0, 0.0] 
[0.0, 0.0, 0.0, 0.0] 
[0.5, 0.2, 0.0, 0.3]]

可以被表示爲：

vals: [0.3, 0.1, 0.1, 0.5, 0.2, 0.3] 
cols: [2, 3, 0, 0, 1, 4] 
rows: [0,  2, null, 4]

壓縮稀疏行是一個有效的鄰接表（列索引功能相同的方式），但格式使其本身更多的乾淨到矩陣運算。

來源

2008-09-28 03:07:21 jbl

如何序列化圖結構？

回答

相關問題