[ create a new paste ] login | about

Link: http://codepad.org/8zsGX4tq    [ raw code | output | fork ]

PHP, pasted on May 30:
<?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, 1));
    
    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;
    }


Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
Array
(
    [a] => 1
    [b] => 1
    [c] => -1
    [d] => 0
    [e] => 0
    [f] => 1
    [g] => 0
    [h] => 1
    [i] => 1
    [j] => 0
)


Create a new paste based on this one


Comments: