| 1 |
lars |
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 |
require_once 'Structures/Graph.php';
|
|
|
28 |
require_once 'PHPUnit/Framework.php';
|
|
|
29 |
|
|
|
30 |
/**
|
|
|
31 |
* @access private
|
|
|
32 |
*/
|
|
|
33 |
class BasicGraph extends PHPUnit_Framework_TestCase
|
|
|
34 |
{
|
|
|
35 |
var $_graph = null;
|
|
|
36 |
|
|
|
37 |
function test_create_graph() {
|
|
|
38 |
$this->_graph = new Structures_Graph();
|
|
|
39 |
$this->assertTrue(is_a($this->_graph, 'Structures_Graph'));
|
|
|
40 |
}
|
|
|
41 |
|
|
|
42 |
function test_add_node() {
|
|
|
43 |
$this->_graph = new Structures_Graph();
|
|
|
44 |
$data = 1;
|
|
|
45 |
$node = new Structures_Graph_Node($data);
|
|
|
46 |
$this->_graph->addNode($node);
|
|
|
47 |
$node = new Structures_Graph_Node($data);
|
|
|
48 |
$this->_graph->addNode($node);
|
|
|
49 |
$node = new Structures_Graph_Node($data);
|
|
|
50 |
$this->_graph->addNode($node);
|
|
|
51 |
}
|
|
|
52 |
|
|
|
53 |
function test_connect_node() {
|
|
|
54 |
$this->_graph = new Structures_Graph();
|
|
|
55 |
$data = 1;
|
|
|
56 |
$node1 = new Structures_Graph_Node($data);
|
|
|
57 |
$node2 = new Structures_Graph_Node($data);
|
|
|
58 |
$this->_graph->addNode($node1);
|
|
|
59 |
$this->_graph->addNode($node2);
|
|
|
60 |
$node1->connectTo($node2);
|
|
|
61 |
|
|
|
62 |
$node =& $this->_graph->getNodes();
|
|
|
63 |
$node =& $node[0];
|
|
|
64 |
$node = $node->getNeighbours();
|
|
|
65 |
$node =& $node[0];
|
|
|
66 |
/*
|
|
|
67 |
ZE1 == and === operators fail on $node,$node2 because of the recursion introduced
|
|
|
68 |
by the _graph field in the Node object. So, we'll use the stupid method for reference
|
|
|
69 |
testing
|
|
|
70 |
*/
|
|
|
71 |
$node = true;
|
|
|
72 |
$this->assertTrue($node2);
|
|
|
73 |
$node = false;
|
|
|
74 |
$this->assertFalse($node2);
|
|
|
75 |
}
|
|
|
76 |
|
|
|
77 |
function test_data_references() {
|
|
|
78 |
$this->_graph = new Structures_Graph();
|
|
|
79 |
$data = 1;
|
|
|
80 |
$node = new Structures_Graph_Node();
|
|
|
81 |
$node->setData(&$data);
|
|
|
82 |
$this->_graph->addNode($node);
|
|
|
83 |
$data = 2;
|
|
|
84 |
$dataInNode =& $this->_graph->getNodes();
|
|
|
85 |
$dataInNode =& $dataInNode[0];
|
|
|
86 |
$dataInNode =& $dataInNode->getData();
|
|
|
87 |
$this->assertTrue($data === $dataInNode);
|
|
|
88 |
}
|
|
|
89 |
|
|
|
90 |
function test_metadata_references() {
|
|
|
91 |
$this->_graph = new Structures_Graph();
|
|
|
92 |
$data = 1;
|
|
|
93 |
$node = new Structures_Graph_Node();
|
|
|
94 |
$node->setMetadata('5', &$data);
|
|
|
95 |
$data = 2;
|
|
|
96 |
$dataInNode =& $node->getMetadata('5');
|
|
|
97 |
$this->assertTrue($data === $dataInNode);
|
|
|
98 |
}
|
|
|
99 |
|
|
|
100 |
function test_metadata_key_exists() {
|
|
|
101 |
$this->_graph = new Structures_Graph();
|
|
|
102 |
$data = 1;
|
|
|
103 |
$node = new Structures_Graph_Node();
|
|
|
104 |
$node->setMetadata('5', $data);
|
|
|
105 |
$this->assertTrue($node->metadataKeyExists('5'));
|
|
|
106 |
$this->assertFalse($node->metadataKeyExists('1'));
|
|
|
107 |
}
|
|
|
108 |
|
|
|
109 |
function test_directed_degree() {
|
|
|
110 |
$this->_graph = new Structures_Graph(true);
|
|
|
111 |
$node = array();
|
|
|
112 |
$node[] = new Structures_Graph_Node();
|
|
|
113 |
$node[] = new Structures_Graph_Node();
|
|
|
114 |
$node[] = new Structures_Graph_Node();
|
|
|
115 |
$this->_graph->addNode($node[0]);
|
|
|
116 |
$this->_graph->addNode($node[1]);
|
|
|
117 |
$this->_graph->addNode($node[2]);
|
|
|
118 |
$this->assertEquals(0, $node[0]->inDegree(), 'inDegree test failed for node 0 with 0 arcs');
|
|
|
119 |
$this->assertEquals(0, $node[1]->inDegree(), 'inDegree test failed for node 1 with 0 arcs');
|
|
|
120 |
$this->assertEquals(0, $node[2]->inDegree(), 'inDegree test failed for node 2 with 0 arcs');
|
|
|
121 |
$this->assertEquals(0, $node[0]->outDegree(), 'outDegree test failed for node 0 with 0 arcs');
|
|
|
122 |
$this->assertEquals(0, $node[1]->outDegree(), 'outDegree test failed for node 1 with 0 arcs');
|
|
|
123 |
$this->assertEquals(0, $node[2]->outDegree(), 'outDegree test failed for node 2 with 0 arcs');
|
|
|
124 |
$node[0]->connectTo($node[1]);
|
|
|
125 |
$this->assertEquals(0, $node[0]->inDegree(), 'inDegree test failed for node 0 with 1 arc');
|
|
|
126 |
$this->assertEquals(1, $node[1]->inDegree(), 'inDegree test failed for node 1 with 1 arc');
|
|
|
127 |
$this->assertEquals(0, $node[2]->inDegree(), 'inDegree test failed for node 2 with 1 arc');
|
|
|
128 |
$this->assertEquals(1, $node[0]->outDegree(), 'outDegree test failed for node 0 with 1 arc');
|
|
|
129 |
$this->assertEquals(0, $node[1]->outDegree(), 'outDegree test failed for node 1 with 1 arc');
|
|
|
130 |
$this->assertEquals(0, $node[2]->outDegree(), 'outDegree test failed for node 2 with 1 arc');
|
|
|
131 |
$node[0]->connectTo($node[2]);
|
|
|
132 |
$this->assertEquals(0, $node[0]->inDegree(), 'inDegree test failed for node 0 with 2 arcs');
|
|
|
133 |
$this->assertEquals(1, $node[1]->inDegree(), 'inDegree test failed for node 1 with 2 arcs');
|
|
|
134 |
$this->assertEquals(1, $node[2]->inDegree(), 'inDegree test failed for node 2 with 2 arcs');
|
|
|
135 |
$this->assertEquals(2, $node[0]->outDegree(), 'outDegree test failed for node 0 with 2 arcs');
|
|
|
136 |
$this->assertEquals(0, $node[1]->outDegree(), 'outDegree test failed for node 1 with 2 arcs');
|
|
|
137 |
$this->assertEquals(0, $node[2]->outDegree(), 'outDegree test failed for node 2 with 2 arcs');
|
|
|
138 |
}
|
|
|
139 |
|
|
|
140 |
function test_undirected_degree() {
|
|
|
141 |
$this->_graph = new Structures_Graph(false);
|
|
|
142 |
$node = array();
|
|
|
143 |
$node[] = new Structures_Graph_Node();
|
|
|
144 |
$node[] = new Structures_Graph_Node();
|
|
|
145 |
$node[] = new Structures_Graph_Node();
|
|
|
146 |
$this->_graph->addNode($node[0]);
|
|
|
147 |
$this->_graph->addNode($node[1]);
|
|
|
148 |
$this->_graph->addNode($node[2]);
|
|
|
149 |
$this->assertEquals(0, $node[0]->inDegree(), 'inDegree test failed for node 0 with 0 arcs');
|
|
|
150 |
$this->assertEquals(0, $node[1]->inDegree(), 'inDegree test failed for node 1 with 0 arcs');
|
|
|
151 |
$this->assertEquals(0, $node[2]->inDegree(), 'inDegree test failed for node 2 with 0 arcs');
|
|
|
152 |
$this->assertEquals(0, $node[0]->outDegree(), 'outDegree test failed for node 0 with 0 arcs');
|
|
|
153 |
$this->assertEquals(0, $node[1]->outDegree(), 'outDegree test failed for node 1 with 0 arcs');
|
|
|
154 |
$this->assertEquals(0, $node[2]->outDegree(), 'outDegree test failed for node 2 with 0 arcs');
|
|
|
155 |
$node[0]->connectTo($node[1]);
|
|
|
156 |
$this->assertEquals(1, $node[0]->inDegree(), 'inDegree test failed for node 0 with 1 arc');
|
|
|
157 |
$this->assertEquals(1, $node[1]->inDegree(), 'inDegree test failed for node 1 with 1 arc');
|
|
|
158 |
$this->assertEquals(0, $node[2]->inDegree(), 'inDegree test failed for node 2 with 1 arc');
|
|
|
159 |
$this->assertEquals(1, $node[0]->outDegree(), 'outDegree test failed for node 0 with 1 arc');
|
|
|
160 |
$this->assertEquals(1, $node[1]->outDegree(), 'outDegree test failed for node 1 with 1 arc');
|
|
|
161 |
$this->assertEquals(0, $node[2]->outDegree(), 'outDegree test failed for node 2 with 1 arc');
|
|
|
162 |
$node[0]->connectTo($node[2]);
|
|
|
163 |
$this->assertEquals(2, $node[0]->inDegree(), 'inDegree test failed for node 0 with 2 arcs');
|
|
|
164 |
$this->assertEquals(1, $node[1]->inDegree(), 'inDegree test failed for node 1 with 2 arcs');
|
|
|
165 |
$this->assertEquals(1, $node[2]->inDegree(), 'inDegree test failed for node 2 with 2 arcs');
|
|
|
166 |
$this->assertEquals(2, $node[0]->outDegree(), 'outDegree test failed for node 0 with 2 arcs');
|
|
|
167 |
$this->assertEquals(1, $node[1]->outDegree(), 'outDegree test failed for node 1 with 2 arcs');
|
|
|
168 |
$this->assertEquals(1, $node[2]->outDegree(), 'outDegree test failed for node 2 with 2 arcs');
|
|
|
169 |
}
|
|
|
170 |
}
|
|
|
171 |
?>
|