PHP排序依賴項數組列表 - 拓撲排序

Question

我有一個具有依賴關係的文件數組。我需要對它們進行排序，以便所有依賴文件在其依賴關係之後進行索引。我已經用forEach循環做了很多嘗試，while循環，但是一旦移動了依賴關係，這些循環就不會考慮以前的迭代，並且索引元素會失序。

我有數據的簡化版本我正在與工作：

$dependencies = array(
     array(
      'handle' => 'jquery', 
      'requires' => array(
       'jquery-core', 
       'jquery-migrate' 
      ) 
     ), 
     array(
      'handle' => 'jquery-migrate', 
      'requires' => array() 
     ), 
     array(
      'handle' => 'common', 
      'requires' => array(
       'utils', 
       'jquery', 
       'jquery-core', 
       'jquery-migrate', 
       'jquery-effects-core', 
       'backbone' 
      ) 
     ), 
     array(
      'handle' => 'jquery-effects-core', 
      'requires' => array(
       'jquery', 
       'jquery-core', 
       'jquery-migrate' 
      ) 
     ), 
     array(
      'handle' => 'backbone', 
      'requires' => array(
       'underscore', 
       'jquery' 
      ) 
     ), 
     array(
      'handle' => 'underscore', 
      'requires' => array() 
     ), 
     array(
      'handle' => 'utils', 
      'requires' => array() 
     ), 
     array(
      'handle' => 'jquery-core', 
      'requires' => array() 
     ) 
    ); 

如果[把手]出現在一個元素[需要]數組，該元素需要被提前移動的指示的要求]元素，同時保持先前解釋的任何其他依賴關係。

function moveEle(&$array, $a, $b){ 
     $out   = array_splice($array, $a, 1); 
     array_splice($array, $b, 0, $out); 
    } 

    foreach($dependencies as $i=>$dependency){ 
     if(count($dependency['requires'])>0){ 
      $itr  = count($dependency['requires']); 
      echo $dependency['handle']."<br/>"; 
      while($itr > 0){ 
       // loop through current files required files 
       foreach($dependency['requires'] as $k=>$dep){ 
        // loop through dependencies array again to find required file handle 
        echo "-- " . $dep . "<br/>"; 
        foreach($dependencies as $j=>$jDep){ 
         // $j = index in dependencies array of required file, $i = index in dependencies array of dependent file. 
         if($dep === $jDep['handle'] && $j > $i){ 
          echo "found " . $jDep['handle'] . "@ " . $j."<br/>"; 
          moveEle(&$dependencies, $j, $i); 
         } 
        } 
        $itr--; 
       } 
      } 
     } 
    } 

我把它有可能是做一些這方面的遞歸的方式就是有點超出了我的技能的範圍在這一點上。任何幫助將不勝感激。

我沒有找到這個解決方案： PHP Order array based on elements dependency 它不工作，但是，一旦陣列到達150個文件（實際數據大小），超時或採取一個非常長的時間。如果存在的話，我想要一個更有效的解決方案。

Answer 1

好吧，我買了這個預期的效果：

/* 
     * 
     * @description  return nested array with all dependencies & sub dependencies 
     * 
    **/ 
    function getWithDependencies($dependency, $collection){ 
     $helper  = new Insight_WP_Scripts_Helpers(); 
     $set = array(
      'handle'  => $dependency, 
      'dependencies' => array() 
     ); 

     foreach($collection as $index=>$data){ 
      if($data['handle'] === $set['handle']){ 
       // echo "<h4>".$data['handle']."</h4>"; 
       if(count($helper->getDependencies($set, $collection))>0){ 
        $dependencies  = $helper->getDependencies($set['handle'], $collection); 
        foreach($dependencies as $i=>$dependency){ 
         // echo $dependency . "<br/>"; 
         $set['dependencies'][$i]  = array(
          'handle'  => $dependency, 
          'dependencies' => array() 
         ); 
         if(count($helper->getDependencies($dependency, $collection)) > 0){ 
          foreach(getWithDependencies($dependency, $collection) as $k=>$dep){ 
           $set['dependencies'][$i]['dependencies'] = $dep; 
          } 
         } 
        } 
       } 
      } 
     } 
     return $set; 
    } 

    /* 
     * 
     * @description  recursively sorts dependencies to depth returned by getWithDependencies() 
     * 
    **/ 
    function sortDependency($data,&$collection){ 
     $helper  = new Insight_WP_Scripts_Helpers(); 
     foreach($collection as $index=>$inst){ 
      if($inst['handle'] === $data['handle'] && count($data['dependencies'])>0){ 
       // iterate over each dependency 
       foreach($inst['dependencies'] as $i=>$dependency){ 
        // iterate over the collection to find dependencies position for comparison against dependent file. 
        foreach($collection as $k=>$kdep){ 
         if($kdep['handle'] === $dependency['handle'] && $index < $k){ 
          $helper->moveArrayElement($collection, $k, $index); 
          // call recursively to search full depth 
          if(count($dependency['dependencies']) > 0){ 
           sortDependency($dependency,$collection); 
          } 
         } 
        } 
       } 
      } 
     } 
    } 

    foreach($dependencies as $index=>$data){ 
     $fullDependencies  = array(); 
     foreach($dependencies as $i=>$dependency){ 
      $fullDependencies[]  = getWithDependencies($dependency['handle'], $dependencies); 
     } 
    } 
    $_fullDependencies = $fullDependencies; 
    foreach($fullDependencies as $index=>$data){ 
     sortDependency($data,$_fullDependencies); 
    } 
    $fullDependencies = $_fullDependencies; 
return $fullDependencies;