aronnovak/graph_creating/sna_test.php

<?php
// $Id$
/**
 *  Unit tests collection using simpletest
 * 
 * @author Aron Novak <aaron@szentimre.hu>
 * @version 0.1
 * @package sna
 */

require_once 'simpletest/unit_tester.php';
require_once 'simpletest/reporter.php';
require_once 'routes.php';
require_once 'includes/bootstrap.inc';

drupal_bootstrap(DRUPAL_BOOTSTRAP_DATABASE);

/**
 * Store the graphs for testing
 *
 */
class SampleGraph {
  
  private $graphs, $which;
  
  function __construct($index) {
    $this->which = $index;
    $this->graphs = array(
              'empty_graph' => array(),    // Empty graph
              'sample1' => array(
                    9 => array(
                               15 => 4,
                               3 => 2,
                              ),
                    4 => array(
                               3 => 1,
                               5 => 4,
                               69 => 25,
                               11 => 6,
                              ),
              ),
              'book_sample' => array(   // Test graph from Algorithms book
                    1 => array(
                               2 => 10,
                               3 => 5,
                              ),
                    2 => array(
                               3 => 2,
                               4 => 1,
                              ),
                    3 => array(
                               2 => 3,
                               4 => 9,
                               5 => 2,
                              ),
                    4 => array(
                               5 => 4,
                              ),
                    5 => array(
                               4 => 6,
                               1 => 7,
                              ),
              ),
              'sample2' => array(
                    9 => array(
                                6 => 3,
                              ),
                    6 => array(
                                9 => 5,
                              ),
              ),
              'two_groups' => array (
                    5 => array (
                                4 => 5.5,
                               ),
                    1 => array (
                                4 => 10,
                                5 => 1,
                               ),
                    2 => array (
                                1 => 10,
                                9 => 10,
                               ),
                    9 => array (
                                2 => 10,
                               ),
                    4 => array (
                                1 => 10,
                               ),
              ),
              'one_edged' => array (
                    2 => array (
                                1 => 1,
                               ),
              ),
    );              
  }
  
  /**
   * Get the graph for further operation
   *
   * @param array $edges The adjacentcy list of the graph
   */
  function getArray() {
    return $this->graphs[$this->which];
  }
  
  /**
   * Get the graph for print to the user
   *
   * @return string The textual representation of the adjacentcy list
   */
  function toPrintable() {
    ob_start();
    print_r($this->graphs[$this->which]);
    return ob_get_clean();
  }
}

class BasicSNATest extends UnitTestCase {
  
  function __construct() {
    clear_cache();
  }
  
  function BasicSNATest($name = false) {
    $this->UnitTestCase($name);
  }
}

class DegreeCountTester extends BasicSNATest {
    
  function testCreation() {
    $sampleGraph = new SampleGraph('sample1');
    $deg1 = vertex_degree($sampleGraph->getArray(), 9);
    $deg2 = vertex_degree($sampleGraph->getArray(), 4);
    $deg3 = vertex_degree($sampleGraph->getArray(), 256);
    $this->assertEqual($deg1, 2);
    $this->assertEqual($deg2, 4);
    $this->assertEqual($deg3, 0);
    }
}

class AToAnyTester extends BasicSNATest {
  
  function testCreation() {
    $sampleGraph = new SampleGraph('empty_graph');
    $min_tree = a_to_any($sampleGraph->getArray(), 1);
    $this->assertEqual(count($min_tree['dist']), 1);
    $this->assertEqual($min_tree['dist'][1], 0);
    clear_cache();
    $sampleGraph = new SampleGraph('book_sample');
    $min_tree = a_to_any($sampleGraph->getArray(), 1);
    $this->assertEqual($min_tree['dist'][4], 9);
    $this->assertEqual($min_tree['dist'][5], 7);
    $this->assertEqual($min_tree['dist'][1], 0);
    $this->assertEqual($min_tree['prev'][1], '-');
    $this->assertEqual($min_tree['prev'][5], 3);
    $this->assertEqual($min_tree['prev'][4], 2);
    clear_cache();
    $sampleGraph = new SampleGraph('sample2');
    $min_tree = a_to_any($sampleGraph->getArray(), 9);
    $this->assertEqual($min_tree['dist'][6], 3);
  }
}

