|
|
Posted by Henk Verhoeven on 10/18/05 22:15
Hi Thomas,
Generally, for recursion detection you use a "Set". You use a either
breadth first search or a depth first search algorithm to go through the
graph of data structures, collection and/or objects and put every node
into the Set (google for these algorithms, or for backtracking
algorithm). Before every next step you also check if the next node is
already in the Set. The Set can answer this question very fast becuase
it uses Hashing. If it is in the set, skip it.
Your problem: php has no Set. But you can use an associative array and
add unique keys for each node, with some not-null value as value.
Something like this:
$visitedKeys[getUniqueKey($node)] = true;
Now you can check wheather the node was already visited by:
isSet($visitedKeys[getUniqueKey($node)])
I bet associative arrays use hasing, just like Sets (lookup is so fast).
Of course you do have to program the getUniqueKey function to work with
your actual data ;-)
Greetings,
Henk Verhoeven,
www.phpPeanuts.org
Thomas Mlynarczyk wrote:
> Hi,
>
> Say I have an array containing a reference to itself:
> $myArray = array();
> $myArray['self'] =& $myArray;
> How can I, looping iteratively through the array, detect the fact that
> $myArray['self'] will "take" me to where I have already been? The print_r()
> and var_dump() functions print *RECURSION* in such a case (though only after
> the "second round"). Setting a flag seems to be the only solution, but I
> don't want to modify the array in question - I want to produce a visual
> representation of its contents like var_dump(), but formatted to my taste. I
> had considered parsing the output of var_dump(), but first, that format
> might change in a future version of PHP and second, an array key might be a
> string resembling part of the output (like $myArray['["myArray"]=>']), which
> seems to be difficult to detect by the parsing code.
>
> Is there another way of doing this?
>
> Greetings,
> Thomas
>
>
Navigation:
[Reply to this message]
|