PHP Create a Multidimensional Array from an array with relational data

Question

Possible Duplicate:
Converting an array from one to multi-dimensional based on parent ID values

I am working in PHP.

I have the following array that has relational data (parent child relationships).

Array        
(        
    [5273] => Array        
        (        
            [id] => 5273        
            [name] => John Doe        
            [parent] =>         
        )        

    [6032] => Array        
        (        
            [id] => 6032        
            [name] => Sally Smith        
            [parent] => 5273        
        )        

    [6034] => Array        
        (        
            [id] => 6034        
            [name] => Mike Jones        
            [parent] => 6032        
        )        

    [6035] => Array        
        (        
            [id] => 6035        
            [name] => Jason Williams        
            [parent] => 6034        
        )        

    [6036] => Array        
        (        
            [id] => 6036        
            [name] => Sara Johnson        
            [parent] => 5273        
        )        

    [6037] => Array        
        (        
            [id] => 6037        
            [name] => Dave Wilson        
            [parent] => 5273        
        )        

    [6038] => Array        
        (        
            [id] => 6038        
            [name] => Amy Martin        
            [parent] => 6037        
        )        
)

I need it to be in this JSON format:

{        
   "id":"5273",        
   "name":"John Doe",        
   "data":{        

   },        
   "children":[        
      {        
         "id":" Sally Smith",        
         "name":"6032",        
         "data":{        

         },        
         "children":[        
            {        
               "id":"6034",        
               "name":"Mike Jones",        
               "data":{        

               },        
               "children":[        
                  {        
                     "id":"6035",        
                     "name":"Jason Williams",        
                     "data":{        

                     },        
                     "children":[        
                        {        
                           "id":"node46",        
                           "name":"4.6",        
                           "data":{        

                           },        
                           "children":[        

                           ]        
                        }        
                     ]        
                  }        
               ]        
            },        
            {        
               "id":"6036",        
               "name":"Sara Johnson",        
               "data":{        

               },        
               "children":[        

               ]        
            },        
            {        
               "id":"6037",        
               "name":"Dave Wilson",        
               "data":{        

               },        
               "children":[        
                  {        
                     "id":"6038",        
                     "name":"Amy Martin",        
                     "data":{        

                     },        
                     "children":[        

                     ]        
                  }        
               ]        
            }        
         ]        
      }        
   ]        
}

I know I need to create a multidimensional array and run it through json_encode(). I also believe this method used to do this needs to be recursive because the real world data could have an unknown number of levels.

I would be glad to show some of my approaches but they have not worked.

Can anyone help me?

I was asked to share my work. This is what I have tried but I have not gotten that close to I don't know how helpful it is.

I made an array of just the relationships.

foreach($array as $k => $v){
    $relationships[$v['id']] = $v['parent'];
}

I think (based off another SO post) used this relational data to create a the new multidimensional array. If I got this to work I was going to work on adding in the correct "children" labels etc.

$childrenTable = array();
    $data = array();
    foreach ($relationships as $n => $p) {
      //parent was not seen before, put on root
      if (!array_key_exists($p, $childrenTable)) {
          $childrenTable[$p] = array();
          $data[$p] = &$childrenTable[$p];  
      }
      //child was not seen before
      if (!array_key_exists($n, $childrenTable)) {
          $childrenTable[$n] = array();
      }
      //root node has a parent after all, relocate
      if (array_key_exists($n, $data)) {
          unset($data[$n]);
      }
      $childrenTable[$p][$n] = &$childrenTable[$n];      
    }
    unset($childrenTable);

print_r($data);

The initial format you posted *is* a multidimensional array. Shouldn't that work in json encode? — Ben Roux, Jun 28 '12 at 07:13
Ben Roux, Yes, that is a multidimensional array but it is not in the correct format to produce that JSON. — maestrojed, Jun 28 '12 at 07:18
what you have tried ? post your code how you are preparing array. — Sanjay, Jun 28 '12 at 07:37
Sanjay, I added a little of my work to my question. I couldn't get the formatting correct in the comments. I have also tried a do-while but failed there too. — maestrojed, Jun 28 '12 at 07:53
Yoshi, I went back and credited all previous answers that were certain solutions. I hope this helps. I will keep up with this better in the future. — maestrojed, Jun 28 '12 at 07:55

Yoshi · Accepted Answer · 2016-10-25T16:57:23.070

16

<?php
header('Content-Type: application/json; charset="utf-8"');

/**
 * Helper function
 * 
 * @param array   $d   flat data, implementing a id/parent id (adjacency list) structure
 * @param mixed   $r   root id, node to return
 * @param string  $pk  parent id index
 * @param string  $k   id index
 * @param string  $c   children index
 * @return array
 */
