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

ルートを構築し、接続されていない場所 (またはノード) を簡単に引き出すことができる場所などを行う必要があります。これが完了したら、@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 に答える
2

これはグラフの問題ですね。基本的に、ノードが場所でエッジがマッピング (エッジの長さ = mapping.totalTime) であるグラフを作成し、関連するグラフ検索アルゴリズム (ダイクストラのアルゴリズムなど) を適用して、関連するノード。

ただし、最初にデータベースからすべてのマッピングを取得してグラフを作成しない限り、これを行う方法はないと思います。

于 2013-01-16T11:02:04.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 に答える