src/PEAR/Downloader.php
function sortPackagesForInstall(&$packages)
    {
        require_once 'Structures/Graph.php';
        require_once 'Structures/Graph/Node.php';
        require_once 'Structures/Graph/Manipulator/TopologicalSorter.php';
        $depgraph = new Structures_Graph(true);
        $nodes = array();
        $reg = &$this->config->getRegistry();
        foreach ($packages as $i => $package) {
            $pname = $reg->parsedPackageNameToString(
                array(
                    'channel' => $package->getChannel(),
                    'package' => strtolower($package->getPackage()),
                ));
            $nodes[$pname] = new Structures_Graph_Node;
            $nodes[$pname]->setData($packages[$i]);
            $depgraph->addNode($nodes[$pname]);
        }

        $deplinks = array();
        foreach ($nodes as $package => $node) {
            $pf = &$node->getData();
            $pdeps = $pf->getDeps(true);
            if (!$pdeps) {
                continue;
            }

            if ($pf->getPackagexmlVersion() == '1.0') {
                foreach ($pdeps as $dep) {
                    if ($dep['type'] != 'pkg' ||
                          (isset($dep['optional']) && $dep['optional'] == 'yes')) {
                        continue;
                    }

                    $dname = $reg->parsedPackageNameToString(
                          array(
                              'channel' => 'pear.php.net',
                              'package' => strtolower($dep['name']),
                          ));

                    if (isset($nodes[$dname])) {
                        if (!isset($deplinks[$dname])) {
                            $deplinks[$dname] = array();
                        }

                        $deplinks[$dname][$package] = 1;
                        // dependency is in installed packages
                        continue;
                    }

                    $dname = $reg->parsedPackageNameToString(
                          array(
                              'channel' => 'pecl.php.net',
                              'package' => strtolower($dep['name']),
                          ));

                    if (isset($nodes[$dname])) {
                        if (!isset($deplinks[$dname])) {
                            $deplinks[$dname] = array();
                        }

                        $deplinks[$dname][$package] = 1;
                        // dependency is in installed packages
                        continue;
                    }
                }
            } else {
                // the only ordering we care about is:
                // 1) subpackages must be installed before packages that depend on them
                // 2) required deps must be installed before packages that depend on them
                if (isset($pdeps['required']['subpackage'])) {
                    $t = $pdeps['required']['subpackage'];
                    if (!isset($t[0])) {
                        $t = array($t);
                    }

                    $this->_setupGraph($t, $reg, $deplinks, $nodes, $package);
                }

                if (isset($pdeps['group'])) {
                    if (!isset($pdeps['group'][0])) {
                        $pdeps['group'] = array($pdeps['group']);
                    }

                    foreach ($pdeps['group'] as $group) {
                        if (isset($group['subpackage'])) {
                            $t = $group['subpackage'];
                            if (!isset($t[0])) {
                                $t = array($t);
                            }

                            $this->_setupGraph($t, $reg, $deplinks, $nodes, $package);
                        }
                    }
                }

                if (isset($pdeps['optional']['subpackage'])) {
                    $t = $pdeps['optional']['subpackage'];
                    if (!isset($t[0])) {
                        $t = array($t);
                    }

                    $this->_setupGraph($t, $reg, $deplinks, $nodes, $package);
                }

                if (isset($pdeps['required']['package'])) {
                    $t = $pdeps['required']['package'];
                    if (!isset($t[0])) {
                        $t = array($t);
                    }

                    $this->_setupGraph($t, $reg, $deplinks, $nodes, $package);
                }

                if (isset($pdeps['group'])) {
                    if (!isset($pdeps['group'][0])) {
                        $pdeps['group'] = array($pdeps['group']);
                    }

                    foreach ($pdeps['group'] as $group) {
                        if (isset($group['package'])) {
                            $t = $group['package'];
                            if (!isset($t[0])) {
                                $t = array($t);
                            }

                            $this->_setupGraph($t, $reg, $deplinks, $nodes, $package);
                        }
                    }
                }
            }
        }

        $this->_detectDepCycle($deplinks);
        foreach ($deplinks as $dependent => $parents) {
            foreach ($parents as $parent => $unused) {
                $nodes[$dependent]->connectTo($nodes[$parent]);
            }
        }

        $installOrder = Structures_Graph_Manipulator_TopologicalSorter::sort($depgraph);
        $ret = array();
        for ($i = 0, $count = count($installOrder); $i < $count; $i++) {
            foreach ($installOrder[$i] as $index => $sortedpackage) {
                $data = &$installOrder[$i][$index]->getData();
                $ret[] = &$nodes[$reg->parsedPackageNameToString(
                          array(
                              'channel' => $data->getChannel(),
                              'package' => strtolower($data->getPackage()),
                          ))]->getData();
            }
        }

        $packages = $ret;
        return;
    }
