php algorithm recursive tree

Question

I'm modifying an open source source script to show genealogy via organization chart style.

having users table with id and parentid field.

when I open /viewOrgChart?user_id=1 or numbers not in 2 3 4 5, it works well!

BUT when I open with user_id 2 3 4 5, it throw ERROR: Trying to get property 'parentid' of non-object the $us->parentid is having another level array inside... Error only happen for these few user id...

/viewOrgChart?user_id=2
/viewOrgChart?user_id=3
/viewOrgChart?user_id=4
/viewOrgChart?user_id=5

couldn't figure out what's wrong here.

And also I want to restrict the number of levels to display out based on the passed in user_id. Let's say I pass in with user_id=1 and I want to display everything up to 4 level down only

(in this case, it should show up to the level firstname=eng, below eng level all no need show) But... where to ..

Any algo expert?

<?php

    function wpmlm_get_all_user_details_join() {
        $sql = "SELECT * FROM users";
        $results = \DB::select($sql);
        return $results;
    }

    function wpmlm_get_user_details_by_id_join($user_id) {
        $sql = "SELECT * FROM users where id = '" . $user_id . "'";
        $results = \DB::select($sql);
        return $results;
    }

    function wpmlm_makeNested($source) {
        $nested = array();
    
        foreach ($source as &$s) {
            if (is_null($s['parent_id'])) {
                // no parent_id so we put it in the root of the array
                $nested[] = &$s;
            } else {
                $pid = $s['parent_id'];
                if (isset($source[$pid])) {
    
                    if (!isset($source[$pid]['children'])) {
                        $source[$pid]['children'] = array();
                    }
    
                    $source[$pid]['children'][] = &$s;
                }
            }
        }
        return $nested;
    }    

    function wpmlm_buildTree(array $elements, $parentId) {
        static $counter = 0;
        ++$counter;
        $tree = array();
        foreach ($elements as $element) {
            if ($element->id == $parentId) {
                if ($counter == 1) {
                    $tree[] = $this->wpmlm_get_user_details_by_id_join($parentId);
                }
            }
            if ($element->parentid == $parentId) {
                $children = $this->wpmlm_buildTree($elements, $element->id);
                if ($children) {
                    $tree[] = $children;
                }
    
                $tree[] = $element;
            }
        }
        return $tree;
    }  

    public function flattenArray($arr) 
    {
        for ($i = 0; $i < count($arr); $i++) {
            if (is_array($arr[$i])) {
                array_splice($arr, $i, 1, $arr[$i]);
            }
        }
        return $arr;
    }

    public function viewOrgChart(Request $request)
    {
        $user_id = $request->user_id;

        $user_details = $this->wpmlm_get_all_user_details_join();
    
        //$tree = $this->wpmlm_buildTree(elements, parentId);        
        $tree = $this->wpmlm_buildTree($user_details, $user_id);
        
        foreach ($tree as $key => $data) 
        {
            $test = $key; 
            
            if (is_array($data)) {
                foreach ($data as $sub_data) {
                    $tree = $this->flattenArray($tree);
                }
            }
        }
        $arr = array();
        $count = 0;
        foreach ($tree as $us) 
        {
            $count++;
            if ($count == 1) {
                $parent_id = null;
            } else {
                $parent_id = $us->parentid; //fail at here ERROR
            }
            $arr[$us->id] = Array(
                'name' => $us->firstname,
                'user_id' => $us->id,
                'user_code' => $us->usercode,          
                'parent_id' => $parent_id,
                'email' => $us->email,
            );
        }
        
        $uniLevelTree = $this->wpmlm_makeNested($arr);
    
        $treeJson = json_encode($uniLevelTree[0]);  
        
    }

?>

       <div id="unilevel-tree">
          <div class="panel-border">            
              <div id="chart-container"></div>
              <div id="test"></div>
          </div>
      </div>

