SitePoint Sponsor

User Tag List

Results 1 to 10 of 10
  1. #1
    SitePoint Addict
    Join Date
    Nov 2004
    Location
    New Jersey
    Posts
    317
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Adjacency list table to Nested Set table conversion algorithm?

    Say I have an table of categories as an adjacency list; there are three columns in the table: CategoryID (the primary key; an auto-incrementing field, the actual value is not important), CategoryName, and ParentID (which is NULL for top-level categories).

    What would be the algorithm for creating a nested set table from this adjacency list table? (with the nested set table containing CategoryID, CategoryName, lft, and rgt columns)

  2. #2
    SitePoint Wizard Ren's Avatar
    Join Date
    Aug 2003
    Location
    UK
    Posts
    1,060
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    In some pseudo PHP its ...

    Code:
    function recursive($category, $left = 0)
    {
         $right = $left + 1;
         $children = getCategoryChildren($category->categoryID);
         foreach($children as $child)
              $right = recursive($child, $right);
         
        mysql_query('INSERT INTO Category VALUES($category->categoryID, $left, $right, $category->name)');    
    
         return $right + 1;
    }

  3. #3
    SitePoint Wizard Ren's Avatar
    Join Date
    Aug 2003
    Location
    UK
    Posts
    1,060
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Also, once thats done, its a good idea to re-order the rows by left ascending order.

    INSERT INTO RealCategory
    SELECT * FROM Category ORDER BY left ASC

    Because thats the order your mostly be needing.

  4. #4
    SitePoint Addict
    Join Date
    Nov 2004
    Location
    New Jersey
    Posts
    317
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thank you very much, that was of great help to me.
    Quote Originally Posted by Ren
    Also, once thats done, its a good idea to re-order the rows by left ascending order.
    Well, I'm using an index on 'lft' so hopefully this won't be necessary.

    Thanks

  5. #5
    SitePoint Member
    Join Date
    Jan 2011
    Posts
    5
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by Ren View Post
    In some pseudo PHP its ...

    Code:
    function recursive($category, $left = 0)
    {
         $right = $left + 1;
         $children = getCategoryChildren($category->categoryID);
         foreach($children as $child)
              $right = recursive($child, $right);
         
        mysql_query('INSERT INTO Category VALUES($category->categoryID, $left, $right, $category->name)');    
    
         return $right + 1;
    }
    Thanks for the pseudo code. I tried to implement it, however I keep getting a bunch of rows with the same value for "left" which I know shouldn't be the case. I think we're missing a step in the pseudo routine. Can someone provide a real-code example? I'm perplexed. Thanks in advance.

  6. #6
    SitePoint Member
    Join Date
    Jan 2011
    Posts
    5
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I tried to translate your pseudo code to real code and ran into a problem...


    PHP Code:
    <?php

    /**

    --
    -- Table structure for table `adjacent_table`
    --

    CREATE TABLE IF NOT EXISTS `adjacent_table` (
      `id` int(11) NOT NULL AUTO_INCREMENT,
      `father_id` int(11) DEFAULT NULL,
      `category` varchar(128) DEFAULT NULL,
      PRIMARY KEY (`id`)
    ) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=8 ;

    --
    -- Dumping data for table `adjacent_table`
    --

    INSERT INTO `adjacent_table` (`id`, `father_id`, `category`) VALUES
    (1, 0, 'ROOT'),
    (2, 1, 'Books'),
    (3, 1, 'CD''s'),
    (4, 1, 'Magazines'),
    (5, 2, 'Hard Cover'),
    (6, 2, 'Large Format'),
    (7, 4, 'Vintage');

    --
    -- Table structure for table `nested_table`
    --

    CREATE TABLE IF NOT EXISTS `nested_table` (
      `id` int(11) NOT NULL AUTO_INCREMENT,
      `lft` int(11) DEFAULT NULL,
      `rgt` int(11) DEFAULT NULL,
      `category` varchar(128) DEFAULT NULL,
      PRIMARY KEY (`id`)
    ) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=1 ;

    */

        
    mysql_connect('localhost','USER','PASSWORD') or die(mysql_error());
        
    mysql_select_db('DATABASE') or die(mysql_error());
        
    adjacent_to_nested(0);

        
    /**
         * adjacent_to_nested
         *
         * Reads a "adjacent model" table and converts it to a "Nested Set" table.
         * @param    integer        $i_id            Should be the id of the "root node" in the adjacent table;
         * @param    integer        $i_left            Should only be used on recursive calls.  Holds the current value for lft
         */
        
    function adjacent_to_nested($i_id$i_left 0)
        {
                    
            
    // the right value of this node is the left value + 1
            
    $i_right $i_left 1;
            
            
    // get all children of this node
            
    $a_children get_source_children($i_id);
            foreach  (
    $a_children as $a)
            {
                
                
    // recursive execution of this function for each child of this node
                // $i_right is the current right value, which is incremented by the 
                // import_from_dc_link_category method
                
    $i_right adjacent_to_nested($a['id'], $i_right);

                
    // insert stuff into the our new "Nested Sets" table
                
    $s_query "
                    INSERT INTO `nested_table` (`id`, `lft`, `rgt`, `category`) 
                    VALUES(
                        NULL, 
                        '"
    .$i_left."',
                        '"
    .$i_right."',
                        '"
    .mysql_real_escape_string($a['category'])."'
                    )
                "
    ;
                if (!
    mysql_query($s_query))
                {
                    echo 
    "<pre>$s_query</pre>\n";
                    throw new 
    Exception(mysql_error());  
                }
                echo 
    "<p>$s_query</p>\n";
                
                
    // get the newly created row id
                
    $i_new_nested_id mysql_insert_id();

            }
            
            return 
    $i_right 1;
        }



        
    /**
         * get_source_children
         *
         * Examines the "adjacent" table and finds all the immediate children of a node
         * @param    integer        $i_id            The unique id for a node in the adjacent_table table
         * @return    array                        Returns an array of results or an empty array if no results.
         */
        
    function get_source_children($i_id)
        {
            
            
            
    $a_return = array();
            
    $s_query "SELECT * FROM `adjacent_table` WHERE `father_id` = '".$i_id."'";
            if (!
    $i_result mysql_query($s_query))
            {
                echo 
    "<pre>$s_query</pre>\n";
                throw new 
    Exception(mysql_error());  
            }
            if (
    mysql_num_rows($i_result) > 0)
            {
                while(
    $a mysql_fetch_assoc($i_result))
                {
                    
    $a_return[] = $a;
                }
            }
            
            return 
    $a_return;
        }
        
    ?>

    I get the following output...


    INSERT INTO `nested_table` (`id`, `lft`, `rgt`, `category`) VALUES( NULL, '2', '5', 'Hard Cover' )

    INSERT INTO `nested_table` (`id`, `lft`, `rgt`, `category`) VALUES( NULL, '2', '7', 'Large Format' )

    INSERT INTO `nested_table` (`id`, `lft`, `rgt`, `category`) VALUES( NULL, '1', '8', 'Books' )

    INSERT INTO `nested_table` (`id`, `lft`, `rgt`, `category`) VALUES( NULL, '1', '10', 'CD\'s' )

    INSERT INTO `nested_table` (`id`, `lft`, `rgt`, `category`) VALUES( NULL, '10', '13', 'Vintage' )

    INSERT INTO `nested_table` (`id`, `lft`, `rgt`, `category`) VALUES( NULL, '1', '14', 'Magazines' )

    INSERT INTO `nested_table` (`id`, `lft`, `rgt`, `category`) VALUES( NULL, '0', '15', 'ROOT' )

    As you can see there are multiple rows with the same value for lft. That should not be the case. It is as if the "left id" portion of the pseudo code is not being updated. I think a step was left out. Can anyone help?

  7. #7
    SitePoint Member
    Join Date
    Jan 2011
    Posts
    5
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Talking

    UPDATE - PROBLEM SOLVED

    First off, I had mistakenly believed that the source table (the one in adjacent-lists format) needed to be altered to include a source node. This is not the case. Secondly, I found a class via BING that does the trick. I've altered it for PHP5 and converted the original author's mysql related bits to basic PHP. He was using a DB class. You can convert them to your own database abstraction class later if you want.

    Obviously, if your "source table" has other columns that you want to move to the nested set table, you will have to adjust the write method in the class below.

    Hopefully this will save someone else from the same problems in the future.

    PHP Code:
    <?php

    /**


    --
    -- Table structure for table `adjacent_table`
    --

    DROP TABLE IF EXISTS `adjacent_table`;
    CREATE TABLE IF NOT EXISTS `adjacent_table` (
      `id` int(11) NOT NULL AUTO_INCREMENT,
      `father_id` int(11) DEFAULT NULL,
      `category` varchar(128) DEFAULT NULL,
      PRIMARY KEY (`id`)
    ) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=8 ;

    --
    -- Dumping data for table `adjacent_table`
    --

    INSERT INTO `adjacent_table` (`id`, `father_id`, `category`) VALUES
    (1, 0, 'Books'),
    (2, 0, 'CD''s'),
    (3, 0, 'Magazines'),
    (4, 1, 'Hard Cover'),
    (5, 1, 'Large Format'),
    (6, 3, 'Vintage');

    --
    -- Table structure for table `nested_table`
    --

    DROP TABLE IF EXISTS `nested_table`;
    CREATE TABLE IF NOT EXISTS `nested_table` (
      `lft` int(11) NOT NULL DEFAULT '0',
      `rgt` int(11) DEFAULT NULL,
      `id` int(11) DEFAULT NULL,
      `category` varchar(128) DEFAULT NULL,
      PRIMARY KEY (`lft`),
      UNIQUE KEY `id` (`id`),
      UNIQUE KEY `rgt` (`rgt`)
    ) ENGINE=MyISAM DEFAULT CHARSET=latin1;

    */

        /**
         * @class   tree_transformer
         * @author  Paul Houle, Matthew Toledo
         * @created 2008-11-04
         * @url     http://gen5.info/q/2008/11/04/nested-sets-php-verb-objects-and-noun-objects/
         */
        
    class tree_transformer 
        
    {

            private 
    $i_count;
            private 
    $a_link;

            public function 
    __construct($a_link
            {
                if(!
    is_array($a_link)) throw new Exception("First parameter should be an array. Instead, it was type '".gettype($a_link)."'");
                
    $this->i_count 1;
                
    $this->a_link$a_link;
            }

            public function 
    traverse($i_id
            {
                
    $i_lft $this->i_count;
                
    $this->i_count++;

                
    $a_kid $this->get_children($i_id);
                if (
    $a_kid
                {
                    foreach(
    $a_kid as $a_child
                    {
                        
    $this->traverse($a_child);
                    }
                }
                
    $i_rgt=$this->i_count;
                
    $this->i_count++;
                
    $this->write($i_lft,$i_rgt,$i_id);
            }   

            private function 
    get_children($i_id
            {
                return 
    $this->a_link[$i_id];
            }

            private function 
    write($i_lft,$i_rgt,$i_id
            {

                
    // fetch the source column
                
    $s_query "SELECT * FROM `adjacent_table` WHERE `id`  = '".$i_id."'";
                if (!
    $i_result mysql_query($s_query))
                {
                    echo 
    "<pre>$s_query</pre>\n";
                    throw new 
    Exception(mysql_error());  
                }
                
    $a_source = array();
                if (
    mysql_num_rows($i_result))
                {
                    
    $a_source mysql_fetch_assoc($i_result);
                }

                
    // root node?  label it unless already labeled in source table
                
    if (== $i_lft && empty($a_source['category']))
                {
                    
    $a_source['category'] = 'ROOT';
                }

                
    // insert into the new nested tree table
                // use mysql_real_escape_string because one value "CD's"  has a single '
                
    $s_query "
                    INSERT INTO `nested_table`
                    (`id`,`lft`,`rgt`,`category`)
                    VALUES (
                        '"
    .$i_id."',
                        '"
    .$i_lft."',
                        '"
    .$i_rgt."',
                        '"
    .mysql_real_escape_string($a_source['category'])."'
                    )
                "
    ;
                if (!
    $i_result mysql_query($s_query))
                {
                    echo 
    "<pre>$s_query</pre>\n";
                    throw new 
    Exception(mysql_error());  
                }
                else
                {
                    
    // success:  provide feedback
                    
    echo "<p>$s_query</p>\n";
                }
            }
        }

        
    mysql_connect('localhost','USER','PASSWORD') or die(mysql_error());
        
    mysql_select_db('DATABASE') or die(mysql_error());

        
    // build a complete copy of the adjacency table in ram
        
    $s_query "SELECT `id`,`father_id` FROM `adjacent_table`";
        
    $i_result mysql_query($s_query);
        
    $a_rows = array();
        while (
    $a_rows[] = mysql_fetch_assoc($i_result));
        
    $a_link = array();
        foreach(
    $a_rows as $a_row
        {
            
    $i_father_id $a_row['father_id'];
            
    $i_child_id $a_row['id'];
            if (!
    array_key_exists($i_father_id,$a_link)) 
            {
                
    $a_link[$i_father_id]=array();
            }
            
    $a_link[$i_father_id][]=$i_child_id;
        }

        
    $o_tree_transformer = new tree_transformer($a_link);
        
    $o_tree_transformer->traverse(0);

    ?>
    Here is the output...

    INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '4', '3', '4', 'Hard Cover' )

    INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '5', '5', '6', 'Large Format' )

    INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '1', '2', '7', 'Books' )

    INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '2', '8', '9', 'CD\'s' )

    INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '6', '11', '12', 'Vintage' )

    INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '3', '10', '13', 'Magazines' )

    INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '0', '1', '14', 'ROOT' )

  8. #8
    SitePoint Member
    Join Date
    Jan 2011
    Posts
    2
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    or

    PHP Code:
        function shapeshift($lft 1,$father 1)
        {
                    
    //Your DB class here. Check JDatabase for functions 
                    //(like $db->loadobject()  etc);
            
    $db = & JFactory::getDBO();

            
    $tbl_from 'temp_data.adjacent_table';
            
    $tbl_to   'temp_data.nested_table';        
            
    $rgt $lft+1;

            
    $query "select * from $tbl_from where id = $father";
            
    $db->setQuery($query);
            
    $cat $db->loadObject();        

            
    $query "select * from $tbl_from where father_id = $father";
            
    $db->setQuery($query);
            
    $sibs $db->loadObjectList();        
            foreach (
    $sibs as $sib)
            {
                
    $rgt shapeshift($rgt,$sib->id);
            }
            
    $query "insert into $tbl_to (id,lft,rgt,category) values ($cat->id,$lft,$rgt,'$cat->category')";
            
    $db->setQuery($query);
            
    $db->Query();
            return 
    $rgt+1;
        } 


    Enjoy.

  9. #9
    SitePoint Member
    Join Date
    Jan 2011
    Posts
    5
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I'm pretty sure this is the same exact routine as the pseudo code. If that is the case, the left_id will not update correctly. Could you post a non-db-abstraction-class'ed version so I can check it out easily.

  10. #10
    SitePoint Member
    Join Date
    Jan 2011
    Posts
    2
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by mrbinky3000 View Post
    I'm pretty sure this is the same exact routine as the pseudo code. If that is the case, the left_id will not update correctly. Could you post a non-db-abstraction-class'ed version so I can check it out easily.
    This one does works, does updates it all. It is checked, and even sold few times allready ^_^
    I'm sorry but i don't have time to translate it to straight mysql classes, so - you'll have to do it by yourselve, sorry.
    This is how it works in my particular case.
    PHP Code:
    //Generates lft and rgt for 
        
    function shapeshift($lft 1,$father 0,$isroot=false)
        {
            
    $db = & JFactory::getDBO();
            
    $tbl_from '#__sct_category';
            
    $tbl_to   '#__sct_category';        

            
    $query "select * from $tbl_from where id = $father";
            
    $db->setQuery($query);
            
    $cat $db->loadObject();        
                
    $rgt $lft+1;
                
    $query "select * from $tbl_from where parent_id = $father";
                
    $db->setQuery($query);
                
    $sibs $db->loadObjectList();        
                foreach (
    $sibs as $sib)
                {
                    
    $rgt $this->shapeshift($rgt,$sib->id);
                }
                
    $query "update $tbl_to set lft = $lft,rgt = $rgt where id = $cat->id";
                
    $db->setQuery($query);
                
    $db->Query();
                
    $rgt+=1;
            return 
    $rgt;
        } 

    And in case of NOT SINGLE root category -

    PHP Code:
    //And if you have a lot of roots - call proc sequently for each,
    //updating lft 
            
    $left 1;        
            foreach (
    $allroots as $root)
            {
                
    //$this->l->error("Sent $root->id to shapeshift");
                
    $left $this->shapeshift($left,$root->id,true);
            } 
    .
    And to end this article (^_^) i'll put last useful piece that I've made

    PHP Code:
    //this one moves rgt values, IF you have created some cats,
    //that are started from some cat(not from root)        

    //This piece of code comes before upper one.
            
    if($lim_cat)
            {
                
    $query "select lft from $tbl_to where id = $lim_cat ";
                
    $db->setQuery($query);
                
    $oldleft $db->loadResult() + 1;            
    //Important! You have to start with left = oldleft in such case...
                
    $left $oldleft;
            }        

    //Calling the shapeshifter

            
    if($lim_cat)
            {
                
    $query "select max(rgt) from $tbl_from ";
                
    $db->setQuery($query);
                
    $right $db->loadResult() + 1;
                
    //Shift all existing cats by generated right value
                
    $query "update $tbl_to set lft = lft+$right, rgt = rgt+$right "
                
    ." where lft > $oldleft";
                
    $db->setQuery($query);
                
    $db->Query();
            } 
    .

    PS After spending some time analysing efficiency of nested approach, I've come to a conclusion, tht there is one thing, that would be verry useful in this schema. It is depth.
    I've engineered schema with depth, and it gave me a lot of benefits in selecting.
    It did make an insert\delete\update procedures a bit heavier, but in sites case - that is a lot less important than selecting abilities of approach ^_^ .

    Hope this will be useful.

    PPS Once again - JDatabase, the db class used here can be easily translated to standard mysql. I just dont have the time, sorry guys
    I won't be sleeping for today anyways As for all this week
    Just google for "JDatabase api" and you will get all your answers there...
    Enjoy.


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •