Плоская структура спецификации для иерархической, обнаружение циклов в вашем дереве / графике

Question

Плоская структура спецификации для иерархической, обнаружение циклов в вашем дереве / графике

У меня много<> множество таблиц, в которых хранятся данные иерархической ведомости, например:

id | childId

а | б

а | с

с | d

д |

Мне нужно найти замкнутые петли, как в этом случае d указывает на a, что разрушает систему, поскольку некоторые рекурсивные функции никогда не остановятся.

Моя идея состояла в том, чтобы преобразовать эту структуру данных из плоской в иерархическую, а затем выполнить итерацию по иерархической структуре с помощью рекурсии.

Я изучаю некоторые знания в Интернете и большинство решений по преобразованию плоской во вложенную структуру, рассмотрим случай, когда есть:

id | ParentID

структура, где элементы верхнего уровня имеют parentId установить корневое значение (например, ноль).

Я работаю разработчиком систем самообучения в течение многих лет, но в этот момент мне не хватает образования, которое многие из вас получили во время учебы 🙂

РЕДАКТИРОВАТЬ: графические примеры

Valid trees:
a)
A
/ \
B   C
\
D
/ \
E   F

b)

K -> E
/ \
G   B
/|\
H I J


Invalid tree (closed loop)
A
/ \
B   C<----\
\     |
D   /
/ \ /
E   F
\
G
/|\
H I J

0

flat hierarchical hierarchical-data hierarchy php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

После проб и ошибок вот что я придумал.

Учитывая плоский список отношений, он строит поиск, который затем используется в рекурсивной функции обхода. Функция обхода «запоминает» оригинальную деталь, которая была запрошена ($initialPart) и выдает исключение при обнаружении цикла.
Например. исключение: Loop detected: f=>c=>d=>f!

Автор сценария:

$rows = [
['assemblyId' => 'a', 'partId' => 'b'],
['assemblyId' => 'a', 'partId' => 'c'],
['assemblyId' => 'c', 'partId' => 'd'],
['assemblyId' => 'd', 'partId' => 'e'],
['assemblyId' => 'd', 'partId' => 'f'],
['assemblyId' => 'f', 'partId' => 'c'],
['assemblyId' => 'f', 'partId' => 'g'],
['assemblyId' => 'g', 'partId' => 'h'],
['assemblyId' => 'g', 'partId' => 'i'],
['assemblyId' => 'g', 'partId' => 'j'],
];

$assemblyLookup = [];
foreach ($rows as $row) {
$assemblyLookup[$row['assemblyId']][$row['partId']] = $row;
}

function getTree(&$part, $initialPart = null, $path = '', $level = 0, $maxLevel = 100) {
global $assemblyLookup;

if ($initialPart === null) {
$initialPart = $part;
}

if ($level >= $maxLevel) {
return;
}

$path .= '=>' . $part['partId'];
if (is_array($assemblyLookup[$part['partId']])) {
$lookup = $assemblyLookup[$part['partId']];
foreach ($lookup as $child) {

if ($child['partId'] === $initialPart['partId']) {
$circularPath = substr($path, 2) . '=>' . $child['partId'] . '!';
throw new Exception("Loop detected: " . $circularPath);
return;
}

$part['children'][$child['partId']] = $child;
getTree($part['children'][$child['partId']], $initialPart, $path, ++$level, $maxLevel);
}
} else {
$path .= ';';
$part['path'] = substr($path, 2); // Strip arrow from left side
}

return $part;

}

$part = ['partId' => 'f'];

$tree = getTree($part);

0