如何將定向非循環圖（DAG）存儲爲JSON？

我想將DAG表示爲JSON文本，並且想知道是否有人嘗試了這個以及他們處理的有關驗證JSON實際上是否爲DAG的任何問題。如何將定向非循環圖（DAG）存儲爲JSON？

2012-03-27 828

如果我獲得DAG，DAG可能沒有單根。所以如果你不確定你是否看到它，你如何幹掉這個模型。 – 2012-03-27 21:31:10

任何JSON對象肯定都是DAG。 – Pointy 2012-03-27 22:00:01

標記每個節點並創建一個邊界列表。也就是說，對於每個節點商店，它有邊緣節點，例如：

{ 
    "a": [ "b", "c", "d" ], 
    "b": [ "d" ], 
    "c": [ "d" ], 
    "d": [ ] 
}

您可以存儲多種圖形的這種方式，不僅僅是DAG的，所以你需要進行後期處理它做確定它沒有循環。只要選擇一個節點即DFS，如果您看到任何節點不止一次，它就不是DAG。然後刪除剛纔看到的所有節點，然後重複其餘節點。做到這一點，直到找到一個循環或者你已經刪除了所有的節點，在後一種情況下，圖形是一個DAG。

請注意，這不會存儲父節點，因爲這是冗餘信息。如果您需要這些數據，您可以在加載圖表後生成這些數據。

來源

2012-03-27 23:15:47

反向存儲有什麼缺點（數組值是「from」節點而不是「to」）？如果你想做一個拓撲排序，我會認爲這會更好。 – 2016-04-04 09:47:13

嚴格地說，你不能直接用JSON來做。您必須想出自己的方式來表示可以通過數據結構中其他位置引用標識的對象，然後您必須後處理反序列化JSON字符串的結果。

你不能用JSON來實現它，原因很簡單，JSON表達式是對象圖，而且根本沒有關於表達屬性值應該是另一個屬性值的規定在數據結構中。換句話說，圖中沒有任何對象可以有多個父對象，這意味着每個對象都是一個對象的一個屬性的值。

來源

2012-03-27 21:29:26 Pointy

在DAG中，一個節點可以有兩個父母。考慮用一種編程語言表示一個表達式（比如，JavaScript :-)，其中包含兩個對單個變量的引用。傳統上，表達式中的那兩點將指向同一個節點。 DAG中沒有周期（根據定義），因爲（通常;不一定我猜）所有鏈接「點下」圖表，所以你永遠不會「返回」。它就像一棵樹，除了類似的節點被合併。 – Pointy 2012-03-27 21:40:19

哈哈，這個評論是回答關於這個與週期有關的問題，所以我會把它留在那裏。 – Pointy 2012-03-27 21:40:54

是的，我的基本CS理解失敗;-)感謝您的解釋。 – 2012-03-27 21:41:10

除非您自行約定表示鏈接的數據，否則JSON無法代表DAG。 JSON-LD（一個W3C提案）是一個JSON擴展，正試圖完成這一任務。建議可以在這裏找到：http://json-ld.org/spec/latest/json-ld/。

來源

2013-07-25 19:01:56 dave

如何將定向非循環圖（DAG）存儲爲JSON？

回答

相關問題