crm.fsf.org/20131203/files/sites/all/modules-new/civicrm/packages/Structures/Graph.php

   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 ?>