芝麻web文件管理V1.00

编辑当前文件:/home/mgatv524/public_html/avenida/views/Structures.zip

PK�������JqYUyv�����	��Graph.phpnu��[�����������<?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 
 *
 * @package Structures_Graph
 */

/* dependencies {{{ */
require_once 'PEAR.php';
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
{
    /**
     * List of node objects in this graph
     * @access private
     */
    var $_nodes = array();

/**
     * If the graph is directed or not
     * @access private
     */
    var $_directed = false;

/**
     * Constructor
     *
     * @param boolean $directed Set to true if the graph is directed.
     *                          Set to false if it is not directed.
     */
    public function __construct($directed = true)
    {
        $this->_directed = $directed;
    }

/**
     * Old constructor (PHP4-style; kept for BC with extending classes)
     *
     * @param boolean $directed Set to true if the graph is directed.
     *                          Set to false if it is not directed.
     *
     * @return void
     */
    public function Structures_Graph($directed = true)
    {
        $this->__construct($directed);
    }

/**
     * Return true if a graph is directed
     *
     * @return boolean true if the graph is directed
     */
    public function isDirected()
    {
        return (boolean) $this->_directed;
    }

/**
     * Add a Node to the Graph
     *
     * @param Structures_Graph_Node $newNode The node to be added.
     *
     * @return void
     */
    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);
    }

/**
     * Remove a Node from the Graph
     *
     * @param Structures_Graph_Node $node The node to be removed from the graph
     *
     * @return void
     * @todo   This is unimplemented
     */
    public function removeNode(&$node)
    {
    }

/**
     * Return the node set, in no particular order.
     * For ordered node sets, use a Graph Manipulator insted.
     *
     * @return array The set of nodes in this graph
     * @see    Structures_Graph_Manipulator_TopologicalSorter
     */
    public function &getNodes()
    {
        return $this->_nodes;
    }
}
?>
PK�������JqY9��������!��Graph/Manipulator/AcyclicTest.phpnu��[�����������<?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.
    *
    * @return	integer	 Number of non-visited nodes that link to this one
    */
    protected static 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 {{{ */
    /**
     * Check if the graph is acyclic
     */
    protected static 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
    */
    public static 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);
    }
    /* }}} */
}
/* }}} */
?>
PK�������JqY~(�ht��t��'��Graph/Manipulator/TopologicalSorter.phpnu��[�����������<?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.
 * 
 * @package Structures_Graph
 */

require_once 'PEAR.php';
require_once 'Structures/Graph.php';
require_once 'Structures/Graph/Node.php';
require_once 'Structures/Graph/Manipulator/AcyclicTest.php';

/**
 * 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
{
    /**
     * This is a variant of Structures_Graph::inDegree which does 
     * not count nodes marked as visited.
     *
     * @param object $node Node to check
     *
     * @return integer Number of non-visited nodes that link to this one
     */
    protected static 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 implementation
     *
     * @param object $graph Graph to sort
     *
     * @return void
     */
    protected static 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'))
                    && static::_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 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.
     *
     * @param object $graph Graph to sort
     *
     * @return array The graph's nodes, sorted by topological order.
     */
    public static 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;
    }
}
?>
PK�������JqY�C� +�� +����Graph/Node.phpnu��[�����������<?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);
    }
    /* }}} */
}
?>
PK���������JqYUyv�����	����������������Graph.phpnu��[�����������PK���������JqY9��������!������������X��Graph/Manipulator/AcyclicTest.phpnu��[�����������PK���������JqY~(�ht��t��'������������*/��Graph/Manipulator/TopologicalSorter.phpnu��[�����������PK���������JqY�C� +�� +���������������J��Graph/Node.phpnu��[�����������PK������_��Sv����