File: /home/boxelikax/public_html/demoltec.com/Structures.tar
Graph/Node.php 0000644 00000025440 15240240513 0007204 0 ustar 00 <?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);
}
/* }}} */
}
?>
Graph/Manipulator/TopologicalSorter.php 0000644 00000015564 15240240513 0014273 0 ustar 00 <?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;
}
}
?>
Graph/Manipulator/AcyclicTest.php 0000644 00000013201 15240240513 0013011 0 ustar 00 <?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);
}
/* }}} */
}
/* }}} */
?>
Graph.php 0000644 00000014037 15240240513 0006317 0 ustar 00 <?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;
}
}
?>