class CostTester extends BasicSNATest {
  function testCreation() {
    $sampleGraph = new SampleGraph('book_sample');
    $min_max = get_min_and_max_degree($sampleGraph->getArray());
    $weight1 = get_edge_weight($sampleGraph->getArray(), 1, 2, $min_max[0], $min_max[1]);
    $weight2 = get_edge_weight($sampleGraph->getArray(), 4, 1, $min_max[0], $min_max[1]);
    $weight3 = get_edge_weight($sampleGraph->getArray(), 2, 4, $min_max[0], $min_max[1]);
    $weight4 = get_edge_weight($sampleGraph->getArray(), 4, 5, $min_max[0], $min_max[1]);
    $this->assertEqual($weight1, 1);
    $this->assertIdentical($weight2, FALSE);
    $this->assertEqual($weight3, 10);
    $this->assertEqual($weight4, 7); 
  }
}

class AToBTester extends BasicSNATest {
  function testCreation() {
    $sampleGraph = new SampleGraph('book_sample');
    $route1 = a_to_b($sampleGraph->getArray(), 1, 4);
    $route2 = a_to_b($sampleGraph->getArray(), 3, 5);
    $this->assertEqual(count($route1), 4);
    $this->assertEqual($route1[0]['d'], 9);
    $this->assertEqual($route1[0]['n'], 4);
    $this->assertEqual($route1[1]['d'], 8);
    $this->assertEqual($route1[1]['n'], 2);
    
    $this->assertEqual(count($route2), 2);
    $this->assertEqual($route2[1]['n'], 3);
    $this->assertEqual($route2[1]['d'], 0);
    $this->assertEqual($route2[0]['n'], 5);
    $this->assertEqual($route2[0]['d'], 2);
    $sampleGraph = new SampleGraph('one_edged');
    $is_route = a_to_b($sampleGraph->getArray(), 2, 1);
    $this->assertEqual($is_route[0]['n'], 1);
    $this->assertEqual($is_route[0]['d'], 1);
    $sampleGraph = new SampleGraph('empty_graph');
    $no_route = a_to_b($sampleGraph->getArray(), 5, 3);
    $this->assertEqual($no_route, FALSE);
    $sampleGraph = new SampleGraph('sample2');
    $no_route2 = a_to_b($sampleGraph->getArray(), 99, 9);
    $this->assertEqual($no_route2, FALSE);
    
  }
}

class NStepDistanceTester extends BasicSNATest {
  function testCreating() {
    $sampleGraph = new SampleGraph('book_sample');
    $dist1 = n_step_distance($sampleGraph->getArray(), 5, 1);
    $dist2 = n_step_distance($sampleGraph->getArray(), 5, 2);
    $dist3 = n_step_distance($sampleGraph->getArray(), 1, 4);
    $dist4 = n_step_distance($sampleGraph->getArray(), 1, 10);
    $dist5 = n_step_distance($sampleGraph->getArray(), 3, 4);
    $sampleGraph = new SampleGraph('one_edged');
    $dist6 = n_step_distance($sampleGraph->getArray(), 2, 1);
    $this->assertEqual($dist1, 1);
    $this->assertEqual($dist2, 2); 
    $this->assertEqual($dist3, 2);
    $this->assertEqual($dist4, FALSE);
    $this->assertEqual($dist5, 1);
    $this->assertEqual($dist6, 1);
  }
}

class AverageSeparationTester extends BasicSNATest {
  function testCreating() {
    $sampleGraph = new SampleGraph('book_sample');
    $step1 = average_step_separation($sampleGraph->getArray());
    $sampleGraph = new SampleGraph('sample2');
    $step2 = average_step_separation($sampleGraph->getArray());
    $this->assertEqual($step1, 1.65);
    $this->assertEqual($step2, 1);
  }
}

class ClusteringCoefficientTester extends BasicSNATest {
  function testCreating() {
    $sampleGraph = new SampleGraph('book_sample');
    $cc1 = clustering_coefficient($sampleGraph->getArray(), 1);
    $cc2 = clustering_coefficient($sampleGraph->getArray(), 2);
    $cc3 = clustering_coefficient($sampleGraph->getArray(), 3);
    $cc4 = clustering_coefficient($sampleGraph->getArray(), 4);
    $cc5 = clustering_coefficient($sampleGraph->getArray(), 5);
    $cc6 = clustering_coefficient($sampleGraph->getArray(), 88);
    $sampleGraph = new SampleGraph('sample2');
    $cc7 = clustering_coefficient($sampleGraph->getArray(), 6);
    $this->assertEqual($cc1, 1);
    $this->assertEqual($cc2, 0.5);
    $this->assertEqual($cc3, 3 / 6);
    $this->assertEqual($cc4, FALSE);
    $this->assertEqual($cc5, 0);
    $this->assertEqual($cc6, FALSE);
    $this->assertEqual($cc7, FALSE);
  }
}

