芝麻web文件管理V1.00
编辑当前文件:/home/mgatv524/public_html/avenida/views/Graph.tar
Manipulator/AcyclicTest.php 0000644 00000013201 14716372636 0011773 0 ustar 00 | // +-----------------------------------------------------------------------------+ // /** * 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 Srgio Carvalho
* @copyright (c) 2004 by Srgio 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); } /* }}} */ } /* }}} */ ?> Manipulator/TopologicalSorter.php 0000644 00000015564 14716372636 0013255 0 ustar 00 | // +-----------------------------------------------------------------------------+ // /** * This file contains the definition of the Structures_Graph_Manipulator_TopologicalSorter class. * * @package Structures_Graph */ require_once 'PEAR.php'; require_once 'Structures/Graph.php'; require_once 'Structures/Graph/Node.php'; require_once 'Structures/Graph/Manipulator/AcyclicTest.php'; /** * The Structures_Graph_Manipulator_TopologicalSorter is a manipulator * which is able to return the set of nodes in a graph, sorted by topological * order. * * A graph may only be sorted topologically iff it's a DAG. You can test it * with the Structures_Graph_Manipulator_AcyclicTest. * * @author Srgio Carvalho
* @copyright (c) 2004 by Srgio Carvalho * @see Structures_Graph_Manipulator_AcyclicTest * @package Structures_Graph */ class Structures_Graph_Manipulator_TopologicalSorter { /** * This is a variant of Structures_Graph::inDegree which does * not count nodes marked as visited. * * @param object $node Node to check * * @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('topological-sort-visited')) && $graphNodes[$key]->connectsTo($node) ) { $result++; } } return $result; } /** * Sort implementation * * @param object $graph Graph to sort * * @return void */ protected static function _sort(&$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( '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'); } } /** * 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. * * @param object $graph Graph to sort * * @return array The graph's nodes, sorted by topological order. */ public static function sort(&$graph) { // 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; } } ?> Node.php 0000644 00000025440 14716372636 0006166 0 ustar 00 | // +-----------------------------------------------------------------------------+ // /** * This file contains the definition of the Structures_Graph_Node class * * @see Structures_Graph_Node * @package Structures_Graph */ /* dependencies {{{ */ /** */ require_once 'PEAR.php'; /** */ require_once 'Structures/Graph.php'; /* }}} */ /* class Structures_Graph_Node {{{ */ /** * The Structures_Graph_Node class represents a Node that can be member of a * graph node set. * * A graph node can contain data. Under this API, the node contains default data, * and key index data. It behaves, thus, both as a regular data node, and as a * dictionary (or associative array) node. * * Regular data is accessed via getData and setData. Key indexed data is accessed * via getMetadata and setMetadata. * * @author Srgio Carvalho
* @copyright (c) 2004 by Srgio Carvalho * @package Structures_Graph */ /* }}} */ class Structures_Graph_Node { /* fields {{{ */ /** * @access private */ var $_data = null; /** @access private */ var $_metadata = array(); /** @access private */ var $_arcs = array(); /** @access private */ var $_graph = null; /* }}} */ /* Constructor {{{ */ /** * * Constructor * * @access public */ function __construct() { } /* }}} */ /* getGraph {{{ */ /** * * Node graph getter * * @return Structures_Graph Graph where node is stored * @access public */ function &getGraph() { return $this->_graph; } /* }}} */ /* setGraph {{{ */ /** * * Node graph setter. This method should not be called directly. Use Graph::addNode instead. * * @param Structures_Graph Set the graph for this node. * @see Structures_Graph::addNode() * @access public */ function setGraph(&$graph) { $this->_graph =& $graph; } /* }}} */ /* getData {{{ */ /** * * Node data getter. * * Each graph node can contain a reference to one variable. This is the getter for that reference. * * @return mixed Data stored in node * @access public */ function &getData() { return $this->_data; } /* }}} */ /* setData {{{ */ /** * * Node data setter * * Each graph node can contain a reference to one variable. This is the setter for that reference. * * @return mixed Data to store in node * @access public */ function setData(&$data) { $this->_data =& $data; } /* }}} */ /* metadataKeyExists {{{ */ /** * * Test for existence of metadata under a given key. * * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an * associative array or in a dictionary. This method tests whether a given metadata key exists for this node. * * @param string Key to test * @return boolean * @access public */ function metadataKeyExists($key) { return array_key_exists($key, $this->_metadata); } /* }}} */ /* getMetadata {{{ */ /** * * Node metadata getter * * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an * associative array or in a dictionary. This method gets the data under the given key. If the key does * not exist, an error will be thrown, so testing using metadataKeyExists might be needed. * * @param string Key * @param boolean nullIfNonexistent (defaults to false). * @return mixed Metadata Data stored in node under given key * @see metadataKeyExists * @access public */ function &getMetadata($key, $nullIfNonexistent = false) { if (array_key_exists($key, $this->_metadata)) { return $this->_metadata[$key]; } else { if ($nullIfNonexistent) { $a = null; return $a; } else { $a = Pear::raiseError('Structures_Graph_Node::getMetadata: Requested key does not exist', STRUCTURES_GRAPH_ERROR_GENERIC); return $a; } } } /* }}} */ /* unsetMetadata {{{ */ /** * * Delete metadata by key * * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an * associative array or in a dictionary. This method removes any data that might be stored under the provided key. * If the key does not exist, no error is thrown, so it is safe using this method without testing for key existence. * * @param string Key * @access public */ function unsetMetadata($key) { if (array_key_exists($key, $this->_metadata)) unset($this->_metadata[$key]); } /* }}} */ /* setMetadata {{{ */ /** * * Node metadata setter * * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an * associative array or in a dictionary. This method stores data under the given key. If the key already exists, * previously stored data is discarded. * * @param string Key * @param mixed Data * @access public */ function setMetadata($key, &$data) { $this->_metadata[$key] =& $data; } /* }}} */ /* _connectTo {{{ */ /** @access private */ function _connectTo(&$destinationNode) { $this->_arcs[] =& $destinationNode; } /* }}} */ /* connectTo {{{ */ /** * * Connect this node to another one. * * If the graph is not directed, the reverse arc, connecting $destinationNode to $this is also created. * * @param Structures_Graph_Node Node to connect to * @access public */ function connectTo(&$destinationNode) { // We only connect to nodes if (!is_a($destinationNode, 'Structures_Graph_Node')) return Pear::raiseError('Structures_Graph_Node::connectTo received an object that is not a Structures_Graph_Node', STRUCTURES_GRAPH_ERROR_GENERIC); // Nodes must already be in graphs to be connected if ($this->_graph == null) return Pear::raiseError('Structures_Graph_Node::connectTo Tried to connect a node that is not in a graph', STRUCTURES_GRAPH_ERROR_GENERIC); if ($destinationNode->getGraph() == null) return Pear::raiseError('Structures_Graph_Node::connectTo Tried to connect to a node that is not in a graph', STRUCTURES_GRAPH_ERROR_GENERIC); // Connect here $this->_connectTo($destinationNode); // If graph is undirected, connect back if (!$this->_graph->isDirected()) { $destinationNode->_connectTo($this); } } /* }}} */ /* getNeighbours {{{ */ /** * * Return nodes connected to this one. * * @return array Array of nodes * @access public */ function getNeighbours() { return $this->_arcs; } /* }}} */ /* connectsTo {{{ */ /** * * Test wether this node has an arc to the target node * * @return boolean True if the two nodes are connected * @access public */ function connectsTo(&$target) { if (version_compare(PHP_VERSION, '5.0.0') >= 0) { return in_array($target, $this->getNeighbours(), true); } $copy = $target; $arcKeys = array_keys($this->_arcs); foreach($arcKeys as $key) { /* ZE1 chokes on this expression: if ($target === $arc) return true; so, we'll use more convoluted stuff */ $arc =& $this->_arcs[$key]; $target = true; if ($arc === true) { $target = false; if ($arc === false) { $target = $copy; return true; } } } $target = $copy; return false; } /* }}} */ /* inDegree {{{ */ /** * * Calculate the in degree of the node. * * The indegree for a node is the number of arcs entering the node. For non directed graphs, * the indegree is equal to the outdegree. * * @return integer In degree of the node * @access public */ function inDegree() { if ($this->_graph == null) return 0; if (!$this->_graph->isDirected()) return $this->outDegree(); $result = 0; $graphNodes =& $this->_graph->getNodes(); foreach (array_keys($graphNodes) as $key) { if ($graphNodes[$key]->connectsTo($this)) $result++; } return $result; } /* }}} */ /* outDegree {{{ */ /** * * Calculate the out degree of the node. * * The outdegree for a node is the number of arcs exiting the node. For non directed graphs, * the outdegree is always equal to the indegree. * * @return integer Out degree of the node * @access public */ function outDegree() { if ($this->_graph == null) return 0; return sizeof($this->_arcs); } /* }}} */ } ?>