Page 1 of 1

Help with recursive function needed

Posted: Sat Jul 10, 2010 3:19 pm
by drone076
Hi there!

I have a file like that:

Code: Select all

1 2
1 3
1 4
2 5
7 5
3 4
8 6
9 22
....
There're two columns records - connection points of the graphs per line. Point 1 connected with point 2, 3 and 4. And point 2 connected to point 5 and so on...
Every point can exists in any column. So what I need in output is an array like this:

Code: Select all

0 => '1,2,3,4,5,7',
1 => '8,6',
2 => '9,22',
...
Cause there're can be many graphs described in the file. For such a task I need to use recursive function call to array walk, but my mind goes crazy how this can be done.
Can you help, pls. Thanks beforehand.

Re: Help with recursive function needed

Posted: Sat Jul 10, 2010 3:42 pm
by requinix

Code: Select all

$lines = array_map("trim", file($filename));

$array = array();
$lookup = array();

foreach ($lines as $line) {
	list($a, $b) = explode(" ", $line);
	if (isset($lookup[$a]) && isset($lookup[$b])) {
		// no action needed
	} else if (isset($lookup[$a])) { // but not $b
		$lookup[$a][] = $b;
		$lookup[$b] =& $lookup[$a];
	} else if (isset($lookup[$b])) { // but not $a
		$lookup[$b][] = $a;
		$lookup[$a] =& $lookup[$b];
	} else {
		$n = count($array);
		$array[$n] = array($a, $b);
		$lookup[$a] =& $array[$n];
		$lookup[$b] =& $array[$n];
	}
}
With a bit of modification you can get it to use a string of 1,2,3 instead, but you can easily get that from the array generated here.

Re: Help with recursive function needed

Posted: Sun Jul 11, 2010 2:04 am
by drone076
tasairis wrote:With a bit of modification you can get it to use a string of 1,2,3 instead, but you can easily get that from the array generated here.
Thank you! You make my day!

I do this:

Code: Select all

$graphs = array();
$gcount = 0;
// read file
while($string = // whilenot EOF)
{
    $id = explode(" ",$string);  
 
    $i = 0;
    while ($i < $gcount){
        // are points in graph
        $in0 = in_array($id[0], $graphs[$i]));
        $in1 = in_array($id[1], $graphs[$i]));
           
        if ($in0) {
            if (!$in1) $graphs[$i][] = $id[1]; // point $id[0] exists in graph, but not point $id[1] => add
            break; // graph found
        } else {
            if ($in1) {
                $graphs[$i][] = $id[0]; // point $id[1] exists, but not point $id[0] => add
                break; // graph found
            }            
        }
        $i++;
    }

    if ($i == $gcount){
        // new graph? => add one
        $graphs[] = array($id[0], $id[1]);
        $gcount++;
    }
}
print_r($graphs);
I've think about recursion cause of task like "Finding strongly connected components" - http://en.wikipedia.org/wiki/Strongly_c ... _component

Thank you so much!