class SearchGroupsTester extends BasicSNATest {
  function testCreating() {
    $sampleGraph = new SampleGraph('empty_graph');
    $empty_graph = search_groups($sampleGraph->getArray());
    $this->assertIdentical($empty_graph, array());
    $sampleGraph = new SampleGraph('sample1');
    $sample1 = search_groups($sampleGraph->getArray());
    $sample1_res = array (
                            0 => array (
                              0 => 9,
                            ),
                            1 => array (
                              0 => 4,
                            ),
                            2 => array (
                              0 => 15,
                            ),
                            3 => array (
                              0 => 3,
                            ),
                            4 => array (
                              0 => 5,
                            ),
                            5 => array (
                              0 => 69,
                            ),
                            6 => array (
                              0 => 11,
                            ),
    );
    $this->assertIdentical($sample1, $sample1_res);
    $sampleGraph = new SampleGraph('two_groups');
    $two_groups =  search_groups($sampleGraph->getArray());
    $two_groups_res = array (
                            0 => array (
                              0 => 5,
                              1 => 1,
                              2 => 4,
                            ),
                            1 => array (
                              0 => 2,
                              1 => 9,
                            ),
    );
    $this->assertIdentical($two_groups, $two_groups_res);
  }
}

$tests = array(
                new DegreeCountTester(),
                new AToAnyTester(),
                new CostTester(),
                new AToBTester(),
                new NStepDistanceTester(),
                new AverageSeparationTester(),
                new ClusteringCoefficientTester(),
                new SearchGroupsTester(),
              );

$how_many_tests = count($tests);
for ($i = 0; $i < $how_many_tests; $i++) {
  $tests[$i]->run(new TextReporter());
}