<link rel='stylesheet' id='wp-mlm-bootstrap-css-css'  href='https://wpmlmsoftware.com/unilevel-mlm-demo/wp-content/plugins/wp-mlm/css/bootstrap.min.css?ver=5.2.1' type='text/css' media='all' />
<link rel='stylesheet' id='wp-mlm-font-awesome-css-css'  href='https://wpmlmsoftware.com/unilevel-mlm-demo/wp-content/plugins/wp-mlm/css/font-awesome.min.css?ver=5.2.1' type='text/css' media='all' />
<link rel='stylesheet' id='wp-mlm-orgchart-style-css-css'  href='https://wpmlmsoftware.com/unilevel-mlm-demo/wp-content/plugins/wp-mlm/css/orgchart-style.css?ver=5.2.1' type='text/css' media='all' />
<link rel='stylesheet' id='orgchart-css-css'  href='https://wpmlmsoftware.com/unilevel-mlm-demo/wp-content/plugins/wp-mlm/css/jquery.orgchart.css?ver=5.2.1' type='text/css' media='all' />
<link rel='stylesheet' id='admin-wp-mlm-style-css'  href='https://wpmlmsoftware.com/unilevel-mlm-demo/wp-content/plugins/wp-mlm/css/style.css?ver=5.2.1' type='text/css' media='all' />

<script type='text/javascript' src='https://wpmlmsoftware.com/unilevel-mlm-demo/wp-admin/load-scripts.php?c=0&amp;load%5B%5D=jquery-core,jquery-migrate,utils&amp;ver=5.2.1'></script>
<script type='text/javascript' src='https://wpmlmsoftware.com/unilevel-mlm-demo/wp-content/plugins/wp-mlm/js/bootstrap.min.js?ver=5.2.1'></script>
<script type='text/javascript' src='https://wpmlmsoftware.com/unilevel-mlm-demo/wp-content/plugins/wp-mlm/js/bootstrap-datepicker.js?ver=5.2.1'></script>

<script type='text/javascript' src='https://wpmlmsoftware.com/unilevel-mlm-demo/wp-content/plugins/wp-mlm/js/jquery.orgchart.js?ver=5.2.1'></script> 



<script type="text/javascript">

jQuery( document ).ready( function( $ ) {

    var datasource =<?php echo $treeJson; ?>

    var nodeTemplate = function(data) {
      return `
      <span class = "user-image d-flex justify-content-center" >
        <img src = "https://wpmlmsoftware.com/unilevel-mlm-demo/wp-content/plugins/wp-mlm/images/user.png" > 
      </span>
      <div class = "title" > ${data.name} </div>
      <div class = "" > ${data.email} </div>
      <div class = "" > ${data.user_id} </div>   
      `;

      };

      var oc = $('#chart-container').orgchart({
          'data' : datasource,
          'nodeTemplate': nodeTemplate
      });
 });
    
</script>

SQL:

CREATE TABLE `users` (
  `id` bigint(20) UNSIGNED NOT NULL,
  `email` varchar(255) COLLATE utf8mb4_unicode_ci NOT NULL,
  `created_at` timestamp NULL DEFAULT NULL,
  `firstname` varchar(255) COLLATE utf8mb4_unicode_ci DEFAULT NULL,
  `parentid` int(10) UNSIGNED DEFAULT NULL
);

INSERT INTO `users` (`id`, `firstname`, `email`, `created_at`, `usercode`, `parentid`) VALUES
(1, 'andrew', '[email protected]', '2020-11-24 05:22:42', 'MB800001', 0),
(2, 'beta', '[email protected]', '2020-11-24 05:22:42', NULL, 1),
(3, 'cicak', '[email protected]', '2020-11-24 05:22:42', NULL, 2),
(4, 'dorae', '[email protected]', '2020-11-24 05:22:43', NULL, 3),
(5, 'eng', '[email protected]', '2020-11-24 05:22:43', NULL, 4),
(6, 'Fanny', '[email protected]', '2020-11-24 05:22:43', NULL, 5),
(7, 'Gary', '[email protected]', '2020-11-24 05:22:43', NULL, 6),
(8, 'Hafiz', '[email protected]', '2020-11-24 05:22:43', NULL, 7),
(9, 'Isaac', '[email protected]', '2020-11-24 05:22:43', NULL, 8),
(10, 'louis', '[email protected]', '2020-11-24 05:22:44', NULL, 1),
(11, 'shze', '[email protected]', '2020-11-24 05:22:44', NULL, 1),
(12, 'paul', '[email protected]', '2020-11-24 05:22:44', NULL, 10),
(13, 'eunice', '[email protected]', '2020-11-24 05:22:44', NULL, 10),
(14, 'shaun', '[email protected]', '2020-11-24 05:22:44', NULL, 11),
(15, 'xiao', '[email protected]', '2020-11-24 05:22:44', NULL, 11),
(16, 'hui', '[email protected]', '2020-11-24 05:22:44', NULL, 11),
(17, 'gen', '[email protected]', '2020-11-24 05:22:45', NULL, 16),
(18, 'hani', '[email protected]', '2020-11-24 05:22:45', NULL, 17),
(19, 'hola', '[email protected]', '2020-11-24 05:22:45', NULL, 18),
(20, 'hugo', '[email protected]', '2020-11-24 05:22:45', NULL, 19),
(21, 'lady', '[email protected]', '2020-11-24 05:22:45', NULL, 18);

