我正在为我正在开发的应用程序使用GTFS提要。我正在尝试列出所选路线的所有站点。目前，我正试图按stop_sequence对列表进行排序，但这无法正常工作，因为有些行程不会到达每一站，而且我收到的数据会使stop_sequent在每一站的行程中增加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 Feed附带的其他数据？
更新为真实世界的示例
这里是获取路线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的链接。两个列表不同的第一个例子是在"COLUMBIA MALL&SOUTH RING RD eb"之后
http://mta.maryland.gov/sites/default/files/915May2011B.pdf
我正试图让这个应用程序对通勤者尽可能友好，但与通勤者通常使用的应用程序相比，当站点出现故障时，可能会引起很多混乱。
更新2:
我仍然不知道如何使用拓扑排序来获得正确的序列。是的，它可能会给出一个有效的序列，但不能保证它是通勤者容易识别的正确序列。让我们看看另一个使用我提供的pdf的例子。我们将看到行程1和5，直到"哥伦比亚购物中心"。我会创建以下边缘：
跳闸1创建的边缘
Cedar Lane --> Gray Star Way
Gray Star Way --> White Cord Way
...
Harpers Farm Rd --> Columbia Mall
从Trip 5创建的边缘
Lotte Plaza --> Columbia Mall
拓扑排序唯一能确保的是
对于从顶点u到顶点v的每个有向边uv，在排序中u在v之前
这意味着有多个有效订单，但只有一个是我想要的实际正确（但我无法渐进地选择这个订单而不是其他有效订单，至少我想不出）。
有效的排序可能是（这也是正确的）：
Lotte Plaza,
Cedar Lane
Gray Star
...
Columbia Mall
甚至
Cedar Lane
Gray Star
...
Lotte Plaza
Columbia Mall
正如你所看到的，根据拓扑排序，这两个都是有效的，但只有一个是我想要的。我想不出一种方法可以根据GTFS提要提供的数据一致地选择正确的序列。
如果我看错了方向，请告诉我。
您可以构建一个有向图（DAG），其中属于一条路线的每个站点都是一个节点，一次旅行中两个站点之间的每个转换都是一条边。然后，你可以对图进行拓扑排序(http://en.wikipedia.org/wiki/Topological_sorting)以获得停靠站的顺序。请注意，拓扑排序只适用于没有循环的图，但有些trip实际上有循环，所以如果它创建了循环，您就不想添加边。
这恰好是OneBusAway应用程序套件用于排序站点的算法：https://github.com/OneBusAway/onebusaway-application-modules/blob/master/onebusaway-transit-data-federation/src/main/java/org/onebusaway/transit_data_federation/impl/beans/RouteBeanServiceImpl.java#L281
请注意，有时路线会有岔路口或分支，其中有两组停靠站（每个分支一个）彼此不交互。一个简单的拓扑排序可能会任意交错这些停止，但OBA代码使用以下两种启发式方法来获得更自然的排序：
1） 组在同一分支中一起停止。
2） 当相对于彼此排列两个分支时，请先将分支放在离分支点较近的位置。
对于任何遇到这个问题的人来说，这就是我几年前解决这个问题的方法。
没有一个正确的序列——这里的目标是产生一个"视觉上最优"的序列（在大多数情况下）。与其看单个的停止，我已经将停止分组为逻辑部分，然后将这些部分合并在一起，这与拓扑排序没有太大的不同。
然后，您可以将其他规则/权重添加到不相关的部分，以确定哪个部分应优先于另一个部分。例如ABC--->CDE或GHI
https://github.com/mhkey/supersequence
构建和排序一个站点的DAG（有向无循环图）就足够简单了。从本质上讲，我们将每一次行程的停止序列合并为一个整体停止序列。
唯一令人讨厌的是，你大多数情况下都会提前处理所有行程，以确保所有站点都被覆盖。因此，这可能需要一些时间，这取决于你的系统中有多少次旅行。
我们首先需要一些代码来对DAG进行排序。请记住，以下JavaScript代码尚未经过广泛测试。
/**
* This function sorts a directed acyclic graph (DAG) using depth-first search (DFS).
*
* @example
*
* const edges = [
* ["a", "b"],
* ["a", "c"],
* ["a", "e"],
* ["b", "d"],
* ["c", "d"],
* ["d", "e"],
* ];
*
* const order = sort_dag_dfs(edges); // ["a", "c", "b", "d", "e"]
*/
export const sort_dag_dfs = (edges) => {
const nodes = new Set();
const edges_map = new Map();
for (const [from, to] of edges) {
nodes.add(from);
nodes.add(to);
if (!edges_map.has(from)) {
edges_map.set(from, new Set());
}
edges_map.get(from).add(to);
}
const visited = new Set();
const stack = [];
const dfs = (node) => {
if (visited.has(node)) {
return;
}
visited.add(node);
if (edges_map.has(node)) {
for (const to of edges_map.get(node)) {
dfs(to);
}
}
stack.push(node);
};
for (const node of nodes) {
dfs(node);
}
return stack.reverse();
};
现在我们需要迭代一条路线的所有行程。对于每次旅行，我们添加一个"；边缘"；对于每一对连续的停车，这本质上是一个约束，即一个停车必须在另一个停车之后。将这些约束条件组合以获得最终序列。
这里有一些伪代码：
const edges = new Set();
for (const trip of trips) {
const stops = [];
for (const stop_idx of trip.sorted_stop_indices) {
stops.push(trip.stop_ids.get(stop_idx));
}
for (let i = 1; i < stops.length; i++) {
edges.add(`${stops[i - 1]}---${stops[i]}`);
}
}
const sorted_stop_ids = sort_dag_dfs(Array.from(edges).map((edge) => edge.split("---")));
请注意，可以有多个正确的排序，并且可能值得进一步增强基于站点的GPS坐标的排序。如果下一个可能出现两个站点（例如，有一个分支），则可能值得选择距离上一个站点较近的站点。