PHPソート依存関係配列リスト - トポロジカルソート

Question

私は依存関係のあるファイルの配列を持っています。私はそれらをソートする必要があるので、すべての依存ファイルは依存関係の後で索引付けされます。私はそれぞれのループに対して多くの試みを行いましたが、ループ中に、一度依存関係が移動されると、ループは以前の反復を考慮せず、インデックスされた要素は順不同です。

私は私が働いているデータの簡易版があります：[ハンドル]が要素に表示された場合

$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;