Как пройти через упорядоченную «сеть»? - PullRequest
Новая
       31

Как пройти через упорядоченную «сеть»?

0 голосов
/ 18 мая 2018

У меня есть интересный питонский "сетевой" вызов.Не уверен, какую конструкцию данных использовать, и я надеюсь узнать что-то новое от экспертов!

Ниже приведен фрагмент упорядоченной таблицы (см. Столбец SORT) с FROM NODE и TO NODE.Эта таблица представляет гидрологическую сеть (секвенирование водораздела) от верховья до низовья.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]

Таблица: 

 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 для расчета маршрутизации, поэтому эффективность важна.

1 Ответ

0 голосов
/ 18 мая 2018

Стандартный способ сделать это с помощью неупорядоченного словаря, представляющего ориентированный граф, а затем выполнить итерацию по нему.Сначала вы должны заполнить словарь (который, скажем, является 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

Должно примерно получить то, что вы хотите.

...