function makeRecursive($d, $r = 0, $pk = 'parent', $k = 'id', $c = 'children') {
  $m = array();
  foreach ($d as $e) {
    isset($m[$e[$pk]]) ?: $m[$e[$pk]] = array();
    isset($m[$e[$k]]) ?: $m[$e[$k]] = array();
    $m[$e[$pk]][] = array_merge($e, array($c => &$m[$e[$k]]));
  }

  return $m[$r][0]; // remove [0] if there could be more than one root nodes
}

echo json_encode(makeRecursive(array(
  array('id' => 5273, 'parent' => 0,    'name' => 'John Doe'),  
  array('id' => 6032, 'parent' => 5273, 'name' => 'Sally Smith'),
  array('id' => 6034, 'parent' => 6032, 'name' => 'Mike Jones'),
  array('id' => 6035, 'parent' => 6034, 'name' => 'Jason Williams'),
  array('id' => 6036, 'parent' => 5273, 'name' => 'Sara Johnson'),
  array('id' => 6037, 'parent' => 5273, 'name' => 'Dave Wilson'),
  array('id' => 6038, 'parent' => 6037, 'name' => 'Amy Martin'),
)));

demo: https://3v4l.org/s2PNC

edited Oct 25 '16 at 16:57

answered Jun 28 '12 at 08:14

Yoshi

54,081
14
89
103

Yoshi, Thank you. I ran your code against the test and it work great. However when I implemented some real world data can be 300-400 people. I get a PHP exhausted 128mb of memory error. I understand 300-400 records is more then the example I provided but I didn't think it would be considered a large data set. Any ideas? Does it make sense that this used such much memory? – maestrojed Jun 28 '12 at 09:25
@maestrojed There was an error in my first version (probably the cause for the memory leak), please have a look at the update. – Yoshi Jun 28 '12 at 09:37
1

That worked and was more then I expected. Thanks for the help. I look forward to analyzing it and learning something! – maestrojed Jun 29 '12 at 00:02
1

@Yoshi after few checking I have find out that You should `return $m[$r]` if You have more than one _top level parents_. Anyway thanks for that solution. – bumerang Jan 14 '13 at 06:24
@Yoshi your example is working fine for single parent category(parent is 0).but its not working when there are more than one parent category. could you please give me soultion? – Jimmy Dec 04 '13 at 10:28
@bumerang yes got ehe solution from you comment. Thanks. – Jimmy Dec 04 '13 at 10:31
@Yoshi , please can you explain how data is going into [children] => Array() – Lovepreet Singh Batth Sep 08 '17 at 08:20
@LovepreetSinghBatth It's a bit hidden. The trick is the reference (the `&`) here `$c => &$m[$e[$k]]`. With this a reference to the value in `$m` is assigned and not a copy. This way all later manipulations will happen in the correct children arrays. – Yoshi Sep 08 '17 at 09:03
1

@Yoshi got it thanks bro, You mean this (ref - &) is putting the variable itself inside children part, not a copy of its value, which is getting its value on final output – Lovepreet Singh Batth Sep 08 '17 at 09:46
A little modification, may help some one, https://stackoverflow.com/questions/46129056/deleting-a-item-from-multilevel-category-or-menu-list – Lovepreet Singh Batth Sep 12 '17 at 04:05

score 3 · Answer 2 · answered Dec 25 '12 at 19:52

Okay, this is how it works, you were actually not too far off as you started, but what you actually look for are references. This is a general procedure:

As there is a relation between parent and child-nodes on their ID, you first need to index the data based on the ID. I do this here with an array ($rows) to simulate your data access, if you read from the database, it would be similar. With this indexing you can also add additional properties like your empty data:

// create an index on id
$index = array();
foreach($rows as $row)
{
    $row['data'] = (object) array();
    $index[$row['id']] = $row;
}

So now all entries are indexed on their ID. This was the first step.

The second step is equally straight forward. Because we now can access each node based on it's ID in the $index, we can assign the children to their parent.

There is one "virtual" node, that is the one with the ID 0. It does not exists in any of the rows, however, if we could add children to it too, we can use this children collection as the store for all root nodes, in your case, there is a single root node.

Sure, for the ID 0, we should not process the parent - because it does not exists.

So let's do that. We make use of references here because otherwise the same node could not be both parent and child:

// build the tree
foreach($index as $id => &$row)
{
    if ($id === 0) continue;
    $parent = $row['parent'];
    $index[$parent]['children'][] = &$row;
}
unset($row);

Because we use references, the last line takes care to unset the reference stored in $row after the loop.

Now all children have been assigned to their parents. That could it be already, however lets not forget the last step, the actual node for the output should be accessed.

For brevity, just assign the root node to the $index itself. If we remember, the only root node we want is the first one in the children array in the node with the ID 0:

// obtain root node
$index = $index[0]['children'][0];

And that's it. We can use it now straight away to generate the JSON:

