| 1 |
<?php
|
| 2 |
// $Id$
|
| 3 |
/**
|
| 4 |
* Finding minimal routes, BFS and DFS searches, collecting groups from the graph
|
| 5 |
*
|
| 6 |
* @author Aron Novak <aaron@szentimre.hu>
|
| 7 |
* @version 0.1
|
| 8 |
* @package sna
|
| 9 |
*/
|
| 10 |
|
| 11 |
/**
|
| 12 |
* Get sql access and important functions
|
| 13 |
*/
|
| 14 |
require_once 'common.php';
|
| 15 |
|
| 16 |
/**
|
| 17 |
* Track back the route
|
| 18 |
*
|
| 19 |
* @param array $result The minimal tree of routes
|
| 20 |
* @param integer $to The vertex's id
|
| 21 |
* @return array The route from $to to the root
|
| 22 |
*/
|
| 23 |
function rollback($result, $to) {
|
| 24 |
|
| 25 |
$out = array();
|
| 26 |
$prev = $to;
|
| 27 |
$watch_infinite_loop = 0;
|
| 28 |
while ($result['prev'][$prev] != '-') {
|
| 29 |
$out[] = array('n' => $prev, 'd' => $result['dist'][$prev]);
|
| 30 |
$prev = $result['prev'][$prev];
|
| 31 |
if (++$watch_infinite_loop === 5000) {
|
| 32 |
// It must be an infinite loop. This means that something terrible happens in the code elsewhere
|
| 33 |
return array();
|
| 34 |
}
|
| 35 |
}
|
| 36 |
return $out;
|
| 37 |
}
|
| 38 |
|
| 39 |
/**
|
| 40 |
* Returns the shortest route from <var>$from</var> to <var>$to</var>
|
| 41 |
*
|
| 42 |
* @param array $edges The adjacentcy list of the graph
|
| 43 |
* @param integer $from The from vertex
|
| 44 |
* @param integer $to The to vertex
|
| 45 |
* @param boolean $step If False - Dijkstra, True - BFS
|
| 46 |
*/
|
| 47 |
function a_to_b($edges, $from, $to, $step = FALSE) {
|
| 48 |
if ($from === $to) {
|
| 49 |
return array();
|
| 50 |
}
|
| 51 |
if ($step === FALSE) {
|
| 52 |
$min_tree = a_to_any($edges, $from);
|
| 53 |
}
|
| 54 |
else {
|
| 55 |
$min_tree = breadth_first_walk($edges, $from, -1);
|
| 56 |
}
|
| 57 |
if (isset($min_tree['dist'][$to]) && $min_tree['dist'][$to] !== '-') {
|
| 58 |
$route = rollback($min_tree, $to);
|
| 59 |
$route[] = array('n' => $from, 'd' => 0);
|
| 60 |
return $route;
|
| 61 |
}
|
| 62 |
else {
|
| 63 |
return FALSE;
|
| 64 |
}
|
| 65 |
}
|
| 66 |
|
| 67 |
/**
|
| 68 |
* Measure the needed steps between two vertices
|
| 69 |
*
|
| 70 |
* @param array $edges The adjacentcy list of the graph
|
| 71 |
* @param integer $from The from vertex
|
| 72 |
* @param integer $to The to vertex
|
| 73 |
* @return integer The count of needed steps
|
| 74 |
*/
|
| 75 |
function n_step_distance($edges, $from, $to) {
|
| 76 |
static $cached, $cached_uid;
|
| 77 |
if ($from === $to) {
|
| 78 |
return 0;
|
| 79 |
}
|
| 80 |
if ($cached_uid === $from && is_array($cached)) {
|
| 81 |
/* It's optimal caching because the average_step_separation function
|
| 82 |
calls this function repeatedly */
|
| 83 |
$min_tree = $cached;
|
| 84 |
}
|
| 85 |
else {
|
| 86 |
$min_tree = breadth_first_walk($edges, $from, -1);
|
| 87 |
$cached = $min_tree;
|
| 88 |
$cached_uid = $from;
|
| 89 |
}
|
| 90 |
|
| 91 |
if (isset($min_tree['dist'][$to]) && $min_tree['dist'][$to] !== '-') {
|
| 92 |
$route = rollback($min_tree, $to);
|
| 93 |
return count($route);
|
| 94 |
}
|
| 95 |
else {
|
| 96 |
return FALSE;
|
| 97 |
}
|
| 98 |
}
|
| 99 |
|
| 100 |
/**
|
| 101 |
* Compute the average step of separation in the network
|
| 102 |
*
|
| 103 |
* @param array $edges The adjacentcy list of the graph
|
| 104 |
* @return integer Step of separation
|
| 105 |
*/
|
| 106 |
function average_step_separation($edges) {
|
| 107 |
$users = get_all_vertices();
|
| 108 |
$num = 0;
|
| 109 |
foreach ($users as $uid1) {
|
| 110 |
foreach ($users as $uid2) {
|
| 111 |
if ($uid1 !== $uid2) {
|
| 112 |
$dist = n_step_distance($edges, $uid1, $uid2);
|
| 113 |
if ($dist !== FALSE) {
|
| 114 |
$sum += $dist;
|
| 115 |
++$num;
|
| 116 |
}
|
| 117 |
}
|
| 118 |
}
|
| 119 |
}
|
| 120 |
if ($num != 0) { // Avoid division by zero!
|
| 121 |
return $sum / $num;
|
| 122 |
}
|
| 123 |
else {
|
| 124 |
return 0;
|
| 125 |
}
|
| 126 |
}
|
| 127 |
|
| 128 |
/**
|
| 129 |
* Read the graph from storage
|
| 130 |
*
|
| 131 |
* @param array_ref $edges This array will be filled with the graph's adjacentcy list
|
| 132 |
*/
|
| 133 |
function get_graph(&$edges) {
|
| 134 |
if (variable_get('sna_realtime_network', FALSE) == TRUE) {
|
| 135 |
clear_cache();
|
| 136 |
$graph_source = variable_get('sna_data_source', GRAPH_SOURCE);
|
| 137 |
$build_edges = 'build_edges_from_' . $graph_source;
|
| 138 |
$build_edges($edges);
|
| 139 |
$edges = transform_edges($edges);
|
| 140 |
}
|
| 141 |
else {
|
| 142 |
include(DATA_PATH);
|
| 143 |
}
|
| 144 |
$limit = variable_get('sna_limit', 0);
|
| 145 |
if ($limit > 0) {
|
| 146 |
$edges = shrink($edges, $limit);
|
| 147 |
}
|
| 148 |
//print_r($edges);
|
| 149 |
}
|
| 150 |
|
| 151 |
/**
|
| 152 |
* Breadt-first search algorithm
|
| 153 |
*
|
| 154 |
* @param graph $edges The adjacentcy list of the graph
|
| 155 |
* @param vertex $start Starting vertex
|
| 156 |
* @param integer $max Maximum step. -1 for no limit
|
| 157 |
* @return array Result
|
| 158 |
*/
|
| 159 |
function breadth_first_walk($edges, $start, $max = -1) {
|
| 160 |
// Set start values
|
| 161 |
foreach ($edges as $key => $rel) {
|
| 162 |
$c[$key] = 0;
|
| 163 |
/* Color of point. 0 - white, 1 - grey, 2 - black
|
| 164 |
white - not reached
|
| 165 |
grey - reached
|
| 166 |
black - reached and all neighbours is reached too
|
| 167 |
*/
|
| 168 |
$d[$key] = '-'; // Distance from $start
|
| 169 |
$p[$key] = '-'; // Previous vertex
|
| 170 |
foreach (array_keys($rel) as $child) {
|
| 171 |
$c[$child] = 0;
|
| 172 |
$d[$child] = '-';
|
| 173 |
$p[$child] = '-';
|
| 174 |
}
|
| 175 |
}
|
| 176 |
$c[$start] = 1;
|
| 177 |
$d[$start] = 0;
|
| 178 |
$p[$start] = '-';
|
| 179 |
$Q = array();
|
| 180 |
$Q[] = $start;
|
| 181 |
while (!empty($Q)) {
|
| 182 |
foreach ($Q as $vk => $vertex) {
|
| 183 |
if ($c[$vertex] === 1) {
|
| 184 |
$u = $vertex;
|
| 185 |
$u_k = $vk;
|
| 186 |
break;
|
| 187 |
}
|
| 188 |
}
|
| 189 |
if (($max !== -1) && $d[$u] + 1 > $max) { // Reached the specified depth
|
| 190 |
return array('dist' => $d, 'prev' => $p);
|
| 191 |
}
|
| 192 |
$neighbours = is_array($edges[$u]) ? array_keys($edges[$u]) : array();
|
| 193 |
foreach ($neighbours as $vert) {
|
| 194 |
if ($c[$vert] === 0) {
|
| 195 |
$c[$vert] = 1;
|
| 196 |
$d[$vert] = $d[$u] + 1;
|
| 197 |
$p[$vert] = $u;
|
| 198 |
$Q[] = $vert;
|
| 199 |
}
|
| 200 |
}
|
| 201 |
$c[$u] = 2;
|
| 202 |
unset($Q[$u_k]);
|
| 203 |
}
|
| 204 |
return array('dist' => $d, 'prev' => $p);
|
| 205 |
}
|
| 206 |
|
| 207 |
/**
|
| 208 |
* Depth-first search algorithm
|
| 209 |
*
|
| 210 |
* @param array $edges The adjacentcy list of the graph
|
| 211 |
*/
|
| 212 |
function depth_first_walk($edges) {
|
| 213 |
$all_vertices = get_all_vertices();
|
| 214 |
foreach ($all_vertices as $u) {
|
| 215 |
$c[$u] = 0;
|
| 216 |
/* Color of point. 0 - white, 1 - grey, 2 - black
|
| 217 |
white - not reached
|
| 218 |
grey - reached
|
| 219 |
black - reached and all neighbours is reached too
|
| 220 |
*/
|
| 221 |
$p[$u] = '-'; // Previous vertex
|
| 222 |
}
|
| 223 |
$time = 0;
|
| 224 |
foreach ($all_vertices as $u) {
|
| 225 |
if ($c[$u] === 0) {
|
| 226 |
|
| 227 |
walk($u, $edges, $time, $c, $p, $f, $d);
|
| 228 |
|
| 229 |
}
|
| 230 |
}
|
| 231 |
return array($f, $p);
|
| 232 |
}
|
| 233 |
|
| 234 |
/**
|
| 235 |
* Depth-first search according to a previous BFS result (for interconnected parts)
|
| 236 |
*
|
| 237 |
* @param array $edges The adjacentcy list of the graph
|
| 238 |
* @param array $prev_res The previous BFS's results
|
| 239 |
*/
|
| 240 |
function mod_depth_first_walk($edges, $prev_res) {
|
| 241 |
$prev_f = $prev_res[0];
|
| 242 |
$p = $prev_res[1];
|
| 243 |
$all_vertices = get_all_vertices();
|
| 244 |
foreach ($all_vertices as $u) {
|
| 245 |
$c[$u] = 0;
|
| 246 |
/* Color of point. 0 - white, 1 - grey, 2 - black
|
| 247 |
white - not reached
|
| 248 |
grey - reached
|
| 249 |
black - reached and all neighbours is reached too
|
| 250 |
*/
|
| 251 |
$p[$u] = '-'; // Previous vertex
|
| 252 |
}
|
| 253 |
$time = 0;
|
| 254 |
$prev_f_keys = empty($prev_f) ? array() : array_keys($prev_f);
|
| 255 |
while ($u = array_pop($prev_f_keys)) {
|
| 256 |
if ($c[$u] === 0) {
|
| 257 |
walk($u, $edges, $time, $c, $p, $f, $d);
|
| 258 |
}
|
| 259 |
}
|
| 260 |
return array($f, $p, $d);
|
| 261 |
}
|
| 262 |
|
| 263 |
/**
|
| 264 |
* Helper function for BFS search algorithm
|
| 265 |
*
|
| 266 |
* @param integer $u The vertex's id
|
| 267 |
* @param array $edges The adjacentcy list of the graph
|
| 268 |
*/
|
| 269 |
function walk($u, $edges, &$time, &$c, &$p, &$f, &$d) {
|
| 270 |
|
| 271 |
$c[$u] = 1;
|
| 272 |
$d[$u] = $time++;
|
| 273 |
if (isset($edges[$u])) {
|
| 274 |
foreach (array_keys($edges[$u]) as $v) {
|
| 275 |
if ($c[$v] === 0) {
|
| 276 |
$p[$v] = $u;
|
| 277 |
walk($v, $edges, $time, $c, $p, $f, $d);
|
| 278 |
}
|
| 279 |
}
|
| 280 |
}
|
| 281 |
$c[$u] = 2;
|
| 282 |
$f[$u] = $time++;
|
| 283 |
|
| 284 |
}
|
| 285 |
|
| 286 |
/**
|
| 287 |
* Generate GML for outside tree visualization
|
| 288 |
* Input for http://www.cs.ubc.ca/~sfingram/cs533C/small_world.html
|
| 289 |
*
|
| 290 |
* @param array $tree The BFS search result
|
| 291 |
*/
|
| 292 |
function show_tree($tree) {
|
| 293 |
$num_of_edges = 0;
|
| 294 |
foreach ($tree['prev'] as $vert => $prev) {
|
| 295 |
if (is_numeric($prev)) {
|
| 296 |
$map .= "<param name=\"edge". $num_of_edges++ ."\" value=\"". str_replace(' ', '_', get_real_name($prev)) . ' ' . str_replace(' ', '_', get_real_name($vert)) ."\">";
|
| 297 |
}
|
| 298 |
}
|
| 299 |
$map .= "<param name=\"edgenum\" value=\"". $num_of_edges ."\">";
|
| 300 |
return $map;
|
| 301 |
}
|
| 302 |
|
| 303 |
/**
|
| 304 |
* Generate GML for outside network visualization
|
| 305 |
*
|
| 306 |
*
|
| 307 |
* @param array $edges The adjacentcy list of the graph
|
| 308 |
* @return string The GML string
|
| 309 |
*/
|
| 310 |
function show_map($edges) {
|
| 311 |
$num_of_edges = 0;
|
| 312 |
foreach (array_keys($edges) as $A) {
|
| 313 |
foreach (array_keys($edges[$A]) as $B) {
|
| 314 |
$map .= "<param name=\"edge". $num_of_edges++ ."\" value=\"". str_replace(' ', '_', get_real_name($A)) . ' ' . str_replace(' ', '_', get_real_name($B)) ."\">";
|
| 315 |
|
| 316 |
}
|
| 317 |
|
| 318 |
}
|
| 319 |
$map .= "<param name=\"edgenum\" value=\"". $num_of_edges ."\">";
|
| 320 |
return $map;
|
| 321 |
}
|
| 322 |
|
| 323 |
/**
|
| 324 |
* Transpose a graph.
|
| 325 |
* $new grgraph is $edges with all its edges reversed.
|
| 326 |
*
|
| 327 |
* @param array $edges The original graph
|
| 328 |
* @return array $new_graph The transposed graph
|
| 329 |
*/
|
| 330 |
function transpose($edges) {
|
| 331 |
$transposed_graph = array();
|
| 332 |
foreach (array_keys($edges) as $A) {
|
| 333 |
foreach (array_keys($edges[$A]) as $B) {
|
| 334 |
$transposed_graph[$B][$A] = $edges[$A][$B];
|
| 335 |
}
|
| 336 |
}
|
| 337 |
return $transposed_graph;
|
| 338 |
}
|
| 339 |
|
| 340 |
/**
|
| 341 |
* Collect interconnected subgraphs according to two DFS search.
|
| 342 |
*
|
| 343 |
* @param array $prev The result of DFS
|
| 344 |
* @return array The subgraphs (vertices list)
|
| 345 |
*/
|
| 346 |
function search_groups($edges) {
|
| 347 |
|
| 348 |
$dfs_res = depth_first_walk($edges);
|
| 349 |
|
| 350 |
$mod_dfs_res = mod_depth_first_walk(transpose($edges), $dfs_res);
|
| 351 |
$f = $mod_dfs_res[0];
|
| 352 |
$prev = $mod_dfs_res[1];
|
| 353 |
if (empty($prev)) {
|
| 354 |
return array();
|
| 355 |
}
|
| 356 |
$d = $mod_dfs_res[2];
|
| 357 |
$d = empty($d) ? array() : $d;
|
| 358 |
$f = empty($f) ? array() : $f;
|
| 359 |
$groups = array();
|
| 360 |
$index = 0;
|
| 361 |
foreach (array_keys($prev) as $vert) {
|
| 362 |
if ($prev[$vert] === '-') {
|
| 363 |
$time = $d[$vert] + 1;
|
| 364 |
$groups[$index][] = $vert;
|
| 365 |
while ((($key = array_search($time, $d)) || array_search($time, $f)) && $prev[$key] !== '-') {
|
| 366 |
if (!empty($key)) {
|
| 367 |
$groups[$index][] = $key;
|
| 368 |
unset($prev[$key]);
|
| 369 |
}
|
| 370 |
$time++;
|
| 371 |
}
|
| 372 |
$index++;
|
| 373 |
|
| 374 |
}
|
| 375 |
}
|
| 376 |
return $groups;
|
| 377 |
|
| 378 |
}
|
| 379 |
/**
|
| 380 |
* Throw away edges from an adjacentcy list according to edge weight
|
| 381 |
*
|
| 382 |
* @param array $edges The adjacentcy list of the graph
|
| 383 |
* @return array The shrinked $edges graph
|
| 384 |
*/
|
| 385 |
function shrink($edges, $limit) {
|
| 386 |
foreach (array_keys($edges) as $A) {
|
| 387 |
foreach (array_keys($edges[$A]) as $B) {
|
| 388 |
if ($edges[$A][$B] > $limit) {
|
| 389 |
unset($edges[$A][$B]);
|
| 390 |
}
|
| 391 |
}
|
| 392 |
}
|
| 393 |
return $edges;
|
| 394 |
}
|
| 395 |
|
| 396 |
/**
|
| 397 |
* Collect all the vertices degree
|
| 398 |
*
|
| 399 |
* @param array $edges The adjacentcy list of the graph
|
| 400 |
*/
|
| 401 |
function distribution_of_degree($edges) {
|
| 402 |
$dist = array();
|
| 403 |
foreach (array_keys($edges) as $vertex) {
|
| 404 |
$dist[] = vertex_degree($edges, $vertex);
|
| 405 |
}
|
| 406 |
rsort($dist);
|
| 407 |
return $dist;
|
| 408 |
}
|
| 409 |
|
| 410 |
/**
|
| 411 |
* Draw a distribution of edges picture in SVG format.
|
| 412 |
*
|
| 413 |
* @param array $distribution
|
| 414 |
* @return string The SVG picture file
|
| 415 |
*/
|
| 416 |
function visualize_distribution($distribution) {
|
| 417 |
$max = $distribution[0];
|
| 418 |
$height = count($distribution) == 0 ? 1 : count($distribution);
|
| 419 |
$scale_height_factor = PIC_HEIGHT / $height;
|
| 420 |
$scale_width_factor = PIC_WIDTH / $height;
|
| 421 |
$svg_pic = '<svg width = "'. PIC_WIDTH .'px" height = "'. PIC_HEIGHT .'px" xmlns = "http://www.w3.org/2000/svg">';
|
| 422 |
$svg_pic .= '<g transform="scale('. $scale_width_factor .' '. $scale_height_factor .')">';
|
| 423 |
/* Draw the curve */
|
| 424 |
$svg_pic .= '<polygon style="fill: #000000; stroke: #000000" points="';
|
| 425 |
for ($i = 0; $i < $height; $i++) {
|
| 426 |
if ($num !== 0) {
|
| 427 |
$svg_pic .= ($i + 1) .",". ($height -($height * ($distribution[$i] / $max))) ." ";
|
| 428 |
}
|
| 429 |
}
|
| 430 |
$svg_pic .= "0,". $height;
|
| 431 |
$svg_pic .= ' " /> ';
|
| 432 |
/* Create the captions */
|
| 433 |
$svg_pic .= '<text x = "'. $height * 0.01 .'" y = "'. $height * 0.09 .'"
|
| 434 |
font-family = "Verdana" font-size = "'. $height / 30 .'" fill = "blue" >'. $max .'</text>';
|
| 435 |
$svg_pic .= '</g></svg>';
|
| 436 |
return $svg_pic;
|
| 437 |
}
|
| 438 |
|
| 439 |
/**
|
| 440 |
* Watts-Strogatz: Clustering coefficient
|
| 441 |
* The clustering coefficient for a vertex is the proportion of links between the vertices within
|
| 442 |
* its neighbourhood divided by the number of links that could possibly exist between them.
|
| 443 |
*
|
| 444 |
* @param integer $vertex
|
| 445 |
* @param array $edges The adjacentcy list of the graph
|
| 446 |
*/
|
| 447 |
function clustering_coefficient($edges, $vertex) {
|
| 448 |
if (!isset($edges[$vertex])) {
|
| 449 |
if (function_exists('t')) { // Used in drupal, so we inform the user
|
| 450 |
return t('Cannot compute clustering coefficient while user not have any connection.');
|
| 451 |
}
|
| 452 |
else { // Used in sna_test so possible to be rude :)
|
| 453 |
return FALSE;
|
| 454 |
}
|
| 455 |
}
|
| 456 |
/* Count the edges between the */
|
| 457 |
$num_conn = 0;
|
| 458 |
$neighbours = array_keys($edges[$vertex]);
|
| 459 |
foreach ($neighbours as $vert) {
|
| 460 |
if (is_array($edges[$vert])) {
|
| 461 |
foreach (array_keys($edges[$vert]) as $vert_next) {
|
| 462 |
if (array_search($vert_next, $neighbours) !== FALSE) {
|
| 463 |
$num_conn++;
|
| 464 |
}
|
| 465 |
}
|
| 466 |
}
|
| 467 |
}
|
| 468 |
$kn_vertices = num_vertices_of_complete_graph(count($neighbours));
|
| 469 |
return $kn_vertices === 0 ? 0 : $num_conn / $kn_vertices;
|
| 470 |
}
|
| 471 |
|
| 472 |
/**
|
| 473 |
* Compute the number of edges in Kn graph.
|
| 474 |
*
|
| 475 |
* @param integer $n Number of vertices
|
| 476 |
* @return integer number of edges
|
| 477 |
*/
|
| 478 |
function num_vertices_of_complete_graph($n) {
|
| 479 |
return $n * ($n - 1);
|
| 480 |
}
|
| 481 |
|
| 482 |
/**
|
| 483 |
* Average shortest route
|
| 484 |
*
|
| 485 |
* @param unknown_type $edges
|
| 486 |
* @return unknown
|
| 487 |
*/
|
| 488 |
function average_shortest_route($edges) {
|
| 489 |
$all = get_all_vertices();
|
| 490 |
$how_many_vertices = count($all);
|
| 491 |
$how_many_probe = ceil(log($how_many_vertices) * 10);
|
| 492 |
for ($i = 0; $i < $how_many_probe; $i++) {
|
| 493 |
$rand1 = rand(0, $how_many_vertices - 1);
|
| 494 |
$rand2 = rand(0, $how_many_vertices - 1);
|
| 495 |
if ($rand1 !== $rand2) {
|
| 496 |
print $rand1 ." ". $rand2 ."\n";
|
| 497 |
$best_route = a_to_b($edges, $rand1, $rand2);
|
| 498 |
$sum += count($best_route);
|
| 499 |
}
|
| 500 |
}
|
| 501 |
return $sum / $how_many_probe;
|
| 502 |
}
|
| 503 |
|
| 504 |
?>
|
Parent Directory
| 
Revision Log
| 
Revision Graph