В базе данных HANA есть возможность работать с графами. Есть WEB-визуализатор. Если говорить грубо, то при создании графа в HANA, мы создаем объект похожий на Calculation view. Если задача стоит найти кратчайшее расстояние эффективным способом, то тут могут возникнуть проблемы. Как выяснилось, алгоритм из коробки работает медленнее чем, написанный на ABAP. (С версии, кажется, SP2 есть модификация алгоритма в HANA для нахождения кратчайшего расстояния one-to-one, а не one-to-all, но проверить его я не могу)
Алгоритм Дейкстры
Алгоритм Дейкстры входит в университетский курс «Теории графов», так что заострять внимание на его работе в этой статье я не буду. Тем более в интернете есть масса источников. Из особенностей можно выделить, что мы ищем кратчайшее расстояние от одной вершины ко всем.
Инициализация
Таблица для хранения ребер ZSTATION_EDGES
Таблица содержит 27.328 записей, инициализировать вершины в этом алгоритме я не буду, вершины будут «набираться» по ходу расчета. Количество вершин составляет 13.371. Логику расчета я вынес в функциональный модуль, подпрограммы не используются для ускорения расчета.
Импорт модуля
Экспорт модуля
Структура ZROUSTE_T
Реализация алгоритма Дейкстры
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
constants int_max type i value 2147483647. types: begin of path_s_t, name type /bic/oistbeg, distance type /bic/oilengthm, end of path_s_t, path_s type standard table of path_s_t with non-unique default key, begin of node_s, name type /bic/oistbeg, path type path_s, " кратчайший путь до узла distance type /bic/oilengthm, "общее растояние до узла end of node_s. if edges is initial. select station_beg station_end weight from zstation_edges into table edges. endif. data: uncheckedNodes type sorted table of node_s with non-unique key primary_key components distance, checkedNodes type sorted table of node_s with unique key primary_key components name, startNode type node_s, newNode type node_s. startNode-name = start_node. insert startNode into table uncheckedNodes. data lowestDistanceNode type node_s. while lines( uncheckedNodes ) > 0. clear: lowestDistanceNode. * возвращает узел с наименьшей дистанцией lowestDistanceNode = uncheckedNodes[ 1 ]. delete table uncheckedNodes from lowestDistanceNode. * обходим все смежные узлы loop at edges assigning field-symbol(<edge>) where stbeg = lowestDistanceNode-name. clear newNode. if line_exists( checkedNodes[ name = <edge>-stend ] ). newNode = checkedNodes[ name = <edge>-stend ]. else. newNode-name = <edge>-stend. newNode-distance = int_max. endif. ****************** * вычисление наименьшей дистанции до начального узла if lowestDistanceNode-distance + <edge>-lengthm < newnode-distance. newNode-distance = lowestDistanceNode-distance + <edge>-lengthm. data(lowPath) = lowestDistanceNode-path. append initial line to lowPath assigning field-symbol(<patch_line>). <patch_line>-name = lowestDistanceNode-name. <patch_line>-distance = <edge>-lengthm. newNode-path = lowPath. endif. ****************** * если нашли путь до уже проверенного узла и он меньше if line_exists( checkedNodes[ name = newNode-name ] ). assign checkedNodes[ name = newNode-name ] to field-symbol(<choice_shortest>). if newNode-distance < <choice_shortest>-distance. delete table uncheckedNodes from <choice_shortest>. insert newNode into table checkedNodes. endif. else. insert newNode into table uncheckedNodes. endif. **** endloop. insert lowestDistanceNode into table checkedNodes. endwhile. |
На этом этапе в chekedNodes находятся кратчайшие маршруты от START_NODE до всех вершин.
Пример маршрута (поле PATH)
Так как мы ищем расстояние между двумя вершинами, то соберем ответ.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
lowestDistanceNode = checkedNodes[ name = end_node ]. check lines( lowestDistanceNode-path ) > 0. data: out_lines type zrouste_s. loop at lowestDistanceNode-path assigning field-symbol(<path>). if sy-tabix = 1. out_lines-st_beg = <path>-name. out_lines-length = <path>-distance. else. out_lines-st_end = <path>-name. out_lines-number = ITERATOR. append out_lines to output. iterator = iterator + 1. out_lines-st_beg = out_lines-st_end. out_lines-length = <path>-distance. endif. endloop. out_lines-number = iterator. out_lines-st_end = lowestdistancenode-name. out_lines-length = lowestdistancenode-path[ lines( lowestdistancenode-path ) ]-distance. append out_lines to output. |
Результат на тестовых вершинах, на изменяемые параметры можно не обращать внимание
Часть ответа
т.к. решение из коробки и реализованный алгоритм дали одинаковые результаты, можно говорить, что реализация работает верно.
Весь код можно посмотреть в GIT.