codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
<?php $graph = array ( 'a' => array(), 'b' => array('a'), 'c' => array('a', 'b'), 'd' => array('a'), 'e' => array('d'), 'f' => array('a', 'b', 'c', 'd'), 'g' => array('d'), 'h' => array('c'), 'i' => array('c', 'g'), 'j' => array(), ); $graph = directed2Undirected($graph); print_r(Distance('c', $graph, 0)); function Distance($node, $graph, $depth = 0) { $result = array(); if (array_key_exists($node, $graph) === true) { $result = array_fill_keys(array_keys($graph), 0); foreach (expand($node, $graph, $depth - 1) as $child) { if (strcmp($node, $child) !== 0) { $result[$child] += $depth; } } $result[$node] = -1; } return $result; } function directed2Undirected($data) { foreach ($data as $key => $values) { foreach ($values as $value) { $data[$value][] = $key; } } return $data; } function expand($id, $data, $depth = 0) { while (--$depth >= 0) { $id = flatten(array_intersect_key($data, array_flip((array) $id))); } return flatten(array_intersect_key($data, array_flip((array) $id))); } function flatten($data) { $result = array(); if (is_array($data) === true) { foreach (new RecursiveIteratorIterator(new RecursiveArrayIterator($data)) as $value) { $result[] = $value; } } return $result; }
Private
[
?
]
Run code
Submit