?>
1	<?php
2	// $Id$
3	/**
4	* Unit tests collection using simpletest
5	*
6	* @author Aron Novak <aaron@szentimre.hu>
7	* @version 0.1
8	* @package sna
9	*/
10
11	require_once 'simpletest/unit_tester.php';
12	require_once 'simpletest/reporter.php';
13	require_once 'routes.php';
14	require_once 'includes/bootstrap.inc';
15
16	drupal_bootstrap(DRUPAL_BOOTSTRAP_DATABASE);
17
18	/**
19	* Store the graphs for testing
20	*
21	*/
22	class SampleGraph {
23
24	private $graphs, $which;
25
26	function __construct($index) {
27	$this->which = $index;
28	$this->graphs = array(
29	'empty_graph' => array(), // Empty graph
30	'sample1' => array(
31	9 => array(
32	15 => 4,
33	3 => 2,
34	),
35	4 => array(
36	3 => 1,
37	5 => 4,
38	69 => 25,
39	11 => 6,
40	),
41	),
42	'book_sample' => array( // Test graph from Algorithms book
43	1 => array(
44	2 => 10,
45	3 => 5,
46	),
47	2 => array(
48	3 => 2,
49	4 => 1,
50	),
51	3 => array(
52	2 => 3,
53	4 => 9,
54	5 => 2,
55	),
56	4 => array(
57	5 => 4,
58	),
59	5 => array(
60	4 => 6,
61	1 => 7,
62	),
63	),
64	'sample2' => array(
65	9 => array(
66	6 => 3,
67	),
68	6 => array(
69	9 => 5,
70	),
71	),
72	'two_groups' => array (
73	5 => array (
74	4 => 5.5,
75	),
76	1 => array (
77	4 => 10,
78	5 => 1,
79	),
80	2 => array (
81	1 => 10,
82	9 => 10,
83	),
84	9 => array (
85	2 => 10,
86	),
87	4 => array (
88	1 => 10,
89	),
90	),
91	'one_edged' => array (
92	2 => array (
93	1 => 1,
94	),
95	),
96	);
97	}
98
99	/**
100	* Get the graph for further operation
101	*
102	* @param array $edges The adjacentcy list of the graph
103	*/
104	function getArray() {
105	return $this->graphs[$this->which];
106	}
107
108	/**
109	* Get the graph for print to the user
110	*
111	* @return string The textual representation of the adjacentcy list
112	*/
113	function toPrintable() {
114	ob_start();
115	print_r($this->graphs[$this->which]);
116	return ob_get_clean();
117	}
118	}
119
120	class BasicSNATest extends UnitTestCase {
121
122	function __construct() {
123	clear_cache();
124	}
125
126	function BasicSNATest($name = false) {
127	$this->UnitTestCase($name);
128	}
129	}
130
131	class DegreeCountTester extends BasicSNATest {
132
133	function testCreation() {
134	$sampleGraph = new SampleGraph('sample1');
135	$deg1 = vertex_degree($sampleGraph->getArray(), 9);
136	$deg2 = vertex_degree($sampleGraph->getArray(), 4);
137	$deg3 = vertex_degree($sampleGraph->getArray(), 256);
138	$this->assertEqual($deg1, 2);
139	$this->assertEqual($deg2, 4);
140	$this->assertEqual($deg3, 0);
141	}
142	}
143
144	class AToAnyTester extends BasicSNATest {
145
146	function testCreation() {
147	$sampleGraph = new SampleGraph('empty_graph');
148	$min_tree = a_to_any($sampleGraph->getArray(), 1);
149	$this->assertEqual(count($min_tree['dist']), 1);
150	$this->assertEqual($min_tree['dist'][1], 0);
151	clear_cache();
152	$sampleGraph = new SampleGraph('book_sample');
153	$min_tree = a_to_any($sampleGraph->getArray(), 1);
154	$this->assertEqual($min_tree['dist'][4], 9);
155	$this->assertEqual($min_tree['dist'][5], 7);
156	$this->assertEqual($min_tree['dist'][1], 0);
157	$this->assertEqual($min_tree['prev'][1], '-');
158	$this->assertEqual($min_tree['prev'][5], 3);
159	$this->assertEqual($min_tree['prev'][4], 2);
160	clear_cache();
161	$sampleGraph = new SampleGraph('sample2');
162	$min_tree = a_to_any($sampleGraph->getArray(), 9);
163	$this->assertEqual($min_tree['dist'][6], 3);
164	}
165	}
166
167	class CostTester extends BasicSNATest {
168	function testCreation() {
169	$sampleGraph = new SampleGraph('book_sample');
170	$min_max = get_min_and_max_degree($sampleGraph->getArray());
171	$weight1 = get_edge_weight($sampleGraph->getArray(), 1, 2, $min_max[0], $min_max[1]);
172	$weight2 = get_edge_weight($sampleGraph->getArray(), 4, 1, $min_max[0], $min_max[1]);
173	$weight3 = get_edge_weight($sampleGraph->getArray(), 2, 4, $min_max[0], $min_max[1]);
174	$weight4 = get_edge_weight($sampleGraph->getArray(), 4, 5, $min_max[0], $min_max[1]);
175	$this->assertEqual($weight1, 1);
176	$this->assertIdentical($weight2, FALSE);
177	$this->assertEqual($weight3, 10);
178	$this->assertEqual($weight4, 7);
179	}
180	}
181
182	class AToBTester extends BasicSNATest {
183	function testCreation() {
184	$sampleGraph = new SampleGraph('book_sample');
185	$route1 = a_to_b($sampleGraph->getArray(), 1, 4);
186	$route2 = a_to_b($sampleGraph->getArray(), 3, 5);
187	$this->assertEqual(count($route1), 4);
188	$this->assertEqual($route1[0]['d'], 9);
189	$this->assertEqual($route1[0]['n'], 4);
190	$this->assertEqual($route1[1]['d'], 8);
191	$this->assertEqual($route1[1]['n'], 2);
192
193	$this->assertEqual(count($route2), 2);
194	$this->assertEqual($route2[1]['n'], 3);
195	$this->assertEqual($route2[1]['d'], 0);
196	$this->assertEqual($route2[0]['n'], 5);
197	$this->assertEqual($route2[0]['d'], 2);
198	$sampleGraph = new SampleGraph('one_edged');
199	$is_route = a_to_b($sampleGraph->getArray(), 2, 1);
200	$this->assertEqual($is_route[0]['n'], 1);
201	$this->assertEqual($is_route[0]['d'], 1);
202	$sampleGraph = new SampleGraph('empty_graph');
203	$no_route = a_to_b($sampleGraph->getArray(), 5, 3);
204	$this->assertEqual($no_route, FALSE);
205	$sampleGraph = new SampleGraph('sample2');
206	$no_route2 = a_to_b($sampleGraph->getArray(), 99, 9);
207	$this->assertEqual($no_route2, FALSE);
208
209	}
210	}
211
212	class NStepDistanceTester extends BasicSNATest {
213	function testCreating() {
214	$sampleGraph = new SampleGraph('book_sample');
215	$dist1 = n_step_distance($sampleGraph->getArray(), 5, 1);
216	$dist2 = n_step_distance($sampleGraph->getArray(), 5, 2);
217	$dist3 = n_step_distance($sampleGraph->getArray(), 1, 4);
218	$dist4 = n_step_distance($sampleGraph->getArray(), 1, 10);
219	$dist5 = n_step_distance($sampleGraph->getArray(), 3, 4);
220	$sampleGraph = new SampleGraph('one_edged');
221	$dist6 = n_step_distance($sampleGraph->getArray(), 2, 1);
222	$this->assertEqual($dist1, 1);
223	$this->assertEqual($dist2, 2);
224	$this->assertEqual($dist3, 2);
225	$this->assertEqual($dist4, FALSE);
226	$this->assertEqual($dist5, 1);
227	$this->assertEqual($dist6, 1);
228	}
229	}
230
231	class AverageSeparationTester extends BasicSNATest {
232	function testCreating() {
233	$sampleGraph = new SampleGraph('book_sample');
234	$step1 = average_step_separation($sampleGraph->getArray());
235	$sampleGraph = new SampleGraph('sample2');
236	$step2 = average_step_separation($sampleGraph->getArray());
237	$this->assertEqual($step1, 1.65);
238	$this->assertEqual($step2, 1);
239	}
240	}
241
242	class ClusteringCoefficientTester extends BasicSNATest {
243	function testCreating() {
244	$sampleGraph = new SampleGraph('book_sample');
245	$cc1 = clustering_coefficient($sampleGraph->getArray(), 1);
246	$cc2 = clustering_coefficient($sampleGraph->getArray(), 2);
247	$cc3 = clustering_coefficient($sampleGraph->getArray(), 3);
248	$cc4 = clustering_coefficient($sampleGraph->getArray(), 4);
249	$cc5 = clustering_coefficient($sampleGraph->getArray(), 5);
250	$cc6 = clustering_coefficient($sampleGraph->getArray(), 88);
251	$sampleGraph = new SampleGraph('sample2');
252	$cc7 = clustering_coefficient($sampleGraph->getArray(), 6);
253	$this->assertEqual($cc1, 1);
254	$this->assertEqual($cc2, 0.5);
255	$this->assertEqual($cc3, 3 / 6);
256	$this->assertEqual($cc4, FALSE);
257	$this->assertEqual($cc5, 0);
258	$this->assertEqual($cc6, FALSE);
259	$this->assertEqual($cc7, FALSE);
260	}
261	}
262
263	class SearchGroupsTester extends BasicSNATest {
264	function testCreating() {
265	$sampleGraph = new SampleGraph('empty_graph');
266	$empty_graph = search_groups($sampleGraph->getArray());
267	$this->assertIdentical($empty_graph, array());
268	$sampleGraph = new SampleGraph('sample1');
269	$sample1 = search_groups($sampleGraph->getArray());
270	$sample1_res = array (
271	0 => array (
272	0 => 9,
273	),
274	1 => array (
275	0 => 4,
276	),
277	2 => array (
278	0 => 15,
279	),
280	3 => array (
281	0 => 3,
282	),
283	4 => array (
284	0 => 5,
285	),
286	5 => array (
287	0 => 69,
288	),
289	6 => array (
290	0 => 11,
291	),
292	);
293	$this->assertIdentical($sample1, $sample1_res);
294	$sampleGraph = new SampleGraph('two_groups');
295	$two_groups = search_groups($sampleGraph->getArray());
296	$two_groups_res = array (
297	0 => array (
298	0 => 5,
299	1 => 1,
300	2 => 4,
301	),
302	1 => array (
303	0 => 2,
304	1 => 9,
305	),
306	);
307	$this->assertIdentical($two_groups, $two_groups_res);
308	}
309	}
310
311	$tests = array(
312	new DegreeCountTester(),
313	new AToAnyTester(),
314	new CostTester(),
315	new AToBTester(),
316	new NStepDistanceTester(),
317	new AverageSeparationTester(),
318	new ClusteringCoefficientTester(),
319	new SearchGroupsTester(),
320	);
321
322	$how_many_tests = count($tests);
323	for ($i = 0; $i < $how_many_tests; $i++) {
324	$tests[$i]->run(new TextReporter());
325	}
326
327	?>