作業中のアプリに GTFS フィードを使用しています。選択したルートのすべての停留所をリストしようとしています。現在、リストを stop_sequence で並べ替えようとしていますが、一部のルートはすべての停留所に行くわけではなく、受信したデータによって stop_sequence が各停車地ごとに 1 ずつ増加するため、正しく機能していません。これの重要性は、stop_sequence が、多かれ少なかれ停車する可能性のある他のルートを考慮していないことです。
次に例を示します。
これは、ルートの停車地の順序です (すべてのルートが各停車地に停車するわけではないという事実は無視してください)。
Stop A
Stop B
Stop C
Stop D
Stop E
次に、ルートの旅行の例をいくつか示します。
Trip 1: A, B, C, D
Trip 2: A, B, E
私のデータが行っていること:
トリップ 1 の場合:
Stop A: stop_sequence = 1
Stop B: stop_sequence = 2
Stop C: stop_sequence = 3
Stop D: stop_sequence = 4
トリップ 2 の場合:
Stop A: stop_sequence = 1
Stop B: stop_sequence = 2
Stop E: stop_sequence = 3
したがって、ルートのすべての潜在的な停車地を注文しようとすると、次のようになります。
Stop A
Stop B
Stop C
Stop E
Stop D
これは明らかに間違っています。
おそらくGTFSフィードに付属する他のデータを使用して、ストップを正しく順序付けるための他の潜在的なアイデアを知っている人はいますか?
実際の例で更新
ルート 915 のすべての停留所を取得するデータベース クエリの出力例を次に示します。これは AM スケジュール用です。
+---------+---------+---------------+------------------------------------------------+
| stop_id | trip_id | stop_sequence | stop_name |
+---------+---------+---------------+------------------------------------------------+
| 11771 | 1269287 | 1 | LOTTE PLAZA US 40 & US 29 |
| 11772 | 1269280 | 1 | HARPER'S FARM RD & CEDAR LA eb |
| 11773 | 1269280 | 2 | LITTLE PATUXENT & GRAY STAR wb |
| 11774 | 1269280 | 3 | LITTLE PATUXENT & WHITE CORD WAY wb |
| 11775 | 1269280 | 4 | LITTLE PATUXENT & BRIGHT PASSAGE eb |
| 11776 | 1269280 | 5 | LITTLE PATUXENT & HICKORY RID nb |
| 11777 | 1269280 | 6 | LITTLE PATUXENT & CEDAR LA eb |
| 11778 | 1269280 | 7 | LITTLE PATUXENT & HARPER'S FARM opp eb |
| 11779 | 1269280 | 8 | COLUMBIA MALL & SOUTH RING RD eb |
| 11782 | 1269280 | 9 | BROKEN LAND & HICKORY RIDGE sb |
| 11780 | 1269289 | 9 | LITTLE PATUXENT & GOV WARFIELD nb |
| 11783 | 1269280 | 10 | BROKEN LAND PARK & RIDE |
| 11781 | 1269289 | 10 | LITTLE PATUXENT & VANTAGE PT nb |
| 11784 | 1269280 | 11 | SCAGGSVILLE PARK & RIDE |
| 11785 | 1269280 | 12 | BURTONSVILLE PARK & RIDE |
| 11786 | 1269280 | 13 | COLESVILLE RD & FENTON ST sb |
| 11787 | 1269280 | 14 | SILVER SPRING METRO STATION |
| 11788 | 1269280 | 15 | WALTER REED HOSP & 16TH ST NW |
| 11789 | 1269280 | 16 | 16TH ST & P ST NW |
| 11790 | 1269280 | 17 | 16TH ST & M ST NW |
| 11718 | 1269280 | 18 | K ST & 16TH ST NW fs eb |
| 11719 | 1269280 | 19 | K ST & 14TH ST NW eb |
| 11791 | 1269280 | 20 | 13TH ST & H ST NW sb |
| 11759 | 1269280 | 21 | PENNSYLVANIA AVE & 12TH ST NW eb |
| 11793 | 1269280 | 22 | CONSTITUTION AVE & 10TH ST NW fs eb |
| 12046 | 1269280 | 23 | 7TH ST NW & CONSTITUTION AVE eb |
| 11650 | 1269280 | 24 | INDEPENDENCE AVE & 7/6 ST SW mid eb |
| 11601 | 1269280 | 25 | INDEPENDENCE AVE & 4TH/3RD ST SW eb |
| 13627 | 1269280 | 26 | M ST & 1st ST SE (NAVY YARD) sb |
| 13628 | 1269280 | 27 | M ST & 4th ST SE (SOUTHEAST FEDERAL CENTER) eb |
| 11569 | 1269280 | 28 | M ST & ISAAC HALL AVE SE eb |
| 11795 | 1269280 | 29 | M ST & 8/9TH STS mid eb |
+---------+---------+---------------+------------------------------------------------+
そして、多くの通勤者が現在使用している時刻表の PDF へのリンクです。2 つのリストが異なる最初の例は、「COLUMBIA MALL & SOUTH RING RD eb」の後です。
http://mta.maryland.gov/sites/default/files/915May2011B.pdf
私はこのアプリを通勤者にできるだけ使いやすいものにしようとしていますが、通勤者が通常使用するものと比較して停留所がずれていると、多くの混乱を招く可能性があります.
更新 2:
正しいシーケンスを取得するためにトポロジカル ソートをどのように使用できるかはまだわかりません。はい、有効なシーケンスを提供する可能性がありますが、通勤者が簡単に認識できる正しいシーケンスであるとは限りません。私が提供した pdf を使用した別の例を見てみましょう。Trips 1 と 5、そして停留所 "Columbia Mall" までを見ていきます。次のエッジを作成します。
トリップ 1 から作成されたエッジ
Cedar Lane --> Gray Star Way
Gray Star Way --> White Cord Way
...
Harpers Farm Rd --> Columbia Mall
トリップ 5 から作成されたエッジ
Lotte Plaza --> Columbia Mall
トポロジカルソートが保証する唯一のことは
頂点 u から頂点 v へのすべての有向辺 uv に対して、u は順序で v の前に来る
つまり、有効な順序が複数あることを意味しますが、実際に正しいのは1 つだけです (ただし、少なくとも私が考えることができる他の有効な順序よりもプログラム的にこれを選択する方法はありません)。
有効な順序は次のようになります (これも正しい順序です)。
Lotte Plaza,
Cedar Lane
Gray Star
...
Columbia Mall
あるいは
Cedar Lane
Gray Star
...
Lotte Plaza
Columbia Mall
ご覧のとおり、トポロジーの並べ替えによると、これらは両方とも有効ですが、必要なものは 1 つだけです。GTFS フィードによって提供されるデータに基づいて、一貫して正しいシーケンスを選択する方法が思いつきません。
これを間違った方法で見ている場合はお知らせください。