Creating a PHP/MySQL Tree

  • xclanet
  • Born
  • Born
  • xclanet
  • Posts: 3

Post 3+ Months Ago

I was messing arround with code and i can't figure out to do this:

See attached image.

I have a Table in the database like this:

CREATE TABLE IF NOT EXISTS `nodetree` (
`node` int(11) NOT NULL,
`prevnode` int(11) NOT NULL,
`nextnode` int(11) NOT NULL,
`nodename` varchar(30) NOT NULL,
`nodelink` varchar(255) NOT NULL,
PRIMARY KEY (`node`,`prevnode`, `nextnode`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

What i want to do is to get php build that graph automatically with tables. Each node is a clickable link to node description.

Thanks in advance.
Attachments:
NodeTree.png
  • gisele
  • Expert
  • Expert
  • User avatar
  • Posts: 585
  • Loc: Nimes (France)

Post 3+ Months Ago

Hi,

the really indicated approach in that case is the use of a recursive function.

I see 3 little classes.

I see a class "node" witch would be a kind of POPO (Plain-Old PHP Object), simple value object containing only accessors (getPrev(), getName() ...)and mutators (setPrev(), setName()) just like beans / POJO java objects.

I see a NodeDao that maps the node object attributes with table fields name and do Read/write operation in db.
the methods are like that :
Node NodeDao::find(Node $node) => you just set the ID to the Node object and ask DAO to find and fullfill it.
array NodeDao::getChild(Node $node) => this method list children and return a collection of Node objects
Node NodeDao::Create(Node $createMe)
SQL statments are only in the DAO of course.
etc.

Then you can make a function or a method that can be called recursivly :
Code: [ Select ]
buildNode (NodeDao $dao, Node $node)
{
  [... here the code to build current cliquable node ...]

  //are there children?
  $nodeList = $dao->getChildren($node);

  foreach ($nodeList as $childNode){
   buildNode($dao, $childNode);// this the recursive call to the same build method foreach child found
  }
}
  1. buildNode (NodeDao $dao, Node $node)
  2. {
  3.   [... here the code to build current cliquable node ...]
  4.   //are there children?
  5.   $nodeList = $dao->getChildren($node);
  6.   foreach ($nodeList as $childNode){
  7.    buildNode($dao, $childNode);// this the recursive call to the same build method foreach child found
  8.   }
  9. }


Il you want more details on how to implement a DAO (Data access object ) feel free to ask.

If you are < PHP5 change the methods signature (remove the type hiting).

be careful to not repeat twice the same node id as a child in your table unless you fall into an aternel loop
  • gisele
  • Expert
  • Expert
  • User avatar
  • Posts: 585
  • Loc: Nimes (France)

Post 3+ Months Ago

Well, I feel like I should just add a couple of key informations.

1/ How should your process begin?

something like that

Code: [ Select ]
//assuming we have the root node id whatever the one it is in db
//you need a Dao instance
$O_dao = new NodeDao()
//build the root node and set its known id and ask DAO to fill it
$O_rootNode = new Node();
$O_rootNode->setId($S_rootId);//
$O_rootNode = $dao->find($rootNode);

//we have the root POPO node filled so let's build the treeview
$O_treeViewBuilder = new TreeViewBuilder();
//the method we call is the same that "buildTreview()" above but let's put the method in a class
$O_treeViewBuilder->build($O_dao, $O_rootNode);
  1. //assuming we have the root node id whatever the one it is in db
  2. //you need a Dao instance
  3. $O_dao = new NodeDao()
  4. //build the root node and set its known id and ask DAO to fill it
  5. $O_rootNode = new Node();
  6. $O_rootNode->setId($S_rootId);//
  7. $O_rootNode = $dao->find($rootNode);
  8. //we have the root POPO node filled so let's build the treeview
  9. $O_treeViewBuilder = new TreeViewBuilder();
  10. //the method we call is the same that "buildTreview()" above but let's put the method in a class
  11. $O_treeViewBuilder->build($O_dao, $O_rootNode);

That's it, we launched the whole treeView building since treeViewBuilder::build() we automatically go on recursivly while it will find children.

2. what does treevView builder class look like?
Code: [ Select ]

class TreeViewBuilder
  /**
   * build the current node
   * @param NodeDao
   * @param Node
   * @return string  html string
   */
  public method buildNode (NodeDao $O_dao, Node $O_node)
  {
     $S_html = '';
    /** [... here the code to build current cliquable node ($S_html), using info returned by Node object accessors...] */

    //are there children?
    $A_nodeList = $o_dao->getChildren($O_node);

    foreach ($A_nodeList as $O_childNode){
      $S_html .= $this->buildNode($O_dao, $O_childNode);// this the recursive call to the same build method foreach child found
    }

      return $S_html;
  }
}
  1. class TreeViewBuilder
  2.   /**
  3.    * build the current node
  4.    * @param NodeDao
  5.    * @param Node
  6.    * @return string  html string
  7.    */
  8.   public method buildNode (NodeDao $O_dao, Node $O_node)
  9.   {
  10.      $S_html = '';
  11.     /** [... here the code to build current cliquable node ($S_html), using info returned by Node object accessors...] */
  12.     //are there children?
  13.     $A_nodeList = $o_dao->getChildren($O_node);
  14.     foreach ($A_nodeList as $O_childNode){
  15.       $S_html .= $this->buildNode($O_dao, $O_childNode);// this the recursive call to the same build method foreach child found
  16.     }
  17.       return $S_html;
  18.   }
  19. }


