在谷歌appengine數據存儲中存儲有向圖

Question

我需要在谷歌appengine中存儲一個大而動態的無向圖，什麼是最好的方式來做到這一點？ 圖形表示必須能夠支持快速提取一組頂點（用於在頁面上呈現）以及來自特定頂點的所有鏈接，以及跨圖形的路徑查找（儘管最佳路徑並非真正需要，只是一個相當好的一個）

我對這個問題的看法： 最明顯的方法是有一個頂點模型和引用兩個頂點的邊緣模型，但是這聽起來像最終會使用很多查詢每一個操作，我想知道是否有更好的方法（可能建立的鏈接信息到每個頂點不知）

Answer 1

這裏是最簡單的方法：

class Vertex(db.Model): 
    outedges = db.ListProperty(db.Key) 
    # Other information about the vertex here 

現在，你可以在所有的探索沒有任何疑問圖 - 只需調用db.get方法上的1個或多個鍵檢索相關頂點：

# Get the first referenced vertex 
vertex2 = db.get(vertex1.outedges[0]) 

# Get all referenced vertices 
vertices = db.get(vertex1.outedges) 

Answer 2

考慮您正在使用的谷歌應用程序引擎這將是最好的，如果你存儲在單獨的表中的信息：

一個用於頂點，一個從頂點的鏈接（因爲你已經說的）和一個額外的一個地方的路徑已經預先計算。

GAE效果最好，如果您存儲信息被規格化，所以你不必做任何計算。

Answer 3

根據頂點/鏈接的數量，您可能只想使用列表而不是創建一堆新實體。檢查Google IO 2009中此視頻後半部分描述的朋友圖問題：http://www.youtube.com/watch?v=AgaL6NGpkB8

如果您認爲頂點數足夠高，您可以使用表示連接的列表創建頂點模型。