PHP sorting dependency array list - Topological Sorting

Question

I have an array of files with dependencies. I need them sorted so all dependent files are indexed after their dependency. I've made a lot of attempts with forEach loops, while loops, but once a dependency is moved, the loops don't account for previous iterations and indexed elements wind up out of order.

I have a simplified version of the data I am working with:

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

If [handle] appears in an elements [requires] array, that element needs to be moved ahead of the indicated [requires] element, all while maintaining any other dependencies previously accounted for.

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

I'm taking it there is probably some recursive way to do this that is a little beyond my scope of skill at this point. Any help would be greatly appreciated.

I did find this solution: PHP Order array based on elements dependency which does work, however, once the array gets to 150 files (the actual data size), it times out or takes an incredibly long time. I'd like a more efficient solution, if one exists.

Clinton · Accepted Answer · 2016-10-20 22:32:40Z

Well, I got the desired results with this:

/*
        *
        *   @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;

Collectives™ on Stack Overflow

PHP sorting dependency array list - Topological Sorting

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related