let's say pass in user_id=2 and restrict to show only 4 level under this user, then final json should be var datasource= {"name":"beta","user_id":2,"user_code":null,"parent_id":1,"email":"[email protected]","children":[{"name":"cicak","user_id":3,"user_code":null,"parent_id":2,"email":"[email protected]","children":[{"name":"dorae","user_id":4,"user_code":null,"parent_id":3,"email":"[email protected]","children":[{"name":"eng","user_id":5,"user_code":null,"parent_id":4,"email":"[email protected]","children":[{"name":"Fanny","user_id":6,"user_code":null,"parent_id":5,"email":"[email protected]"}]}]}]}]} — i need help
– i need help, Commented Nov 26, 2020 at 9:40

Matt · Accepted Answer · 2020-11-26 10:28:26Z

1

Here's a class I wrote which should do what you need:

<?php
class OrgTree {
    public $users;
    public function __construct($users) {
        $this->users = $users;
    }

    private function getUserById($userId) {
        return array_values(array_filter($this->users, function($user) use ($userId) {
            return $user['id'] === $userId;
        }))[0] ?? null;
    }

    private function getUsersByParentId($parentId) {
        return array_values(array_filter($this->users, function($user) use ($parentId) {
            return $user['parentid'] === $parentId;
        }));
    }
     

    private function buildTree($userDetails, $maxDepth, $currentDepth = 0) 
    {
        $info = [
            "name" => $userDetails['firstname'],
            "user_id" => $userDetails['id'],
            "user_code" => $userDetails['usercode'],
            "parent_id" => $userDetails['parentid'],
            "email" => $userDetails['email'],
        ];
        if ($maxDepth > $currentDepth) {
            $childUsers = $this->getUsersByParentId($userDetails['id']);
            $nextDepth = ++$currentDepth;
            $info['children'] = array_map(function($childUser) use ($nextDepth, $maxDepth) {
                return $this->buildTree($childUser, $maxDepth, $nextDepth);
            }, $childUsers);
        }
        return $info;
    }
    
    public function createOrgTree($userId, $maxDepth = 4) {
        return $this->buildTree($this->getUserById($userId), $maxDepth);
    }
}

You just need to pass in the users from your db:

public function viewOrgChart(Request $request) {
    $user_id = $request->user_id;
    $depth = 4; // get this from request if needed

    $user_details = $this->wpmlm_get_all_user_details_join();
           
    $orgTree = new OrgTree($user_details);
    $tree = $orgTree->createOrgTree($user_id, $depth);

    $treeJson = json_encode($tree);
}

You could also alter the class to pull users from the database as needed instead of receiving the full list at the start, as if you have a huge amount of users that approach would be more efficient, especially with low $depth values.

To do that you'd just remove:

public $users;
public function __construct($users) {
    $this->users;
}

and change getUserById and getUsersByParentId to perform SQL queries and return the data.

answered Nov 26, 2020 at 10:28

Matt

1,1781 gold badge9 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

i need help Over a year ago

hi Matt, it throw error at return $user['id'] === $userId; Error Cannot use object of type stdClass as array

Matt Over a year ago

How are you getting the users from db? Sounds like you need to get them as assoc array rather than object

i need help Over a year ago

i use laravel, they no longer support db FETCH_ASSOC, tried the toArray(); but doesn't work. I'm now thinking to manually reconstruct, is this suitable? foreach($results as $row) { $id = $row->id; $firstname = $row->firstname; $parentid = $row->parentid; $email = $row->email; $resultsxx[$id] = array( 'id' => $id, 'firstname' => $firstname, 'parentid' => $parentid, 'email' => $email ); }

Matt Over a year ago

Sorry I didn't realise that, your original example uses array access so I assumed that would work. The easiest way is probably to change any array accesses in the OrgTree class from array access, e.g., $user['firstname'] to object access, e.g., $user->firstname

i need help Over a year ago

i put breakpoint at __construct and gotten this structure, pasteboard.co/JC9HIPG.png pasteboard.co/JC9HTuS.png

|

Collectives™ on Stack Overflow

php algorithm recursive tree

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest