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!