3/ What does a DAO look like?
let's show examples of DAO methods
Code: [ Select ]
class NodeDao
{
  /**
   * find a Node in DB
   * @param Node
   * @return Node
   */
  public function find(Node $O_node)
  {
    if(!$O_node->getId()) {
      throw new Exception ('Node object should have an Id');
    }

    $S_sql = 'select ..... where node = \'' . mysql_real_escape_string($O_node->getId()) . '\'';
    $recordset = mysql_query($S_sql);
    if($A_row = mysql_fetch_assoc($R_recordset))
    {
      $O_nodeFind = clone $O_node;

      $O_nodeFind->setName($A_row['nodename']);
      $O_nodeFind->setLink($A_row['nodelink']);
      //etc.

      return $O_nodeFind;
    }
    else {
      throw new Exception ('Node "' .$node->getId(). '" not Find');
    }

    return $nodeFind;
  }

  /**
   * Find the children of a given node
   * @param Node
   * @return Node
   */
  public function getChildren(Node $O_parent)
  {
    if(!$O_parent->getId()) {
      throw new Exception ('Parent Node object should have an Id');
    }

    $A_found = array();



    $S_sql = 'select ..... where prevnode = \'' . mysql_real_escape_string($O_parent->getId()) . '\'';
    $R_recordset = mysql_query($S_sql);

    while($A_row = mysql_fetch_assoc($R_recordset))
    {
      $O_nodeFind = clone $node;
      $O_nodeFind->setId($A_row['node']);
      $O_nodeFind->setName($A_row['nodename']);
      $O_nodeFind->setLink($A_row['nodelink']);
      //etc.
      $A_found[$O_nodeFind->getId()] = $O_nodeFind;
    }

    return $A_found;
  }

