[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   * The Graph.php file contains the definition of the Structures_Graph class 
  28   *
  29   * @see Structures_Graph
  30   * @package Structures_Graph
  31   */
  32  
  33  /* dependencies {{{ */
  34  /** PEAR base classes */
  35  require_once  'PEAR.php';
  36  /** Graph Node */
  37  require_once  'Structures/Graph/Node.php';
  38  /* }}} */
  39  
  40  define('STRUCTURES_GRAPH_ERROR_GENERIC', 100);
  41  
  42  /* class Structures_Graph {{{ */
  43  /**
  44   * The Structures_Graph class represents a graph data structure. 
  45   *
  46   * A Graph is a data structure composed by a set of nodes, connected by arcs.
  47   * Graphs may either be directed or undirected. In a directed graph, arcs are 
  48   * directional, and can be traveled only one way. In an undirected graph, arcs
  49   * are bidirectional, and can be traveled both ways.
  50   *
  51   * @author        Sérgio Carvalho <sergio.carvalho@portugalmail.com> 
  52   * @copyright    (c) 2004 by Sérgio Carvalho
  53   * @package Structures_Graph
  54   */
  55  /* }}} */
  56  class Structures_Graph {
  57      /* fields {{{ */
  58      /**
  59       * @access private
  60       */
  61      var $_nodes = array();
  62      /**
  63       * @access private
  64       */
  65      var $_directed = false;
  66      /* }}} */
  67  
  68      /* Constructor {{{ */
  69      /**
  70      *
  71      * Constructor
  72      *
  73      * @param    boolean    Set to true if the graph is directed. Set to false if it is not directed. (Optional, defaults to true)
  74      * @access    public
  75      */
  76      function Structures_Graph($directed = true) {
  77          $this->_directed = $directed;
  78      }
  79      /* }}} */
  80  
  81      /* isDirected {{{ */
  82      /**
  83      *
  84      * Return true if a graph is directed
  85      *
  86      * @return    boolean     true if the graph is directed
  87      * @access    public
  88      */
  89      function isDirected() {
  90          return (boolean) $this->_directed;
  91      }
  92      /* }}} */
  93  
  94      /* addNode {{{ */
  95      /**
  96      *
  97      * Add a Node to the Graph
  98      *
  99      * @param    Structures_Graph_Node   The node to be added.
 100      * @access    public
 101      */
 102      function addNode(&$newNode) {
 103          // We only add nodes
 104          if (!is_a($newNode, 'Structures_Graph_Node')) return Pear::raiseError('Structures_Graph::addNode received an object that is not a Structures_Graph_Node', STRUCTURES_GRAPH_ERROR_GENERIC);
 105          // Graphs are node *sets*, so duplicates are forbidden. We allow nodes that are exactly equal, but disallow equal references.
 106          foreach($this->_nodes as $key => $node) {
 107              /*
 108               ZE1 equality operators choke on the recursive cycle introduced by the _graph field in the Node object.
 109               So, we'll check references the hard way (change $this->_nodes[$key] and check if the change reflects in 
 110               $node)
 111              */
 112              $savedData = $this->_nodes[$key];
 113              $referenceIsEqualFlag = false;
 114              $this->_nodes[$key] = true;
 115              if ($node === true) {
 116                  $this->_nodes[$key] = false;
 117                  if ($node === false) $referenceIsEqualFlag = true;
 118              }
 119              $this->_nodes[$key] = $savedData;
 120              if ($referenceIsEqualFlag) return Pear::raiseError('Structures_Graph::addNode received an object that is a duplicate for this dataset', STRUCTURES_GRAPH_ERROR_GENERIC);
 121          }
 122          $this->_nodes[] =& $newNode;
 123          $newNode->setGraph($this);
 124      }
 125      /* }}} */
 126  
 127      /* removeNode (unimplemented) {{{ */
 128      /**
 129      *
 130      * Remove a Node from the Graph
 131      *
 132      * @todo     This is unimplemented
 133      * @param    Structures_Graph_Node   The node to be removed from the graph
 134      * @access    public
 135      */
 136      function removeNode(&$node) {
 137      }
 138      /* }}} */
 139  
 140      /* getNodes {{{ */
 141      /**
 142      *
 143      * Return the node set, in no particular order. For ordered node sets, use a Graph Manipulator insted.
 144      *
 145      * @access   public
 146      * @see      Structures_Graph_Manipulator_TopologicalSorter
 147      * @return   array The set of nodes in this graph
 148      */
 149      function &getNodes() {
 150          return $this->_nodes;
 151      }
 152      /* }}} */
 153  }
 154  ?>