PHP排序依赖数组列表-拓扑排序

Question

我有一个带有依赖项的文件数组。我需要对它们进行排序，以便在它们的依赖项之后对所有相关文件进行索引。我曾多次尝试使用forEach循环，而循环，但是一旦一个依赖项被移动，循环就不会考虑以前的迭代，而索引元素最终会出现混乱。

我有一个我正在使用的数据的简化版本：

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

如果出现在元素中的句柄需要数组，则需要将该元素移动到指定的requires元素之前，这一切都是在维护以前考虑的任何其他依赖项的同时进行的。

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

我认为这里可能有一些递归的方法，在这一点上有点超出了我的技能范围。任何帮助都将不胜感激。

我确实找到了这样的解决方案：https://stackoverflow.com/questions/39711720/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;