<?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, 3));
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;
}