referral system using modified preordered tree traversal

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
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

referral system using modified preordered tree traversal

Post by s.dot »

Currently, this is how I'm displaying the number of people in a given persons downline (their referrals, their referrals referrals, etc..)

Code: Select all

function display($root, $level_limit)
{
    //count
    $downcount = 0;
// retrieve the left and right value of the $root node
    $result = mysql_query('SELECT `left_boundary`, `right_boundary` FROM `downline` WHERE `username` = "'.$root.'";') or die(mysql_error());
    $row = mysql_fetch_array($result);
 
    // start with an empty $right stack
    $right = array();
 
    // now, retrieve all descendants of the $root node
    $result = mysql_query('SELECT `username`, `left_boundary`, `right_boundary` FROM `downline` WHERE `left_boundary` BETWEEN '.$row['left_boundary'].' AND '.$row['right_boundary'].' AND `exists` = 1 GROUP BY `username` ORDER BY `left_boundary` ASC;') or die(mysql_error());
    
    // display each row
    while($row = mysql_fetch_assoc($result))
    {
        // only check stack if there is one
        if(count($right)>0)
        {
            // check if we should remove a node from the stack
            while($right[count($right)-1] < $row['right_boundary'])
            {
                array_pop($right);
            }
        }
 
        // display indented node title
        if($row['username'] != $_SESSION['user_name'])
        {
            $level = 1*count($right);
            
            if($level <= $level_limit)
            {
                $downcount++;
            }
        }
 
        // add this node to the stack
        $right[] = $row['right_boundary'];
    }
}
I'm wondering if there's a way I can query for all the members within a specific level limit (say 5 levels deep) without using the $downcount variable inside of a condition. If I can, this will allow me to paginate the results.

Err.. hope I can make myself clear enough. I want to be able to get all members of bob's downline 5 levels deep within a query. Hopefully someone has good experience with referral systems and downlines. :)
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
EverLearning
Forum Contributor
Posts: 282
Joined: Sat Feb 23, 2008 3:49 am
Location: Niš, Serbia

Re: referral system using modified preordered tree traversal

Post by EverLearning »

Code below should work. Let me know how it goes.

Code: Select all

 
$sql = '
    SELECT d.username, d.left_boundary, d.right_boundary, COUNT(*) as level
        FROM downline d
            INNER JOIN downline d2 ON d.left_boundary BETWEEN d2.left_boundary AND d2.right_boundary
        WHERE d.left_boundary BETWEEN '.$row['left_boundary'].' AND '.$row['right_boundary'].' 
            AND d2.left_boundary > '.$row['left_boundary'].'
            AND exists = 1 
        GROUP BY username 
        HAVING level <= 5
        ORDER BY level asc';
 
User avatar
EverLearning
Forum Contributor
Posts: 282
Joined: Sat Feb 23, 2008 3:49 am
Location: Niš, Serbia

Re: referral system using modified preordered tree traversal

Post by EverLearning »

If you want to learn more about "modified preordered tree traversal" read

Joe Celko's Trees and Hierarchies in SQL for Smarties

EDIT | And there are some nice examples in Pro MySQL in Chapter 8 - "SQL Scenarios"
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Re: referral system using modified preordered tree traversal

Post by s.dot »

Thank you for your generous code sample. I will give it a try and update this topic tonight. Just knowing that it may be possible using a query is very relieving. :)

Thanks for the links -- I may need those. Hierarchical data is not my friend :P:
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
EverLearning
Forum Contributor
Posts: 282
Joined: Sat Feb 23, 2008 3:49 am
Location: Niš, Serbia

Re: referral system using modified preordered tree traversal

Post by EverLearning »

With nested sets you can do pretty much anything that comes to mind, but statements can become quite big, involve multiple self joins, subqueries ... :D
Post Reply