Gam

??? 123123123123 ..................................................................................................................................... Gam

File manager - Edit - /opt/alt/php84/usr/share/pear/Structures/Graph/Manipulator/AcyclicTest.php

Back
<?php /* vim: set expandtab tabstop=4 shiftwidth=4 foldmethod=marker: / // +-----------------------------------------------------------------------------+ // \| Copyright (c) 2003 S�rgio Gon�alves Carvalho \| // +-----------------------------------------------------------------------------+ // \| This file is part of Structures_Graph. \| // \| \| // \| Structures_Graph is free software; you can redistribute it and/or modify \| // \| it under the terms of the GNU Lesser General Public License as published by \| // \| the Free Software Foundation; either version 2.1 of the License, or \| // \| (at your option) any later version. \| // \| \| // \| Structures_Graph is distributed in the hope that it will be useful, \| // \| but WITHOUT ANY WARRANTY; without even the implied warranty of \| // \| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the \| // \| GNU Lesser General Public License for more details. \| // \| \| // \| You should have received a copy of the GNU Lesser General Public License \| // \| along with Structures_Graph; if not, write to the Free Software \| // \| Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA \| // \| 02111-1307 USA \| // +-----------------------------------------------------------------------------+ // \| Author: S�rgio Carvalho <sergio.carvalho@portugalmail.com> \| // +-----------------------------------------------------------------------------+ // /* * This file contains the definition of the Structures_Graph_Manipulator_AcyclicTest graph manipulator. * * @see Structures_Graph_Manipulator_AcyclicTest * @package Structures_Graph / / dependencies {{{ / /* / require_once 'PEAR.php'; /* / require_once 'Structures/Graph.php'; /* / require_once 'Structures/Graph/Node.php'; / }}} / / class Structures_Graph_Manipulator_AcyclicTest {{{ / /* * The Structures_Graph_Manipulator_AcyclicTest is a graph manipulator * which tests whether a graph contains a cycle. * * The definition of an acyclic graph used in this manipulator is that of a * DAG. The graph must be directed, or else it is considered cyclic, even when * there are no arcs. * * @author S�rgio Carvalho <sergio.carvalho@portugalmail.com> * @copyright (c) 2004 by S�rgio Carvalho * @package Structures_Graph / class Structures_Graph_Manipulator_AcyclicTest { / _nonVisitedInDegree {{{ / /* * * This is a variant of Structures_Graph::inDegree which does * not count nodes marked as visited. * * @return integer Number of non-visited nodes that link to this one / protected static function _nonVisitedInDegree(&$node) { $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; } / }}} / / _isAcyclic {{{ / /* * Check if the graph is acyclic / protected static function _isAcyclic(&$graph) { // 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; } / }}} / / isAcyclic {{{ / /* * * isAcyclic returns true if a graph contains no cycles, false otherwise. * * @return boolean true iff graph is acyclic / public static function isAcyclic(&$graph) { // 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); } / }}} / } / }}} */ ?>