/[drupal]/contributions/modules/sna/routes.php
ViewVC logotype

Diff of /contributions/modules/sna/routes.php

Parent Directory Parent Directory | Revision Log Revision Log | View Revision Graph Revision Graph | View Patch Patch

revision 1.1, Wed Aug 16 15:25:46 2006 UTC revision 1.2, Thu Aug 17 14:53:04 2006 UTC
# Line 24  function rollback($result, $to) { Line 24  function rollback($result, $to) {
24    
25    $out = array();    $out = array();
26    $prev = $to;    $prev = $to;
27      $watch_infinite_loop = 0;
28    while ($result['prev'][$prev] != '-') {    while ($result['prev'][$prev] != '-') {
29      $out[] = array('n' => $prev, 'd' => $result['dist'][$prev]);      $out[] = array('n' => $prev, 'd' => $result['dist'][$prev]);
30      $prev = $result['prev'][$prev];      $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;    return $out;
37  }  }
# Line 50  function a_to_b($edges, $from, $to, $ste Line 54  function a_to_b($edges, $from, $to, $ste
54    else {    else {
55      $min_tree = breadth_first_walk($edges, $from, -1);      $min_tree = breadth_first_walk($edges, $from, -1);
56    }    }
   /*print "eredm\n";  
   print_r($min_tree);  
   print "eredmvege\n";  
   ob_flush();*/  
57    if (isset($min_tree['dist'][$to]) && $min_tree['dist'][$to] !== '-') {    if (isset($min_tree['dist'][$to]) && $min_tree['dist'][$to] !== '-') {
58      $route = rollback($min_tree, $to);      $route = rollback($min_tree, $to);
59      $route[] = array('n' => $from, 'd' => 0);      $route[] = array('n' => $from, 'd' => 0);
# Line 111  function average_step_separation($edges) Line 111  function average_step_separation($edges)
111        if ($uid1 !== $uid2) {        if ($uid1 !== $uid2) {
112          $dist = n_step_distance($edges, $uid1, $uid2);          $dist = n_step_distance($edges, $uid1, $uid2);
113          if ($dist !== FALSE) {          if ($dist !== FALSE) {
           //print "F:" . $uid1 . " T:" . $uid2 . " D:" . $dist . "\n";  
114            $sum += $dist;            $sum += $dist;
115            ++$num;            ++$num;
116          }          }
117        }        }
118      }      }
     //print $uid1 . " is done\n";  
119    }    }
120    if ($num != 0) {  // Avoid division by zero!    if ($num != 0) {  // Avoid division by zero!
121      return $sum / $num;      return $sum / $num;
# Line 202  function breadth_first_walk($edges, $sta Line 200  function breadth_first_walk($edges, $sta
200   * @param array $edges The adjacentcy list of the graph   * @param array $edges The adjacentcy list of the graph
201   */   */
202  function depth_first_walk($edges) {  function depth_first_walk($edges) {
203    foreach (array_keys($edges) as $u) {    $all_vertices = get_all_vertices();
204      foreach ($all_vertices as $u) {
205      $c[$u] = 0;      $c[$u] = 0;
206      /* Color of point. 0 - white, 1 - grey, 2 - black      /* Color of point. 0 - white, 1 - grey, 2 - black
207          white - not reached          white - not reached
# Line 212  function depth_first_walk($edges) { Line 211  function depth_first_walk($edges) {
211      $p[$u] = '-';    // Previous vertex      $p[$u] = '-';    // Previous vertex
212    }    }
213    $time = 0;    $time = 0;
214    foreach (array_keys($edges) as $u) {    foreach ($all_vertices as $u) {
215      if ($c[$u] === 0) {      if ($c[$u] === 0) {
216    
217        walk($u, $edges, $time, $c, $p, $f, $d);        walk($u, $edges, $time, $c, $p, $f, $d);
# Line 231  function depth_first_walk($edges) { Line 230  function depth_first_walk($edges) {
230  function mod_depth_first_walk($edges, $prev_res) {  function mod_depth_first_walk($edges, $prev_res) {
231    $prev_f = $prev_res[0];    $prev_f = $prev_res[0];
232    $p = $prev_res[1];    $p = $prev_res[1];
233    foreach (array_keys($edges) as $u) {    $all_vertices = get_all_vertices();
234      foreach ($all_vertices as $u) {
235      $c[$u] = 0;      $c[$u] = 0;
236      /* Color of point. 0 - white, 1 - grey, 2 - black      /* Color of point. 0 - white, 1 - grey, 2 - black
237          white - not reached          white - not reached
# Line 260  function walk($u, $edges, &$time, &$c, & Line 260  function walk($u, $edges, &$time, &$c, &
260    
261    $c[$u] = 1;    $c[$u] = 1;
262    $d[$u] = $time++;    $d[$u] = $time++;
263    foreach (array_keys($edges[$u]) as $v) {    if (isset($edges[$u])) {
264      if ($c[$v] === 0) {      foreach (array_keys($edges[$u]) as $v) {
265        $p[$v] = $u;        if ($c[$v] === 0) {
266        walk($v, $edges, $time, $c, $p, $f, $d);          $p[$v] = $u;
267            walk($v, $edges, $time, $c, $p, $f, $d);
268          }
269      }      }
270    }    }
271    $c[$u] = 2;    $c[$u] = 2;
# Line 316  function show_map($edges) { Line 318  function show_map($edges) {
318   * @return array $new_graph The transposed graph   * @return array $new_graph The transposed graph
319   */   */
320  function transpose($edges) {  function transpose($edges) {
321    $new_graph = array();    $transposed_graph = array();
322    foreach (array_keys($edges) as $A) {    foreach (array_keys($edges) as $A) {
323      foreach (array_keys($edges[$A]) as $B) {      foreach (array_keys($edges[$A]) as $B) {
324        $new_graph[$B][$A] = $edges[$A][$B];        $transposed_graph[$B][$A] = $edges[$A][$B];
325      }      }
326    }    }
327    return $new_graph;    return $transposed_graph;
328  }  }
329    
330  /**  /**
# Line 355  function search_groups($edges) { Line 357  function search_groups($edges) {
357            $groups[$index][] = $key;            $groups[$index][] = $key;
358            unset($prev[$key]);            unset($prev[$key]);
359          }          }
       //$vert_prev = $prev[$vert_prev];  
360          $time++;          $time++;
361        }        }
362        $index++;        $index++;
# Line 397  function distribution_of_degree($edges) Line 398  function distribution_of_degree($edges)
398  }  }
399    
400  /**  /**
401   * Draw a distribution of edges picture in SVG format. (should be replaced with imagemagick integration module?)   * Draw a distribution of edges picture in SVG format.
402   *   *
403   * @param array $distribution   * @param array $distribution
404   * @return string The SVG picture file   * @return string The SVG picture file
# Line 444  function clustering_coefficient($edges, Line 445  function clustering_coefficient($edges,
445    }    }
446    /* Count the edges between the */    /* Count the edges between the */
447    $num_conn = 0;    $num_conn = 0;
   //print_r($edges);  
448    $neighbours = array_keys($edges[$vertex]);    $neighbours = array_keys($edges[$vertex]);
449    foreach ($neighbours as $vert) {    foreach ($neighbours as $vert) {
450      if (is_array($edges[$vert])) {      if (is_array($edges[$vert])) {
Legend:
Removed from v.1.1  
changed lines
  Added in v.1.2
  ViewVC Help
Powered by ViewVC 1.1.2