  //etc. use Node accessor for whrite methods like create (for insertion), delete, update
  1. class NodeDao
  2. {
  3.   /**
  4.    * find a Node in DB
  5.    * @param Node
  6.    * @return Node
  7.    */
  8.   public function find(Node $O_node)
  9.   {
  10.     if(!$O_node->getId()) {
  11.       throw new Exception ('Node object should have an Id');
  12.     }
  13.     $S_sql = 'select ..... where node = \'' . mysql_real_escape_string($O_node->getId()) . '\'';
  14.     $recordset = mysql_query($S_sql);
  15.     if($A_row = mysql_fetch_assoc($R_recordset))
  16.     {
  17.       $O_nodeFind = clone $O_node;
  18.       $O_nodeFind->setName($A_row['nodename']);
  19.       $O_nodeFind->setLink($A_row['nodelink']);
  20.       //etc.
  21.       return $O_nodeFind;
  22.     }
  23.     else {
  24.       throw new Exception ('Node "' .$node->getId(). '" not Find');
  25.     }
  26.     return $nodeFind;
  27.   }
  28.   /**
  29.    * Find the children of a given node
  30.    * @param Node
  31.    * @return Node
  32.    */
  33.   public function getChildren(Node $O_parent)
  34.   {
  35.     if(!$O_parent->getId()) {
  36.       throw new Exception ('Parent Node object should have an Id');
  37.     }
  38.     $A_found = array();
  39.     $S_sql = 'select ..... where prevnode = \'' . mysql_real_escape_string($O_parent->getId()) . '\'';
  40.     $R_recordset = mysql_query($S_sql);
  41.     while($A_row = mysql_fetch_assoc($R_recordset))
  42.     {
  43.       $O_nodeFind = clone $node;
  44.       $O_nodeFind->setId($A_row['node']);
  45.       $O_nodeFind->setName($A_row['nodename']);
  46.       $O_nodeFind->setLink($A_row['nodelink']);
  47.       //etc.
  48.       $A_found[$O_nodeFind->getId()] = $O_nodeFind;
  49.     }
  50.     return $A_found;
  51.   }
  52.   //etc. use Node accessor for whrite methods like create (for insertion), delete, update


4/ what does a POPO like?
Node class is much more simple since it just has node encapsulated attributes, accessors and mutator.
It is manipulated by the Dao pour DB operations and the treev viewBuilder to retrieve node information on current node to build.
Code: [ Select ]
class Node
{
  protected $_S_id://node ID
  protected $_S_name;
  protected $_S_prev;
  //etc.

  /**
   * allows to get node Id
   * @return string
   */
  public function getId()
  {
    return $this->_S_id;
  }

  /**
   * allows to set node Id
   * @param string
   */
  public function setId($S_id)
  {
    $this->_S_id = (string) $S_id;
  }

  //etc.
}
  1. class Node
  2. {
  3.   protected $_S_id://node ID
  4.   protected $_S_name;
  5.   protected $_S_prev;
  6.   //etc.
  7.   /**
  8.    * allows to get node Id
  9.    * @return string
  10.    */
  11.   public function getId()
  12.   {
  13.     return $this->_S_id;
  14.   }
  15.   /**
  16.    * allows to set node Id
  17.    * @param string
  18.    */
  19.   public function setId($S_id)
  20.   {
  21.     $this->_S_id = (string) $S_id;
  22.   }
  23.   //etc.
  24. }
  • xclanet
  • Born
  • Born
  • xclanet
  • Posts: 3

Post 3+ Months Ago

That looks easy if for each node i have only 1 parent...

But for Node A3, Node A4, Node C6, Node E5 and Node F3 they have 2 parents, and this will provoque a recursive loop.
  • SpooF
  • ٩๏̯͡๏۶
  • Bronze Member
  • User avatar
  • Posts: 3422
  • Loc: Richland, WA

Post 3+ Months Ago

Are you looking for a way to show the tree graphically or just represent it in code?
  • gisele
  • Expert
  • Expert
  • User avatar
  • Posts: 585
  • Loc: Nimes (France)

Post 3+ Months Ago

Sorry,

in that case you will have to separate node notion and relation notion.
Relation object would be associations between 2 nodes(a parent- a child)
One step would to list node objects and build a node grid depending on X-Y Positions.
the sd step would be to list and lie on the grid the relations depending on parentX parent Y - child X child Y.

Anyway I think it's important to separate the grid logic and the relation logic so that the latter uses the former for its own representation.
You could also search for site map algorithms since it looks like the same problem.
  • xclanet
  • Born
  • Born
  • xclanet
  • Posts: 3

Post 3+ Months Ago

SpooF wrote:
Are you looking for a way to show the tree graphically or just represent it in code?

both. :wink:
gisele wrote:
Sorry,

in that case you will have to separate node notion and relation notion.
Relation object would be associations between 2 nodes(a parent- a child)
One step would to list node objects and build a node grid depending on X-Y Positions.
the sd step would be to list and lie on the grid the relations depending on parentX parent Y - child X child Y.

Anyway I think it's important to separate the grid logic and the relation logic so that the latter uses the former for its own representation.
You could also search for site map algorithms since it looks like the same problem.


I am searching it's been now 1 week... and i don't find anything that can leads me to something near.

Post Information

  • Total Posts in this topic: 7 posts
  • Users browsing this forum: No registered users and 25 guests
  • You cannot post new topics in this forum
  • You cannot reply to topics in this forum
  • You cannot edit your posts in this forum
  • You cannot delete your posts in this forum
  • You cannot post attachments in this forum
 
 

© 1998-2014. Ozzu® is a registered trademark of Unmelted, LLC.