Structures_Graph_Manipulator_TopologicalSorter Class Reference

Static Public Member Functions
static	sort (&$graph)

Static Protected Member Functions
static	_nonVisitedInDegree (&$node)
static	_sort (&$graph)

Detailed Description

Definition at line 50 of file TopologicalSorter.php.

Member Function Documentation

_nonVisitedInDegree()

_nonVisitedInDegree ( & $node )

staticprotected

This is a variant of Structures_Graph::inDegree which does not count nodes marked as visited.

Parameters

object

$node

Node to check

Returns

integer Number of non-visited nodes that link to this one

Definition at line 60 of file TopologicalSorter.php.

    {
        $result = 0;
        $graphNodes =& $node->_graph->getNodes();
        foreach (array_keys($graphNodes) as $key) {
            if ((!$graphNodes[$key]->getMetadata('topological-sort-visited'))
                && $graphNodes[$key]->connectsTo($node)
            ) {
                $result++;
            }
        }
        return $result;
        
    }

References $result.

_sort()

_sort ( & $graph )

staticprotected

Sort implementation

Parameters

object

$graph

Graph to sort

Returns

void

Definition at line 82 of file TopologicalSorter.php.

    {
        // Mark every node as not visited
        $nodes =& $graph->getNodes();
        $nodeKeys = array_keys($nodes);
        $refGenerator = array();
        foreach ($nodeKeys as $key) {
            $refGenerator[] = false;
            $nodes[$key]->setMetadata(
                'topological-sort-visited',
                $refGenerator[sizeof($refGenerator) - 1]
            );
        }
 
        // Iteratively peel off leaf nodes
        $topologicalLevel = 0;
        do {
            // Find out which nodes are leafs (excluding visited nodes)
            $leafNodes = array();
            foreach ($nodeKeys as $key) {
                if ((!$nodes[$key]->getMetadata('topological-sort-visited'))
                    && static::_nonVisitedInDegree($nodes[$key]) == 0
                ) {
                    $leafNodes[] =& $nodes[$key];
                }
            }
            // Mark leafs as visited
            $refGenerator[] = $topologicalLevel;
            for ($i = sizeof($leafNodes) - 1; $i>=0; $i--) {
                $visited =& $leafNodes[$i]->getMetadata('topological-sort-visited');
                $visited = true;
                $leafNodes[$i]->setMetadata('topological-sort-visited', $visited);
                $leafNodes[$i]->setMetadata(
                    'topological-sort-level',
                    $refGenerator[sizeof($refGenerator) - 1]
                );
            }
            $topologicalLevel++;
        } while (sizeof($leafNodes) > 0);
 
        // Cleanup visited marks
        foreach ($nodeKeys as $key) {
            $nodes[$key]->unsetMetadata('topological-sort-visited');
        }
    }

Referenced by sort().

Here is the caller graph for this function:

sort()

sort ( & $graph )

static

Sort returns the graph's nodes, sorted by topological order.

The result is an array with as many entries as topological levels. Each entry in this array is an array of nodes within the given topological level.

Parameters

object

$graph

Graph to sort

Returns

array The graph's nodes, sorted by topological order.

Definition at line 139 of file TopologicalSorter.php.

    {
        // We only sort graphs
        if (!is_a($graph, 'Structures_Graph')) {
            return Pear::raiseError(
                'Structures_Graph_Manipulator_TopologicalSorter::sort received'
                . ' an object that is not a Structures_Graph',
                STRUCTURES_GRAPH_ERROR_GENERIC
            );
        }
        if (!Structures_Graph_Manipulator_AcyclicTest::isAcyclic($graph)) {
            return Pear::raiseError(
                'Structures_Graph_Manipulator_TopologicalSorter::sort'
                . ' received an graph that has cycles',
                STRUCTURES_GRAPH_ERROR_GENERIC
            );
        }
 
        Structures_Graph_Manipulator_TopologicalSorter::_sort($graph);
        $result = array();
 
        // Fill out result array
        $nodes =& $graph->getNodes();
        $nodeKeys = array_keys($nodes);
        foreach ($nodeKeys as $key) {
            if (!array_key_exists($nodes[$key]->getMetadata('topological-sort-level'), $result)) {
                $result[$nodes[$key]->getMetadata('topological-sort-level')]
                    = array();
            }
            $result[$nodes[$key]->getMetadata('topological-sort-level')][]
                =& $nodes[$key];
            $nodes[$key]->unsetMetadata('topological-sort-level');
        }
 
        return $result;
    }

References $result, _sort(), Structures_Graph_Manipulator_AcyclicTest\isAcyclic(), and STRUCTURES_GRAPH_ERROR_GENERIC.

Referenced by PEAR_Downloader\sortPackagesForInstall(), and TopologicalSorterTest\testSort().

Here is the call graph for this function:

Here is the caller graph for this function:

---

The documentation for this class was generated from the following file:

• E:/Bearsampp-development/sandbox/core/libs/php/pear/pear/Structures/Graph/Manipulator/TopologicalSorter.php