My Gallery recently had some serious database issues. I had to write some code outside of the Gallery proper to look for database errors. When I went to look for cycles in the tree, I didn't find any handy algorithms out in the wild of the internet, so I wrote something.
/**
* Takes an adjacency list: an array of parent/child relationships
* array(array(1,2));
*/
function check_for_cycles($relationships) {
$roots = array();
foreach ($relationships as $row) {
$parent = $row[0];
$child = $row[1];
/* this is the meat of the algorithm and makes
* use of references to put children into sets.
* You could draw an analogy to disjoint set
* forests here, but thanks to the magic of
* references the hierarchy collapses much
* more quickly
*/
if (isset($roots[$parent])) {
$roots[$child] =& $roots[$parent];
} else {
if (isset($roots[$child])) {
$roots[$child] = $parent;
$roots[$parent] =& $roots[$child];
} else {
$roots[$parent] = $parent;
$roots[$child] =& $roots[$parent];
}
}
if ($roots[$parent] == $child) {
return array($parent, $child);
}
}
return false;
}
/**
* Test code
*/
$lists = array('1:2,2:3,3:4',
'1:2,2:3,3:1',
'1:2,2:3,4:1,3:4',
'1:2,2:1');
foreach ($lists as $list) {
$relationships = array();
foreach (explode(',', $list) as $pair) {
$relationships[] = explode(':', $pair);
}
if (check_for_cycles($relationships)) {
echo "Found cycle in $list\n";
}
}
?>
That produces this output:Found cycle in 1:2,2:3,3:1
Found cycle in 1:2,2:3,4:1,3:4
Found cycle in 1:2,2:1
I hope that helps whomever might be searching for this very algorithm. Please note that this does not detect duplicate children or missing parents.
