Как обнаружить и избежать бесконечного цикла в PHP

Question

Этот вопрос не о ошибке в моем PHP-коде (на данный момент у меня нет PHP-скрипта, я все еще думаю об алгоритме). Вот в чем проблема:

В настоящее время я работаю над механическим кусочным менеджером, который мог бы построить механическую деталь на основе внутренней части (например, я получил кусок, который представляет собой велосипед, и для этой части, Мне нужно 2 колеса, 1 руль, а для колеса мне нужна шина и т. Д.).

Каждая внутренняя часть также является механической частью в моей базе данных и связана с уникальным идентификатором (и имеет папку, содержащую много PDF, много 3D-файлов и т. Д.).

У меня есть GUI (в HTML), представляющий мою базу данных, и каждая часть имеет кнопку «Создать», чтобы собрать все файлы, необходимые для создания внутренней части.

Например:

Мой велосипед имеет ID N ° 1, колесо имеет ID № 2, и руль имеет ID N ° 3.

Алгоритм довольно прост, но уязвим с бесконечным циклом.

Как я могу это сделать, чтобы избежать этого следующего случая: что, если моему велосипеду (id 1) нужно колесо (id 2), а моему колесу нужен велосипед ... которому нужно колесо, которому нужен велосипед ... ...?

Большое спасибо,

Answer 1

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

Вот некоторые шаблонный код, который вы можете использовать для вдохновения:

// Sample "database": 
$components = array(
    1 => array (
     "id" => 1, 
     "name" => "bike", 
     "needs" => array (
      array ("id" => 2, "count" => 2), // 2 wheels 
      array ("id" => 3, "count" => 1), // 1 handlebar 
     ), 
     "folder" => "/my/folders/bike" 
    ), 
    2 => array(
     "id" => 2, 
     "name" => "weel", 
     "needs" => array(
      array("id" => 4, "count" => 1), // 1 tire 
      array("id" => 1, "count" => 1) // 1 wheel?? - erroneous information! 
     ), 
     "folder" => "/my/folders/wheel" 
    ), 
    3 => array(
     "id" => 3, 
     "name" => "handlebar", 
     "needs" => array(), 
     "folder" => "/my/folders/handlebar" 
    ), 
    4 => array(
     "id" => 4, 
     "name" => "tire", 
     "needs" => array(), 
     "folder" => "/my/folders/tire" 
    ) 
); 

// Build function: returns a list of folders related 
// to all the parts of the given component. 
function build($componentId, $components, $hash = array()) { 
    // Protection against infinite recursion: 
    if (isset($hash[$componentId])) return []; 
    $elem = $components[$componentId]; 
    // set hash, keyed by component ID. 
    $hash[$componentId] = 1; 
    // Add folder for this component 
    $folders[] = $elem['folder']; 
    // Collect folders of dependent components recursively 
    foreach($elem['needs'] as $child) { 
     // ... pass the hash as third argument 
     $folders = array_merge($folders, build($child["id"], $components, $hash)); 
    } 
    return $folders; 
} 

// Example call: build component with ID 1, returning a list of folders: 
print_r (build(1, $components)); 

Выход выше код будет:

Array 
(
    [0] => /my/folders/bike 
    [1] => /my/folders/wheel 
    [2] => /my/folders/tire 
    [3] => /my/folders/handlebar 
) 

Так, когда велосипед был встречен во второй раз, это было просто игнорируется.

Answer 2

Вы должны дифференцировать ребенка-родительские отношения.

Велосипед может содержать колесо в качестве детского предмета, а на колесе может быть велосипед в качестве его родительского элемента. Также один винт и шина могут быть дочерними элементами колеса.

Навигация должен иметь одно направление: от родительских элементов до дочерних элементов или наоборот.