1

我有以下 Django 模型：

class Mappings(models.Model):
    placeFrom = models.CharField(max_length=50)
    placeTo = models.CharField(max_length=50)
    totalTime = models.TimeField()

以下是表格的填充方式：

placeFrom       placeTo   totalTime     
new york        london        03:55
london          paris         22:33
london          new york      03: 23
amsterdam       london        82:39

这个想法是为没有直接连接的映射找到所有数据库行。例如，在这种情况下，纽约 - 巴黎没有直接连接。所以，返回的表行应该是

new york        london        03:55
london          paris         22:33

知道怎么做吗？我首先使用Mappings.objects.filter(placeTo="london"), 来获取代表“某个地方”和“伦敦”之间映射的所有行。所以，我知道如果“纽约”和'某个地方'返回，但不知道如何检查..

4

3 回答 3

2

这是一个图形问题，不是吗？您基本上需要建立一个图，其中节点是您的位置，边是您的映射（其中边长 = mapping.totalTime），然后应用相关的图搜索算法（例如Dijkstra 算法）来找到之间的最短路径相关节点。

不过，如果不先从数据库中获取所有映射并构建图表，我认为没有任何方法可以做到这一点。

于 2013-01-16T11:02:04.133 回答
2

您需要做一些事情，例如在哪里可以建立路线并轻松找出哪些位置（或节点）未连接。完成此操作后，您需要遵循@DanielRoseman 的建议并使用图形搜索算法来填补空白

import networkx as nx
G = nx.DiGraph()

G.add_node('new york')
G.add_node('london')
G.add_node('paris')
G.add_node('amsterdam')

G.add_edge('new york', 'london', weight=235)
G.add_edge('london', 'paris', weight=1353)
G.add_edge('london', 'new york', weight=203)
G.add_edge('amsterdam', 'london', weight=4959)

print 'All places not linked to new york:'
for location in nx.non_neighbors(G,'new york'):
    print location

nb 为了更清楚，我没有展示从模型中导入数据，但你明白了

你得到以下输出

All places not linked to new york:
paris
amsterdam
于 2013-01-16T11:26:19.133 回答
0

感谢您的建议，我选择从简单的解决方案开始，这远非理想，但它会帮助我找到更好的方法。这就是我现在得到的：

querySetToEndLocation = Mappings.objects.filter(placeTo="london")
toEnd = []
toMiddle = []
for row in querySetToEndLocation:
  locationFrom = row.placeFrom
  queryNew = Mappings.objects.filter(placeFrom="new york")
  for rowquery in queryNew:
    if locationFrom == rowquery.placeTo:
       toEnd.append(row)
       toMiddle.append(rowquery)
于 2013-01-16T15:59:53.380 回答