如何遍历一个有序的"network"？

Question

我有一个有趣的 python "network" 挑战。不确定要使用什么数据结构，希望能从专家那里学到新东西！

以下是来自有序 table（参见 SORT 列）的片段，其中包含 FROM NODE 和 TO NODE。这 table 表示从上游到下游的水文网络（流域排序）。 TO NODE = 0表示网络底部。

鉴于可以有很多分支，如何遍历从任何给定 FROM NODE 到 TO NODE = 0 的网络并存储排序的节点列表？

例如，开始于：

HYBAS_ID (this is same as FROM NODE)= 2120523430

参见 <---- 大约 2/3 向下，节点序列将包括以下内容：

[2120523430, 2120523020, 2120523290, 2120523280,2120523270,2120020790, 0]

Table:

 SORT   FROM NODE   TO NODE
30534   2121173490  2120522070
30533   2120521930  2120521630
30532   2120522070  2120521630
30531   2120521620  2120522930
30530   2120521630  2120522930
30529   2121172200  2121173080
30528   2120522930  2120523360
30527   2120522940  2120523360
30526   2120519380  2120523170
30525   2120519520  2120523170
30524   2120523440  2120523350
30523   2120523360  2120523350
30522   2120525750  2120523430
30521   2120525490  2120523430
30520   2121173080  2120522820
30519   2120523430  2120523020 <------- if you start network here
30518   2120523350  2120523020
30517   2120522820  2120523290
30516   2120523020  2120523290 <------ the second node is here
30515   2120523170  2120523280
30514   2120523290  2120523280 <------ third node here
30513   2120523160  2120523270
30512   2120523280  2120523270 <------ fourth
30511   2120523150  2120020790
30510   2120523270  2120020790 <------ fifth
30509   2120020790  0          <------ End.

字典和某种图形结构可以遍历这个网络吗？可能会向代码提供数千或数百万个 FROM NODES 的列表来计算路由，因此效率很重要。

Answer 1

执行此操作的标准方法是使用表示有向图的无序字典，然后遍历它。首先，您必须填充字典（为了论证，我们假设它是一个 csv），然后遍历这些值。所以

my_graph = {}
with open("myfile.csv") as f:
    for l in f:
        split_lines = l.split(",")
        my_graph[int(split_lines[1])] = int(split_lines[2])

HYBAS_ID = 2120523430
current_hybas = my_graph[HYBAS_ID]
return_value = [HYBAS_ID]
while current_hybas != 0:
    return_value.append(current_hybas)
    current_hybas = my_graph[current_hybas]

print return_value

应该能大致满足您的需求。

如何遍历一个有序的"network"？

How to traverse an ordered "network"?

python

networking

traversal

graph

sequence