[Sommaire] [Imprimer]

   1  <?php
   2  /* vim: set expandtab tabstop=4 shiftwidth=4 foldmethod=marker: */
   3  // +-----------------------------------------------------------------------------+
   4  // | Copyright (c) 2003 Sérgio Gonçalves Carvalho                                |
   5  // +-----------------------------------------------------------------------------+
   6  // | This file is part of Structures_Graph.                                      |
   7  // |                                                                             |
   8  // | Structures_Graph is free software; you can redistribute it and/or modify    |
   9  // | it under the terms of the GNU Lesser General Public License as published by |
  10  // | the Free Software Foundation; either version 2.1 of the License, or         |
  11  // | (at your option) any later version.                                         |
  12  // |                                                                             |
  13  // | Structures_Graph is distributed in the hope that it will be useful,         |
  14  // | but WITHOUT ANY WARRANTY; without even the implied warranty of              |
  15  // | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               |
  16  // | GNU Lesser General Public License for more details.                         |
  17  // |                                                                             |
  18  // | You should have received a copy of the GNU Lesser General Public License    |
  19  // | along with Structures_Graph; if not, write to the Free Software             |
  20  // | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA                    |
  21  // | 02111-1307 USA                                                              |
  22  // +-----------------------------------------------------------------------------+
  23  // | Author: Sérgio Carvalho <sergio.carvalho@portugalmail.com>                  |
  24  // +-----------------------------------------------------------------------------+
  25  //
  26  /**
  27   * This file contains the definition of the Structures_Graph_Node class
  28   * 
  29   * @see Structures_Graph_Node
  30   * @package Structures_Graph
  31   */
  32  
  33  /* dependencies {{{ */
  34  /** */
  35  require_once  'PEAR.php';
  36  /** */
  37  require_once  'Structures/Graph.php';
  38  /* }}} */
  39  
  40  /* class Structures_Graph_Node {{{ */
  41  /**
  42   * The Structures_Graph_Node class represents a Node that can be member of a 
  43   * graph node set.
  44   *
  45   * A graph node can contain data. Under this API, the node contains default data, 
  46   * and key index data. It behaves, thus, both as a regular data node, and as a 
  47   * dictionary (or associative array) node.
  48   * 
  49   * Regular data is accessed via getData and setData. Key indexed data is accessed
  50   * via getMetadata and setMetadata.
  51   *
  52   * @author        Sérgio Carvalho <sergio.carvalho@portugalmail.com> 
  53   * @copyright    (c) 2004 by Sérgio Carvalho
  54   * @package Structures_Graph
  55   */
  56  /* }}} */
  57  class Structures_Graph_Node {
  58      /* fields {{{ */
  59      /** 
  60       * @access private 
  61       */
  62      var $_data = null;
  63      /** @access private */
  64      var $_metadata = array();
  65      /** @access private */
  66      var $_arcs = array();
  67      /** @access private */
  68      var $_graph = null;
  69      /* }}} */
  70  
  71      /* Constructor {{{ */
  72      /**
  73      *
  74      * Constructor
  75      *
  76      * @access    public
  77      */
  78      function Structures_Graph_Node() {
  79      }
  80      /* }}} */
  81  
  82      /* getGraph {{{ */
  83      /**
  84      *
  85      * Node graph getter
  86      *
  87      * @return    Structures_Graph    Graph where node is stored
  88      * @access    public
  89      */
  90      function &getGraph() {
  91          return $this->_graph;
  92      }
  93      /* }}} */
  94  
  95      /* setGraph {{{ */
  96      /**
  97      *
  98      * Node graph setter. This method should not be called directly. Use Graph::addNode instead.
  99      *
 100      * @param    Structures_Graph   Set the graph for this node. 
 101      * @see      Structures_Graph::addNode()
 102      * @access    public
 103      */
 104      function setGraph(&$graph) {
 105          $this->_graph =& $graph;
 106      }
 107      /* }}} */
 108  
 109      /* getData {{{ */
 110      /**
 111      *
 112      * Node data getter.
 113      * 
 114      * Each graph node can contain a reference to one variable. This is the getter for that reference.
 115      *
 116      * @return    mixed    Data stored in node
 117      * @access    public
 118      */
 119      function &getData() {
 120          return $this->_data;
 121      }
 122      /* }}} */
 123  
 124      /* setData {{{ */
 125      /**
 126      *
 127      * Node data setter
 128      *
 129      * Each graph node can contain a reference to one variable. This is the setter for that reference.
 130      *
 131      * @return    mixed    Data to store in node
 132      * @access    public
 133      */
 134      function setData($data) {
 135          $this->_data =& $data;
 136      }
 137      /* }}} */
 138  
 139      /* metadataKeyExists {{{ */
 140      /**
 141      *
 142      * Test for existence of metadata under a given key.
 143      *
 144      * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an 
 145      * associative array or in a dictionary. This method tests whether a given metadata key exists for this node.
 146      *
 147      * @param    string    Key to test
 148      * @return    boolean     
 149      * @access    public
 150      */
 151      function metadataKeyExists($key) {
 152          return array_key_exists($key, $this->_metadata);
 153      }
 154      /* }}} */
 155  
 156      /* getMetadata {{{ */
 157      /**
 158      *
 159      * Node metadata getter
 160      *
 161      * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an 
 162      * associative array or in a dictionary. This method gets the data under the given key. If the key does
 163      * not exist, an error will be thrown, so testing using metadataKeyExists might be needed.
 164      *
 165      * @param    string  Key
 166      * @param    boolean nullIfNonexistent (defaults to false).
 167      * @return    mixed    Metadata Data stored in node under given key
 168      * @see      metadataKeyExists
 169      * @access    public
 170      */
 171      function &getMetadata($key, $nullIfNonexistent = false) {
 172          if (array_key_exists($key, $this->_metadata)) {
 173              return $this->_metadata[$key];
 174          } else {
 175              if ($nullIfNonexistent) {
 176                  $a = null;
 177                  return $a;
 178              } else {
 179                  $a = Pear::raiseError('Structures_Graph_Node::getMetadata: Requested key does not exist', STRUCTURES_GRAPH_ERROR_GENERIC);
 180                  return $a;
 181              }
 182          }
 183      }
 184      /* }}} */
 185  
 186      /* unsetMetadata {{{ */
 187      /**
 188      *
 189      * Delete metadata by key
 190      *
 191      * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an 
 192      * associative array or in a dictionary. This method removes any data that might be stored under the provided key.
 193      * If the key does not exist, no error is thrown, so it is safe using this method without testing for key existence.
 194      *
 195      * @param    string  Key
 196      * @access    public
 197      */
 198      function unsetMetadata($key) {
 199          if (array_key_exists($key, $this->_metadata)) unset($this->_metadata[$key]);
 200      }
 201      /* }}} */
 202  
 203      /* setMetadata {{{ */
 204      /**
 205      *
 206      * Node metadata setter
 207      *
 208      * Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an 
 209      * associative array or in a dictionary. This method stores data under the given key. If the key already exists,
 210      * previously stored data is discarded.
 211      *
 212      * @param    string  Key
 213      * @param    mixed   Data 
 214      * @access    public
 215      */
 216      function setMetadata($key, $data) {
 217          $this->_metadata[$key] =& $data;
 218      }
 219      /* }}} */
 220  
 221      /* _connectTo {{{ */
 222      /** @access private */
 223      function _connectTo(&$destinationNode) {
 224          $this->_arcs[] =& $destinationNode;
 225      }
 226      /* }}} */
 227  
 228      /* connectTo {{{ */
 229      /**
 230      *
 231      * Connect this node to another one.
 232      * 
 233      * If the graph is not directed, the reverse arc, connecting $destinationNode to $this is also created.
 234      *
 235      * @param    Structures_Graph Node to connect to
 236      * @access    public
 237      */
 238      function connectTo(&$destinationNode) {
 239          // We only connect to nodes
 240          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);
 241          // Nodes must already be in graphs to be connected
 242          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);
 243          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);
 244          // Connect here
 245          $this->_connectTo($destinationNode);
 246          // If graph is undirected, connect back
 247          if (!$this->_graph->isDirected()) {
 248              $destinationNode->_connectTo($this);
 249          }
 250      }
 251      /* }}} */
 252  
 253      /* getNeighbours {{{ */
 254      /**
 255      *
 256      * Return nodes connected to this one.
 257      * 
 258      * @return   array   Array of nodes
 259      * @access    public
 260      */
 261      function getNeighbours() {
 262          return $this->_arcs;
 263      }
 264      /* }}} */
 265  
 266      /* connectsTo {{{ */
 267      /**
 268      *
 269      * Test wether this node has an arc to the target node
 270      *
 271      * @return    boolean   True if the two nodes are connected
 272      * @access    public
 273      */
 274      function connectsTo(&$target) {
 275          $copy = $target;
 276          $arcKeys = array_keys($this->_arcs);
 277          foreach($arcKeys as $key) {
 278              /* ZE1 chokes on this expression:
 279                  if ($target === $arc) return true;
 280                so, we'll use more convoluted stuff
 281              */
 282              $arc =& $this->_arcs[$key];
 283              $target = true;
 284              if ($arc === true) {
 285                  $target = false;
 286                  if ($arc === false) {
 287                      $target = $copy;
 288                      return true;
 289                  }
 290              }
 291          }
 292          $target = $copy;
 293          return false;
 294      }
 295      /* }}} */
 296  
 297      /* inDegree {{{ */
 298      /**
 299      *
 300      * Calculate the in degree of the node.
 301      * 
 302      * The indegree for a node is the number of arcs entering the node. For non directed graphs, 
 303      * the indegree is equal to the outdegree.
 304      *
 305      * @return    integer     In degree of the node
 306      * @access    public
 307      */
 308      function inDegree() {
 309          if ($this->_graph == null) return 0;
 310          if (!$this->_graph->isDirected()) return $this->outDegree();
 311          $result = 0;
 312          $graphNodes =& $this->_graph->getNodes();
 313          foreach (array_keys($graphNodes) as $key) {
 314              if ($graphNodes[$key]->connectsTo($this)) $result++;
 315          }
 316          return $result;
 317          
 318      }
 319      /* }}} */
 320  
 321      /* outDegree {{{ */
 322      /**
 323      *
 324      * Calculate the out degree of the node.
 325      *
 326      * The outdegree for a node is the number of arcs exiting the node. For non directed graphs,
 327      * the outdegree is always equal to the indegree.
 328      * 
 329      * @return    integer     Out degree of the node
 330      * @access    public
 331      */
 332      function outDegree() {
 333          if ($this->_graph == null) return 0;
 334          return sizeof($this->_arcs);
 335      }
 336      /* }}} */
 337  }
 338  ?>