Сохранение ориентированного, взвешенного, полного графа в хранилище данных GAE - PullRequest
Новая
       10

Сохранение ориентированного, взвешенного, полного графа в хранилище данных GAE

1 голос
/ 23 июля 2011

У меня есть ориентированный, взвешенный, полный граф с 100 вершинами. Вершины представляют фильмы, а края представляют предпочтения между двумя фильмами. Каждый раз, когда пользователь посещает мой сайт, я запрашиваю набор из 5 вершин, чтобы показать его пользователю (набор часто меняется). Давайте назовем эти вершины A, B, C, D, E. Пользователь упорядочивает их (то есть ранжирует эти фильмы от большинства к наименее любимым). Например, он может заказать их D, B, A, C, E. Затем мне нужно обновить график следующим образом: 

Graph[D][B] +=1
Graph[B][A] +=1
Graph[A][C] +=1
Graph[C][E] +=1

Таким образом, график подсчета [V1] [V2] в конечном итоге отражает количество пользователей (фильм) V1 непосредственно над (фильм) V2. Когда данные собраны, я могу выполнять все виды анализа графиков в автономном режиме, например, найдите приемники и источники графика, чтобы определить наиболее и наименее любимые фильмы.

Проблема в следующем: как сохранить ориентированный, взвешенный, полный график в хранилище данных? Очевидный ответ таков: 

class Vertex(db.Model):
    name = db.StringProperty()

class Edge(db.Model):
    better = db.ReferenceProperty(Vertex, collection_name = 'better_set')
    worse = db.ReferenceProperty(Vertex, collection_name = 'worse_set')
    count = db.IntegerProperty()

Но проблема, с которой я сталкиваюсь, заключается в том, что я должен сделать 4 отдельных уродливых запроса в соответствии с: 

edge = Edge.all().filter('better =', vertex1).filter('worse =', vertex2).get()

Затем мне нужно обновить и поместить () новые ребра в пятый запрос.

Более эффективной (меньше запросов), но хакерской реализацией была бы эта, которая использует пары списков для имитации диктов: 

class Vertex(db.Model):
    name = db.StringProperty()
    better_keys = db.ListProperty(db.Key)
    better_values = db.ListProperty(int)

Итак, чтобы добавить оценку, гласящую, что A лучше, чем B, я бы сделал: 

index = vertexA.index(vertexB.key())
vertexA.better_values[index] += 1

Есть ли более эффективный способ смоделировать это?

1 Ответ

1 голос
/ 25 июля 2011

Я решил свою собственную проблему с незначительной модификацией первого проекта, который я предложил в своем вопросе.

Я узнал об аргументе key_name , который позволяет мне устанавливать свои собственные имена ключей.Поэтому каждый раз, когда я создаю новое ребро, я передаю конструктору следующий аргумент: 

key_name = vertex1.name + ' > ' + vertex2.name

Затем, вместо многократного выполнения этого запроса: 

edge = Edge.all().filter('better =', vertex1).filter('worse =', vertex2).get()

Я могу получитькрая легко, так как я знаю, как построить их ключи.Используя метод Key.from_path () , я создаю список ключей, которые ссылаются на ребра.Каждый ключ получается следующим образом: 

db.Key.from_path('Edge', vertex1.name + ' > ' + vertex2.name)

Затем я передаю этот список ключей, чтобы получить все объекты в одном запросе.

...