<?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_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 S�rgio Carvalho <sergio.carvalho@portugalmail.com> * @copyright (c) 2004 by S�rgio 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); } /* }}} */ } ?>