Help with recursive function needed

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
drone076
Forum Newbie
Posts: 2
Joined: Sat Jul 10, 2010 3:10 pm

Help with recursive function needed

Post 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.
Last edited by drone076 on Sun Jul 11, 2010 2:05 am, edited 1 time in total.
User avatar
requinix
Spammer :|
Posts: 6617
Joined: Wed Oct 15, 2008 2:35 am
Location: WA, USA

Re: Help with recursive function needed

Post 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.
drone076
Forum Newbie
Posts: 2
Joined: Sat Jul 10, 2010 3:10 pm

Re: Help with recursive function needed

Post 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!
Post Reply