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

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

0 голосов
/ 09 июня 2018

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

id |childId

a |b

a |с

с |д

д |a

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

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

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

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

1 Ответ

0 голосов
/ 09 июня 2018

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

Учитывая плоский список отношений, он строит поиск, который затем используется в рекурсивной функции обхода.Функция обхода «запоминает» исходную часть, которая была запрошена ($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);
...