Structures_Graph_Manipulator_AcyclicTest Class Reference

Static Public Member Functions
static	isAcyclic (&$graph)

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

Detailed Description

Definition at line 55 of file AcyclicTest.php.

Member Function Documentation

_isAcyclic()

_isAcyclic ( & $graph )

staticprotected

Check if the graph is acyclic

Definition at line 79 of file AcyclicTest.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('acyclic-test-visited', $refGenerator[sizeof($refGenerator) - 1]);
        }
 
        // Iteratively peel off leaf nodes
        do {
            // Find out which nodes are leafs (excluding visited nodes)
            $leafNodes = array();
            foreach($nodeKeys as $key) {
                if ((!$nodes[$key]->getMetadata('acyclic-test-visited')) && Structures_Graph_Manipulator_AcyclicTest::_nonVisitedInDegree($nodes[$key]) == 0) {
                    $leafNodes[] =& $nodes[$key];
                }
            }
            // Mark leafs as visited
            for ($i=sizeof($leafNodes) - 1; $i>=0; $i--) {
                $visited =& $leafNodes[$i]->getMetadata('acyclic-test-visited');
                $visited = true;
                $leafNodes[$i]->setMetadata('acyclic-test-visited', $visited);
            }
        } while (sizeof($leafNodes) > 0);
 
        // If graph is a DAG, there should be no non-visited nodes. Let's try to prove otherwise
        $result = true;
        foreach($nodeKeys as $key) if (!$nodes[$key]->getMetadata('acyclic-test-visited')) $result = false;
        
        // Cleanup visited marks
        foreach($nodeKeys as $key) $nodes[$key]->unsetMetadata('acyclic-test-visited');
 
        return $result;
    }

References $result, and _nonVisitedInDegree().

Referenced by isAcyclic().

Here is the call graph for this function:

Here is the caller graph for this function:

_nonVisitedInDegree()

_nonVisitedInDegree ( & $node )

staticprotected

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

Returns

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

Definition at line 64 of file AcyclicTest.php.

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

References $result.

Referenced by _isAcyclic().

Here is the caller graph for this function:

isAcyclic()

isAcyclic ( & $graph )

static

isAcyclic returns true if a graph contains no cycles, false otherwise.

Returns

boolean true iff graph is acyclic

Definition at line 124 of file AcyclicTest.php.

                                              {
        // We only test graphs
        if (!is_a($graph, 'Structures_Graph')) return Pear::raiseError('Structures_Graph_Manipulator_AcyclicTest::isAcyclic received an object that is not a Structures_Graph', STRUCTURES_GRAPH_ERROR_GENERIC);
        if (!$graph->isDirected()) return false; // Only directed graphs may be acyclic
 
        return Structures_Graph_Manipulator_AcyclicTest::_isAcyclic($graph);
    }

References _isAcyclic(), and STRUCTURES_GRAPH_ERROR_GENERIC.

Referenced by Structures_Graph_Manipulator_TopologicalSorter\sort(), AcyclicTestTest\testIsAcyclicFalse(), and AcyclicTestTest\testIsAcyclicTrue().

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/AcyclicTest.php