PEAR/Structures does not currently work with E_STRICT so we need to manually convert

This is only being stored here as it will then be used correctly when installed
Unmodified at all as yet ...

4 files changed, 785 insertions, 0 deletions

diff --git a/pear/Structures/Graph.php b/pear/Structures/Graph.php
new file mode 100644
index 0000000..3757f15
--- /dev/null
+++ b/pear/Structures/Graph.php
@@ -0,0 +1,154 @@
+<?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>                  |
+// +-----------------------------------------------------------------------------+
+//
+/**
+ * The Graph.php file contains the definition of the Structures_Graph class 
+ *
+ * @see Structures_Graph
+ * @package Structures_Graph
+ */
+
+/* dependencies {{{ */
+/** PEAR base classes */
+require_once 'PEAR.php';
+/** Graph Node */
+require_once 'Structures/Graph/Node.php';
+/* }}} */
+
+define('STRUCTURES_GRAPH_ERROR_GENERIC', 100);
+
+/* class Structures_Graph {{{ */
+/**
+ * The Structures_Graph class represents a graph data structure. 
+ *
+ * A Graph is a data structure composed by a set of nodes, connected by arcs.
+ * Graphs may either be directed or undirected. In a directed graph, arcs are 
+ * directional, and can be traveled only one way. In an undirected graph, arcs
+ * are bidirectional, and can be traveled both ways.
+ *
+ * @author		Sérgio Carvalho <sergio.carvalho@portugalmail.com> 
+ * @copyright	(c) 2004 by Sérgio Carvalho
+ * @package Structures_Graph
+ */
+/* }}} */
+class Structures_Graph {
+    /* fields {{{ */
+    /**
+     * @access private
+     */
+    var $_nodes = array();
+    /**
+     * @access private
+     */
+    var $_directed = false;
+    /* }}} */
+
+    /* Constructor {{{ */
+    /**
+    *
+    * Constructor
+    *
+    * @param    boolean    Set to true if the graph is directed. Set to false if it is not directed. (Optional, defaults to true)
+    * @access	public
+    */
+    function Structures_Graph($directed = true) {
+        $this->_directed = $directed;
+    }
+    /* }}} */
+
+    /* isDirected {{{ */
+    /**
+    *
+    * Return true if a graph is directed
+    *
+    * @return	boolean	 true if the graph is directed
+    * @access	public
+    */
+    function isDirected() {
+        return (boolean) $this->_directed;
+    }
+    /* }}} */
+
+    /* addNode {{{ */
+    /**
+    *
+    * Add a Node to the Graph
+    *
+    * @param    Structures_Graph_Node   The node to be added.
+    * @access	public
+    */
+    function addNode(&$newNode) {
+        // We only add nodes
+        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);
+        // Graphs are node *sets*, so duplicates are forbidden. We allow nodes that are exactly equal, but disallow equal references.
+        foreach($this->_nodes as $key => $node) {
+            /*
+             ZE1 equality operators choke on the recursive cycle introduced by the _graph field in the Node object.
+             So, we'll check references the hard way (change $this->_nodes[$key] and check if the change reflects in 
+             $node)
+            */
+            $savedData = $this->_nodes[$key];
+            $referenceIsEqualFlag = false;
+            $this->_nodes[$key] = true;
+            if ($node === true) {
+                $this->_nodes[$key] = false;
+                if ($node === false) $referenceIsEqualFlag = true;
+            }
+            $this->_nodes[$key] = $savedData;
+            if ($referenceIsEqualFlag) return Pear::raiseError('Structures_Graph::addNode received an object that is a duplicate for this dataset', STRUCTURES_GRAPH_ERROR_GENERIC);
+        }
+        $this->_nodes[] =& $newNode;
+        $newNode->setGraph($this);
+    }
+    /* }}} */
+
+    /* removeNode (unimplemented) {{{ */
+    /**
+    *
+    * Remove a Node from the Graph
+    *
+    * @todo     This is unimplemented
+    * @param    Structures_Graph_Node   The node to be removed from the graph
+    * @access	public
+    */
+    function removeNode(&$node) {
+    }
+    /* }}} */
+
+    /* getNodes {{{ */
+    /**
+    *
+    * Return the node set, in no particular order. For ordered node sets, use a Graph Manipulator insted.
+    *
+    * @access   public
+    * @see      Structures_Graph_Manipulator_TopologicalSorter
+    * @return   array The set of nodes in this graph
+    */
+    function &getNodes() {
+        return $this->_nodes;
+    }
+    /* }}} */
+}
+?>
diff --git a/pear/Structures/Graph/Manipulator/AcyclicTest.php b/pear/Structures/Graph/Manipulator/AcyclicTest.php
new file mode 100644
index 0000000..fc1ba92
--- /dev/null
+++ b/pear/Structures/Graph/Manipulator/AcyclicTest.php
@@ -0,0 +1,136 @@
+<?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_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		Sérgio Carvalho <sergio.carvalho@portugalmail.com> 
+ * @copyright	(c) 2004 by Sérgio 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.
+    *
+    * @access   private
+    * @return	integer	 Number of non-visited nodes that link to this one
+    */
+    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 {{{ */
+    /**
+    * @access   private
+    */
+    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
+    * @access	public
+    */
+    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);
+    }
+    /* }}} */
+}
+/* }}} */
+?>
diff --git a/pear/Structures/Graph/Manipulator/TopologicalSorter.php b/pear/Structures/Graph/Manipulator/TopologicalSorter.php
new file mode 100644
index 0000000..98a9fa0
--- /dev/null
+++ b/pear/Structures/Graph/Manipulator/TopologicalSorter.php
@@ -0,0 +1,153 @@
+<?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_Manipulator_TopologicalSorter class.
+ * 
+ * @see Structures_Graph_Manipulator_TopologicalSorter
+ * @package Structures_Graph
+ */
+
+/* dependencies {{{ */
+/** */
+require_once 'PEAR.php';
+/** */
+require_once 'Structures/Graph.php';
+/** */
+require_once 'Structures/Graph/Node.php';
+/** */
+require_once 'Structures/Graph/Manipulator/AcyclicTest.php';
+/* }}} */
+
+/* class Structures_Graph_Manipulator_TopologicalSorter {{{ */
+/**
+ * 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		Sérgio Carvalho <sergio.carvalho@portugalmail.com> 
+ * @copyright	(c) 2004 by Sérgio Carvalho
+ * @see     Structures_Graph_Manipulator_AcyclicTest
+ * @package Structures_Graph
+ */
+class Structures_Graph_Manipulator_TopologicalSorter {
+    /* _nonVisitedInDegree {{{ */
+    /**
+    *
+    * This is a variant of Structures_Graph::inDegree which does 
+    * not count nodes marked as visited.
+    *
+    * @access   private
+    * @return	integer	 Number of non-visited nodes that link to this one
+    */
+    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 {{{ */
+    /**
+    * @access   private
+    */
+    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')) && Structures_Graph_Manipulator_TopologicalSorter::_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 {{{ */
+    /**
+    *
+    * 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.
+    *
+    * @return	array	 The graph's nodes, sorted by topological order.
+    * @access	public
+    */
+    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;
+    }
+    /* }}} */
+}
+/* }}} */
+?>
diff --git a/pear/Structures/Graph/Node.php b/pear/Structures/Graph/Node.php
new file mode 100644
index 0000000..95afa2b
--- /dev/null
+++ b/pear/Structures/Graph/Node.php
@@ -0,0 +1,342 @@
+<?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 Structures_Graph_Node() {
+    }
+    /* }}} */
+
+    /* 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);
+    }
+    /* }}} */
+}
+?>