Google Appengine DataStore에 지시 된 그래프를 저장합니다

Question

Google 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

정점/링크의 수에 따라 많은 새로운 엔티티를 만드는 대신 목록 만 사용할 수 있습니다. Google IO 2009 에서이 비디오의 후반에 설명 된 친구 그래프 문제를 확인하십시오. http://www.youtube.com/watch?v=agal6ngpkb8

정점의 수가 충분히 높다고 생각되면 연결을 나타내는 목록이있는 정점 모델 만 만들 수 있습니다.

Answer 3

Google App Engine을 사용하는 것을 고려하면 정보를 별도의 테이블에 저장하는 것이 가장 좋습니다.

하나는 정점을위한 것이고, 하나는 정점에서 나온 링크 (이미 말했듯이) 및 경로가 이미 미리 컴퓨팅 된 링크 용.

GAE는 저장 한 정보가 정규화되어 계산을 수행 할 필요가없는 경우 가장 잘 작동합니다.