function sortPackagesForInstall(&$packages)
    {
        require_once 'Structures/Graph.php';
        require_once 'Structures/Graph/Node.php';
        require_once 'Structures/Graph/Manipulator/TopologicalSorter.php';
        $depgraph = new Structures_Graph(true);
        $nodes = array();
        $reg = &$this->config->getRegistry();
        foreach ($packages as $i => $package) {
            $pname = $reg->parsedPackageNameToString(
                array(
                    'channel' => $package->getChannel(),
                    'package' => strtolower($package->getPackage()),
                ));
            $nodes[$pname] = new Structures_Graph_Node;
            $nodes[$pname]->setData($packages[$i]);
            $depgraph->addNode($nodes[$pname]);
        }

        $deplinks = array();
        foreach ($nodes as $package => $node) {
            $pf = &$node->getData();
            $pdeps = $pf->getDeps(true);
            if (!$pdeps) {
                continue;
            }

            if ($pf->getPackagexmlVersion() == '1.0') {
                foreach ($pdeps as $dep) {
                    if ($dep['type'] != 'pkg' ||
                          (isset($dep['optional']) && $dep['optional'] == 'yes')) {
                        continue;
                    }

                    $dname = $reg->parsedPackageNameToString(
                          array(
                              'channel' => 'pear.php.net',
                              'package' => strtolower($dep['name']),
                          ));

                    if (isset($nodes[$dname])) {
                        if (!isset($deplinks[$dname])) {
                            $deplinks[$dname] = array();
                        }

                        $deplinks[$dname][$package] = 1;
                        // dependency is in installed packages
                        continue;
                    }

                    $dname = $reg->parsedPackageNameToString(
                          array(
                              'channel' => 'pecl.php.net',
                              'package' => strtolower($dep['name']),
                          ));

                    if (isset($nodes[$dname])) {
                        if (!isset($deplinks[$dname])) {
                            $deplinks[$dname] = array();
                        }

                        $deplinks[$dname][$package] = 1;
                        // dependency is in installed packages
                        continue;
                    }
                }
            } else {
                // the only ordering we care about is:
                // 1) subpackages must be installed before packages that depend on them
                // 2) required deps must be installed before packages that depend on them
                if (isset($pdeps['required']['subpackage'])) {
                    $t = $pdeps['required']['subpackage'];
                    if (!isset($t[0])) {
                        $t = array($t);
                    }

                    $this->_setupGraph($t, $reg, $deplinks, $nodes, $package);
                }

                if (isset($pdeps['group'])) {
                    if (!isset($pdeps['group'][0])) {
                        $pdeps['group'] = array($pdeps['group']);
                    }

                    foreach ($pdeps['group'] as $group) {
                        if (isset($group['subpackage'])) {
                            $t = $group['subpackage'];
                            if (!isset($t[0])) {
                                $t = array($t);
                            }

                            $this->_setupGraph($t, $reg, $deplinks, $nodes, $package);
                        }
                    }
                }

                if (isset($pdeps['optional']['subpackage'])) {
                    $t = $pdeps['optional']['subpackage'];
                    if (!isset($t[0])) {
                        $t = array($t);
                    }

                    $this->_setupGraph($t, $reg, $deplinks, $nodes, $package);
                }

                if (isset($pdeps['required']['package'])) {
                    $t = $pdeps['required']['package'];
                    if (!isset($t[0])) {
                        $t = array($t);
                    }

                    $this->_setupGraph($t, $reg, $deplinks, $nodes, $package);
                }

                if (isset($pdeps['group'])) {
                    if (!isset($pdeps['group'][0])) {
                        $pdeps['group'] = array($pdeps['group']);
                    }

                    foreach ($pdeps['group'] as $group) {
                        if (isset($group['package'])) {
                            $t = $group['package'];
                            if (!isset($t[0])) {
                                $t = array($t);
                            }

                            $this->_setupGraph($t, $reg, $deplinks, $nodes, $package);
                        }
                    }
                }
            }
        }

        $this->_detectDepCycle($deplinks);
        foreach ($deplinks as $dependent => $parents) {
            foreach ($parents as $parent => $unused) {
                $nodes[$dependent]->connectTo($nodes[$parent]);
            }
        }

        $installOrder = Structures_Graph_Manipulator_TopologicalSorter::sort($depgraph);
        $ret = array();
        for ($i = 0, $count = count($installOrder); $i < $count; $i++) {
            foreach ($installOrder[$i] as $index => $sortedpackage) {
                $data = &$installOrder[$i][$index]->getData();
                $ret[] = &$nodes[$reg->parsedPackageNameToString(
                          array(
                              'channel' => $data->getChannel(),
                              'package' => strtolower($data->getPackage()),
                          ))]->getData();
            }
        }

        $packages = $ret;
        return;
    }
Sort a list of arrays of array(downloaded packagefilename) by dependency.

This uses the topological sort method from graph theory, and the
Structures_Graph package to properly sort dependencies for installation.
@param array an array of downloaded PEAR_Downloader_Packages
@return array array of array(packagefilename, package.xml contents)