// output json
header('Content-Type: application/json');
echo json_encode($index);

Finally the whole code at a glance:

<?php
/**
 * @link http://stackoverflow.com/questions/11239652/php-create-a-multidimensional-array-from-an-array-with-relational-data
 */

$rows = array(
    array('id' => 5273, 'parent' => 0,    'name' => 'John Doe'),
    array('id' => 6032, 'parent' => 5273, 'name' => 'Sally Smith'),
    array('id' => 6034, 'parent' => 6032, 'name' => 'Mike Jones'),
    array('id' => 6035, 'parent' => 6034, 'name' => 'Jason Williams'),
    array('id' => 6036, 'parent' => 5273, 'name' => 'Sara Johnson'),
    array('id' => 6037, 'parent' => 5273, 'name' => 'Dave Wilson'),
    array('id' => 6038, 'parent' => 6037, 'name' => 'Amy Martin'),
);

// create an index on id
$index = array();
foreach($rows as $row)
{
    $row['data'] = (object) [];
    $index[$row['id']] = $row;
}

// build the tree
foreach($index as $id => &$row)
{
    if ($id === 0) continue;
    $parent = $row['parent'];
    $index[$parent]['children'][] = &$row;
}
unset($row);

// obtain root node
$index = $index[0]['children'][0];

// output json
header('Content-Type: application/json');
echo json_encode($index, JSON_PRETTY_PRINT);

Which would create the following json (here with PHP 5.4s' JSON_PRETTY_PRINT):

{
    "id": 5273,
    "parent": 0,
    "name": "John Doe",
    "data": {

    },
    "children": [
        {
            "id": 6032,
            "parent": 5273,
            "name": "Sally Smith",
            "data": {

            },
            "children": [
                {
                    "id": 6034,
                    "parent": 6032,
                    "name": "Mike Jones",
                    "data": {

                    },
                    "children": [
                        {
                            "id": 6035,
                            "parent": 6034,
                            "name": "Jason Williams",
                            "data": {

                            }
                        }
                    ]
                }
            ]
        },
        {
            "id": 6036,
            "parent": 5273,
            "name": "Sara Johnson",
            "data": {

            }
        },
        {
            "id": 6037,
            "parent": 5273,
            "name": "Dave Wilson",
            "data": {

            },
            "children": [
                {
                    "id": 6038,
                    "parent": 6037,
                    "name": "Amy Martin",
                    "data": {

                    }
                }
            ]
        }
    ]
}

@LovepreetSinghBatth: It's "Because we use references, the last line takes care to unset the reference stored in $row after the loop." below the example it is in. — hakre, Sep 11 '17 at 18:33

score 2 · Answer 3 · answered Jun 28 '12 at 08:14

Following code will do the job.. you may want to tweak a bit according to your needs.

$data = array(
    '5273' => array( 'id' =>5273, 'name'=> 'John Doe', 'parent'=>''),
    '6032' => array( 'id' =>6032, 'name'=> 'Sally Smith', 'parent'=>'5273'),
    '6034' => array( 'id' =>6034, 'name'=> 'Mike Jones ', 'parent'=>'6032'),
    '6035' => array( 'id' =>6035, 'name'=> 'Jason Williams', 'parent'=>'6034')
    );

$fdata = array();


function ConvertToMulti($data) {
    global $fdata;

    foreach($data as $k => $v)
    {
        if(empty($v['parent'])){
            unset($v['parent']);
        $v['data'] = array();
        $v['children'] = array();
            $fdata[] = $v;
        }
        else {
            findParentAndInsert($v, $fdata);
        }

    }
}

function findParentAndInsert($idata, &$ldata) {

    foreach ($ldata as $k=>$v) {

        if($ldata[$k]['id'] == $idata['parent']) {
            unset($idata['parent']);
        $idata['data'] = array();
        $idata['children'] = array();
            $ldata[$k]['children'][] = $idata;
            return;
        }
        else if(!empty($v['children']))
            findParentAndInsert($idata, $ldata[$k]['children']);
    }
}


print_r($data);
ConvertToMulti($data);
echo "AFTER\n";
print_r($fdata);

http://codepad.viper-7.com/Q5Buaz

I am going to keep trying this in the morning. On first implementation it seemed to have issues. I am not sure what yet and will try to comment back with details. When I implemented it I don't get an error and the structure seems right but a lot of data is missing. — maestrojed, Jun 28 '12 at 09:27
Please note couple of things, Firstly, Fill the $data array with yours. It does not have all the values you used in the question. Secondly, You can make the $fdata local to ConvertToMulti function. Making it global may cause problem in your implementation. Good Luck with your implementation — FatalError, Jun 28 '12 at 09:36

PHP Create a Multidimensional Array from an array with relational data

3 Answers3

Linked

Related