0

我一直在尝试在谷歌应用引擎上实现一个简单的图形搜索。这是我的第一个 gae 项目和 python 项目，以及图形搜索！所以边做边学（可能是错的）。我有一个大型 cvs 文件，其中包含作为 ndb 数据库上传的顶点之间的连接

class Connection(ndb.Model):
    vertexid = ndb.StringProperty()
    connectedto = ndb.StringProperty()

大约有 8000 个顶点，每个顶点都连接到其他几个，所以总共有大约 14000 个连接，所以连接 ndb 中有 14000 个实体。我已经猜想将每个顶点存储为具有重复连接变量的单个实体会更有效，但我不确定如何正确上传我的 cvs 数据来做到这一点。同样在这种情况下，我可以使用 id 作为键，并使用gets而不是下面的fetches，这可能会加快速度吗？

无论如何，我正在根据这篇文章中的一些 python 代码进行广度优先搜索如何在广度优先搜索中跟踪路径？，所以我使用了它并对其进行了一些修改以使其正常工作：

def bfs(origin, destination):   
queue = []
# push the first path into the queue
queue.append(str(origin.vertexid))
count = 0
while queue:
    # get the first path from the queue
    if len(queue) ==1:
        path = queue.pop(0)
        node = path
    else:
        path = queue.pop(0)
        node=path[-1]               
    # get the last node from the path

    # path found
    if node == destination.vertexid:
        return path
    if count>21000:
        return count
    # enumerate all adjacent nodes, construct a new path and push it into the queue
    nodeconns=Connection.query(Connection.vertexid == node).fetch(10)        
    for nodeconn in nodeconns:
        count = count+1
        new_path = []
        new_path.append(path)
        new_path.append(str(nodeconn.connectedto))
        queue.append(new_path)

因此，无论如何，它适用于彼此靠近的起点和终点（相隔 6 或 7 个连接），但对于相距较远的顶点，它的缩放比例似乎非常糟糕。

这是因为它必须从数据存储中读取所有数据吗？我不明白为什么即使尝试上限为 21000 次，它也这么慢，就像上面一样，在我的 SSD 笔记本电脑上需要 50 秒左右，然后在相当遥远的起点和目的地超时（计数> 21,000）。

结合正在进行的对 ndb 数据库的所有读取，这不能很好地在线运行（我只在本地运行它）。

所以...我想我的问题是，上面的算法是否存在一些根本缺陷？在谷歌应用引擎中运行基于 ndb 的图形搜索是一个愚蠢的想法吗？有没有更明智的方式来表示图表？也许有一些现有的软件包可以为我做到这一点？（我找到了一些 dijkstra 算法的代码，但不确定如何将它与我的数据接口）

谢谢！！

4

0 回答 0