Creating a non-binary tree from a two-dimensional array in PHP

Question

I am trying to set up a Treeview, provided by KendoUI, based on the values stored in a two-dimensional array. Unfortunateky i can't wrap my head around the creation of the datasource, which should be a multidimensional array used in JavaScript.

The plan is to recursively read the two dimensional array and piece by piece construct the datasource in PHP as a string and then pass it to the JavaScript function.

An example of the 2-dimensional array: (the key in the 1st dimension is the 'name' of the parent element; the keys of he child elements an integer and the value is the 'name' of the child)

Array
(
    [1] => Array
        (
            [0] => 2
            [1] => 3
            [2] => 4
        )

    [2] => Array
        (
            [0] => 3
        )

    [3] => Array
        (
            [0] => 3
            [1] => 1
        )
    [4] => Array
        (
            [0] => 2
        )
)

An example of what it should look like would be this (with two values):

  dataSource: [
    { text: "1", items: [
      { text: "2", items: [
        { text: "3" }
        ]},
      { text: "3" , items: [
        { text: "3" },
        { text: "1" }
        ]},
      { text: "4", items: [
        { text: "2", items: [
          { text: "3", items: [
            { text: "3" },
              { text: "1" }
            ] }
          ] }
        ] }
     ] },
    { text: "2", items: [
      { text: "3", items: [
        { text: "3" },
        { text: "1" , items: [
          { text: "1" },
          { text: "3" },
            { text: "4", items: [
              { text: "2" }
        ] }
          ] }
        ] }
     ] }
  ]

I know i have to account for infinite loops in the algorithm. The direct path from the 'leaf' to the 'root' aof the tree can only contain max 2 instances of a single value. If that condition is met, the branch is abandoned and shouldn't be filled any further.

Can anybody give me some pointers in the right direction with this? Is there some PHP class i can use to simplify this problem?

can you show the code of what you have done so far pls ?

Damien Legros
– Damien Legros

2019-07-26 12:30:55 +00:00
Commented Jul 26, 2019 at 12:30 — Damien Legros
– Damien Legros, Commented Jul 26, 2019 at 12:30
Are you trying to do this transformation in PHP or in JS?

Scott Sauyet
– Scott Sauyet

2019-07-26 12:33:58 +00:00
Commented Jul 26, 2019 at 12:33 — Scott Sauyet
– Scott Sauyet, Commented Jul 26, 2019 at 12:33

Scott Sauyet · Accepted Answer · 2019-07-26 16:02:45Z

If you want to transform your PHP structure to a simple JS Map, then you could use something like this in JS to create your structure:

const makeTree = (data, nodes = [...data .keys ()], path = []) => { 
  const res = nodes
    .filter ((id) => path .filter (x => x == id) .length < 2)
    .map((id) => {
      const kids = makeTree(data, data .get (id), path .concat (id));
      return {
        text: id,
        ...(kids .length ? {items: kids} : {})
      }
    })
    return res
}

const data = new Map([
  ['1', ['2', '3', '4']],
  ['2', ['3']],
  ['3', ['3', '1']],
  ['4', ['2']]
])


console .log (
  makeTree (data) 
)

makeTree accepts a Map like the above, a array containing the list of branch values, and and array containing the current path. The initial call defaults the branch values to the keys of the Map and defaults the path to an empty array. Subsequent calls calculate the nodes by looking up the current value in the map and append that value to the path.

I found it helpful in debugging to also include the path in the generated object:

      return {
        text: id,
        path: path.join('') + id,
        ...(kids .length ? {items: kids} : {})
      }

With a suitable display function, you can see the output hierarchically:

/*

1                                       (1)
...2                                    (12)
.......3                                (123)
...........3                            (1233)
...............1                        (12331)
...................2                    (123312)
...................4                    (123314)
.......................2                (1233142)
...........1                            (1231)
...............2                        (12312)
...................3                    (123123)
...............3                        (12313)
...............4                        (12314)
...................2                    (123142)
.......................3                (1231423)
...3                                    (13)
.......3                                (133)
...........1                            (1331)
...............2                        (13312)
...............4                        (13314)
...................2                    (133142)
.......1                                (131)
...........2                            (1312)
...............3                        (13123)
...........3                            (1313)
...........4                            (1314)
...............2                        (13142)
...................3                    (131423)
...4                                    (14)
.......2                                (142)
...........3                            (1423)
...............3                        (14233)
...................1                    (142331)
.......................2                (1423312)
.......................4                (1423314)
...........................2            (14233142)
...............1                        (14231)
...................2                    (142312)
.......................3                (1423123)
...................3                    (142313)
...................4                    (142314)
.......................2                (1423142)
...........................3            (14231423)
2                                       (2)
...3                                    (23)
.......3                                (233)
...........1                            (2331)
...............2                        (23312)
...............4                        (23314)
...................2                    (233142)
.......1                                (231)
...........2                            (2312)
...............3                        (23123)
...................1                    (231231)
.......................4                (2312314)
...........3                            (2313)
...............1                        (23131)
...................2                    (231312)
...................4                    (231314)
.......................2                (2313142)
...........4                            (2314)
...............2                        (23142)
...................3                    (231423)
.......................1                (2314231)
...........................4            (23142314)
3                                       (3)
...3                                    (33)
.......1                                (331)
...........2                            (3312)
...........4                            (3314)
...............2                        (33142)
...1                                    (31)
.......2                                (312)
...........3                            (3123)
...............1                        (31231)
...................2                    (312312)
...................4                    (312314)
.......................2                (3123142)
.......3                                (313)
...........1                            (3131)
...............2                        (31312)
...............4                        (31314)
...................2                    (313142)
.......4                                (314)
...........2                            (3142)
...............3                        (31423)
...................1                    (314231)
.......................2                (3142312)
.......................4                (3142314)
...........................2            (31423142)
4                                       (4)
...2                                    (42)
.......3                                (423)
...........3                            (4233)
...............1                        (42331)
...................2                    (423312)
...................4                    (423314)
.......................2                (4233142)
...........1                            (4231)
...............2                        (42312)
...................3                    (423123)
.......................1                (4231231)
...........................4            (42312314)
...............3                        (42313)
...................1                    (423131)
.......................2                (4231312)
.......................4                (4231314)
...........................2            (42313142)
...............4                        (42314)
...................2                    (423142)
.......................3                (4231423)
...........................1            (42314231)

*/

If you really want the input values to be numbers and the text nodes to be strings, you can just wrap id up as String(id) in the generated object.

This code depends upon each entry in each of the mapping values to be a key in the mapping. I don't know what would happen if it didn't. For all I know it will divide by zero, launch the nuclear missiles, and steal your boyfriend, so be wary!

Collectives™ on Stack Overflow

Creating a non-binary tree from a two-dimensional array in PHP

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related